Re: curried fns

[John Harrison <jharriso@ra.abo.fi>]

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



| 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
=========================================================================