The function I want to discuss is a curried version of map. First we examine the non-curried version:
fun map' (f, nil) = nil | map' (f, h::t) = (f h) :: map' (f, t);
The author claims that it is a tad inefficient to keep passing "f" around, so he creates this curried version:
fun map f nil = nil | map f (h::t) = (f h) :: (map f t);
I am trying to understand this, clause-by-clause. My first step is to expand
fun map f nil = nil
which turns out to be:
val map = fn f => (fn nil => nil)
and the thing to note here is that "fn nil" is pattern matching.
But my question are:
1. Regardless of the syntax, I know that the second clause is going to look something like this:
fn f => (fn (h::t) => (f h) :: (map f t));
and what is happening is that (map f t) transforms into (map f) t , meaning that instead of repeated recursive calls, map the dyadic function has been changed into (map f) the monad which simply iterates across t .
Is this is more efficient? Why?
2. Given that my expansion for the second clause is correct, how do I append the next clause for non-empty lists onto this function?
Understanding the currying of map
Maybe this will shed some light on the situation:
- val r = (map (fn x => x - 5)) ; val r = fn : int list -> int list - r [1,23,4,5]; val it = [~4,18,~1,0] : int list -