Re: vector dot multiply

Re: vector dot multiply

[Chet Murthy]

> >Also, is there a similar construct to Haskell array/list comprehensions?
>
> Bird and Wadler's book gives a simple translation scheme
> for list comprehensions to map+filter functions (pp63-64).
> This may meet your requirements.

That translation is wildly inefficient, too.  There's a reason
that lazy languages, and pure languages, haven't caught on --
it's called efficiency.  It's far more efficient to construct
a decent set of imperative classes (e.g. Rogue Wave Vector Classes)
than to try to import into CAML (which was, after all, designed
to (IMHO) not penalize the imperative code writer) the constructs of
intrinsically broken languages like Haskell.


>> ...
>> Also, is there a similar construct to Haskell array/list comprehensions?
>
>There is indeed one construct called streams.

Unfortunately, these streams are *not* the same as array/list comprehensions
-- they are "read-once", lazy, and impure.  So they're far more suitable
for I/O, and other such things, than for implementing such comprehensions.

--chet--

Re: vector dot multiply

[nikhil]

Chet Murthy writes:
>    > >Also, is there a similar construct to Haskell array/list comprehensions?
>    >
>    > Bird and Wadler's book gives a simple translation scheme
>    > for list comprehensions to map+filter functions (pp63-64).
>    > This may meet your requirements.
>    
>    That translation is wildly inefficient, too.  There's a reason
>    that lazy languages, and pure languages, haven't caught on --
>    it's called efficiency.  It's far more efficient to construct
>    a decent set of imperative classes (e.g. Rogue Wave Vector Classes)
>    than to try to import into CAML (which was, after all, designed
>    to (IMHO) not penalize the imperative code writer) the constructs of
>    intrinsically broken languages like Haskell.

I don't understand why the question about list/array comprehensions
provokes this sharp comment about lazy languages and Haskell in
particular.

1) List comprehensions and array comprehensions are simply a
   convenient way to express nested loops, collecting a subset of the
   results.  The notation is completely neutral to whether you embed
   it in a strict, lazy, pure or impure language.  It has nothing
   to do do with Haskell per se.

   In fact, modern list comprehension notation was originally
   introduced by Darlington and Burstall in the _strict_ language Hope
   at Edinburgh.

   A similar construct existed even earlier in the _strict_, _impure_
   language SETL from New York University.

   List and array comprehensions also appear in Id, which is an _impure_
   language.

2) The translation in Bird and Wadler (page 63-64) is given purely for
   illustrative purposes, and was never claimed to be the way to
   implement them efficiently.  It's simply meant to build an
   intuitive connection between list comprehensions and maps and filters.

   A better, more efficiecy-motivated, translation is given (by
   Wadler) in Peyton Jones' book (Ch 7).  It is optimal in the sense
   that it does not cons unnecessarily.  Even better translations
   exist in existing compilers using just loops.

So, to summarize: there's nothing inefficient per se about list and
array comprehensions, and the notation has no specific connection to
lazy languages or to Haskell.

Nikhil

Re: vector dot multiply

[Judicael Courant]

> In order to avoid to (re)compute the length of a at each recursive call, you
> can modify a little your function as follows
>
>  let dot a b = let rec dot_aux a b i sum L =
>  if i < L then
>     dot_aux a b (i+1) (sum +. (a.(i) *. b.(i))) L
>  else
>     sum
>  in dot_aux a b 0 0.0 (vect_length a) ;;

in order to avoid adding a new parameter, one can also write :


let dot a b =
  let rec dot_aux i sum =
    match i with
       -1 -> sum
     |  i -> dot_aux (i-1) (sum +. (a.(i) *. b.(i)))
  else
    sum
in dot_aux ((vect_length a)-1) 0.0  ;;

let dot a b = let rec dot_aux i sum =
 if i >= 0 then
   dot_aux (i-1) (sum +. (a.(i) *. b.(i))) L
 else
    sum
in dot_aux ((vect_length a)-1) 0.0  ;;

(notice that it is a classical way to obtain a tail-recursion from
a non-terminal one : the previous form is obtained from

let dot a b
  let rec dot_aux i =
   match i with
     0 -> 0
   | k -> (a.(i) * b.(i)) + (dot_aux (i-1))
in dot_aux ((vect_length a)-1);;

as

let fact n =
 match n with
   0 -> 1
 | k -> k*(fact (k-1))
;;

becomes

let fact n =
 let rec fact_aux n prod =
   match n with
     0 -> prod
   | k -> k*(fact_aux (k-1))
;;
)

