curried fns

Jocelyn Serot
 John Harrison
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:   (:) 
From:  John Harrison <jharriso@r...> 
Subject:  Re: curried fns 
 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 "nonimperative" 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 etaredexes (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 2654049 Lemminkäisenkatu 14a  fax: +358 (9)21 2654732 20520 Turku  home: +358 (9)21 2316132 FINLAND  time: UTC+2:00 =========================================================================