SML map function

Question

I have the function:

map(map(fn x =>[x])) [[],[1],[2,3,4]];

Which produces:

val it = [[],[[1]],[[2],[3],[4]]]

I don't understand how this function works. Doesn't each map function need both a function and a list? It seems that there isn't enough arguments for this to actually execute.

If I run:

map(fn x =>[x]) [[],[1],[2,3,4]];

I get:

val it = [[[]], [[1]], [[2,3,4]]];

Which makes more sense to me, as it takes each element in the list, and wraps it in another list. But when I put another map on it, it changes the output. Can anyone explain this to me? Thank you!

Answer 1

You said:

I don't understand how this function works. Doesn't each map function need both a function and a list?

Well, keep in mind than, in Standard ML (and, in general, all applicative languages), there is no such thing as a "function of n parameters", for "n" other than 1. However, functions of more than one parameter can be simulated in two ways:

1. As functions of a single parameter that is a tuple or record. The original intended parameters can be recovered in the function's body by means of projection from the tuple or record.

2. As functions of the first parameter that return a function of the remaining parameters.

With this in mind, we check map's type in the REPL:

> map;
val it = fn: ('a -> 'b) -> 'a list -> 'b list

(I use Poly/ML, not SML/NJ, but formatting issues aside, the output should be the same.)

No tuples, no records. map clearly takes the second approach to simulating a function of two parameters: it takes a function of type 'a -> 'b and returns another function of type 'a list -> 'b list.

Now, here is the catch: For any function foo, map foo is a function as well! Since map can take any function as argument, map foo is itself a perfectly legitimate argument for map. Which means that map (map foo) typechecks for any function foo. In particular, this is true if val foo = fn x => [x].

---

You said:

It seems that there isn't enough arguments for this to actually execute.

If it typechecks, it runs.

---

You said:

If I run

map (fn x => [x]) [[], [1], [2,3,4]]

I get

val it = [[[]], [[1]], [[2,3,4]]];

Which makes more sense to me, as it takes each element in the list, and wraps it in another list. But when I put another map on it, it changes the output.

Let's refactor your code a little bit, without changing its meaning:

let
  val foo = fn x => [x]
  val bar = map foo
  val baz = map bar
in
  baz [[], [1], [2,3,4]]
end

Now we can analyze what every function (foo, bar, baz) does to its parameter:

1. foo takes a single element x and wraps it in a list data constructor.
2. bar takes a list of elements, wraps each element in a list data constructor, and returns a list with the resulting wrapped elements (a list of lists).
3. baz takes a (super)list of (sub)lists of elements, applies bar to every sublist, and returns a list with the results.

Perform all of this manually to convince yourself that the result, [[], [[1]], [[2], [3], [4]]], is indeed correct.