Judicael Courant
-- 
||   Judicael.Courant@ens-lyon.fr    \\ ``Big Brother is watching  \\
|| http://www.ens-lyon.fr/~jcourant/  \\           YOU ! ''         \\
||         tel : 72 72 85 82           \\       G. Orwell, 1984      \\

Re: vector dot multiply

[Pascal Nicolas]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 902 bytes --]

> 
> Hi,
>  What would be 1). elegant
>                2). efficient  
>  way to write a "dot multiply" function in caml-light? 
> This is what I came up with but I am hoping for a better one :
> 
> let dot a b = let rec dot_aux a b i sum =
> if i< vect_length a then
>    dot_aux a b (i+1) (sum +. (a.(i) *. b.(i)) )
>  else
>    sum
> in
>  dot_aux a b 0 0.0;;
> 
In order to avoid to (re)compute the length of a at each recursive call, you
can modify a little your function as follows

 let dot a b = let rec dot_aux a b i sum L =
 if i < L then
    dot_aux a b (i+1) (sum +. (a.(i) *. b.(i))) L
 else
    sum
 in dot_aux a b 0 0.0 (vect_length a) ;;


--
Pascal NICOLAS                                       LERIA  Université d'ANGERS
Tél : (33) 41 73 54 20             2, Bd Lavoisier 49045 ANGERS cedex 01 FRANCE
E Mail : pn@univ-angers.fr
WWW Url : http://www.univ-angers.fr/~pn/nicolas.html

Re: vector dot multiply

[Bob Buckley]

>Also, is there a similar construct to Haskell array/list comprehensions?

Bird and Wadler's book gives a simple translation scheme
for list comprehensions to map+filter functions (pp63-64).
This may meet your requirements.

	b++

Re: vector dot multiply

[Ascander Suarez]

Concerning your second question:

> ... 
> Also, is there a similar construct to Haskell array/list comprehensions?

There is indeed one construct called streams.

				Ascander (suarez@usb.ve)

---------- streamExamples.ml -----------

(*  A stream of natural numbers *)

let rec generate f b = [< 'b; (generate f (f b)) >];;

let nats = generate succ 0;;

(* With this definition, the stream natS 
   is the structure [< '0; '1; '2; ... >]
*)

(* A stream of Fibonacci numbers needs two generators
   and can be defined as:  
*)

let rec generate2 f b1 b2 = [< 'b1; (generate2 f b2 (f b1 b2)) >];;

let fibs = generate2 (prefix +) 1 1;;

(* Finally, primes can be computed as follows: 
*)

let rec filter n = 
 function [< 'm; s >] -> 
    if m mod n = 0 then filter n s 
    else [< 'm; (filter n s) >];;

let rec scieve = function [< 'm; s >] -> [< 'm; scieve(filter m s) >];;

let primes = [< '1; scieve (generate succ 2) >];;

(* 
   Notice that streams in Caml light are a little bit surprising in that 
   for any (big) stream s and any integer n, after

let s' = (function [< 'x1; 'x2; ...  'xn; restOfStream >] -> restOfStream) s;;

the streams s and s' are the same.

*)

Re: vector dot multiply

[Pierre Weis]

> Hi,
>  What would be 1). elegant
>                2). efficient  
>  way to write a "dot multiply" function in caml-light? 

You're recursive version seems good (except that you (re)compute
the vect_length of vector a at each recursive call). You may prefer an
imperative version (as yours, this function assumes a and b to have the
same length):

let dot a b =
  let s = ref 0.0 in
  for i = 0 to vect_length a - 1 do
   s := a.(i) *. b.(i) +. !s
  done;
  !s;;

> Also, is there a similar construct to Haskell array/list comprehensions?

No. This is very difficult to get in a strict language, where these
lists cannot be computed as necessary as is done in lazy languages...

Pierre Weis
----------------------------------------------------------------------------
WWW Home Page: http://pauillac.inria.fr/~weis
Projet Cristal
INRIA, BP 105, F-78153 Le Chesnay Cedex (France)
E-mail: Pierre.Weis@inria.fr
Telephone: +33 1 39 63 55 98
Fax: +33 1 39 63 53 30
----------------------------------------------------------------------------

vector dot multiply

[U-E59264-Osman Buyukisik]

Hi,
 What would be 1). elegant
               2). efficient  
 way to write a "dot multiply" function in caml-light? 
This is what I came up with but I am hoping for a better one :

let dot a b = let rec dot_aux a b i sum =
if i< vect_length a then
   dot_aux a b (i+1) (sum +. (a.(i) *. b.(i)) )
 else
   sum
in
 dot_aux a b 0 0.0;;

Also, is there a similar construct to Haskell array/list comprehensions?

Thanks in advance.
Osman