Message-Id: <199511201806.UAA21038@tanichka.abo.fi>
To: Jocelyn Serot <Jocelyn.Serot@lasmea.univ-bpclermont.fr>
Subject: Re: curried fns
Date: Mon, 20 Nov 1995 20:06:42 +0200
From: John Harrison <jharriso@ra.abo.fi>
| Could someone please explain the difference(s) between:
|
| let f x = function y -> y + x;;
|
| and
|
| let f x y = y + x;;
Those should behave identically, even w.r.t evaluation. The two phrases
"let f x = t[x]" and "let f = fun x -> t[x]" are essentially identical.
However in the example you give below, you do additional computation
after getting the first argument:
| let h x = let z = fact x in fun y -> y + z;;
The evaluation strategy of ML is as follows: to evaluate "f x", first
evaluate "f", then evaluate "x" (to "x'"), then if "f" evaluates to a
lambda expression "\v. t[v]", recursively evaluate "t[x']"; otherwise
stop. Evaluation of "f x y" is, of course, just evaluation of "(f x) y",
so the above scheme means "f x" gets evaluated first. However ML will
*not* evaluate inside lambdas, so applying "\u. \v. t[u,v]" to a single
argument "x" just gives "\v. t[x,v]" and evaluation then stops, even if
the body is independent of v. However your example "h" then permits
further evaluation. (In the above I use "\x. t[x]" for "fun x -> t[x]".)
Of course, in a pure functional language one can safely evaluate inside
lambdas, but in a language like ML where there may be imperative bits
floating around, the distinction is important. Doing the kind of "partial
evaluation" you cite is a very important technique in writing efficient
code. (Having said that, I'm surprised compilers don't try to identify
"non-imperative" parts and evaluate them -- of course one has to be
careful with exceptions -- it's not really any different from constant
folding in C compilers.) Conversely, it can occasionally be useful to
delay evaluation by introducing eta-redexes (i.e. including additional
arguments), in particular when defining higher order functions
recursively. For example given:
let I x = x;;
let THEN f g x = g(f x);;
#infix "THEN";;
let ORELSE f g x = try f x with _ -> g x;; (* Sorry, Xavier! *)
#infix "ORELSE";;
the following will loop when applied:
let rec REPEAT f = (f THEN (REPEAT f)) ORELSE I;;
whereas this works:
let rec REPEAT f x = ((f THEN (REPEAT f)) ORELSE I) x;;
Something I sometimes wonder about is which of the following is more
efficient. Perhaps a CAML Light expert can comment.
let map f =
let rec mapf l =
match l with
[] -> []
| (x::t) -> let y = f x in y::(mapf t) in
mapf;;
or
let rec map f l =
match l with
[] -> []
| (x::t) -> let y = f x in y::(map f t);;
John.
=========================================================================
John Harrison | email: jharriso@ra.abo.fi
Åbo Akademi University | web: http://www.abo.fi/~jharriso/
Department of Computer Science | phone: +358 (9)21 265-4049
Lemminkäisenkatu 14a | fax: +358 (9)21 265-4732
20520 Turku | home: +358 (9)21 2316132
FINLAND | time: UTC+2:00
=========================================================================