NEXT ·  UP ·  PREVIOUS ·  CONTENTS ·  INDEX

The map function

The map function has type ('a -> 'b) -> (('a list) -> ('b list)). It behaves as though implemented by the following definition.

fun map f [] = []
  | map f (h::t) = f h :: map f t;

The map function preserves totality: if f is a total function--meaning that it never goes into an infinite loop and never raises an exception--then so is map f. However, map itself is not a total function since we can find f and l such that map f l is not defined.

Note the rather lack-lustre role of the function parameter f in the implementation of map above: it is simply passed back into the recursive call of the function unchanged. This suggests that it can be factored out using a let .. in .. end as shown below.

fun map f = let fun map_f [] = []
                  | map_f (h::t) = f h :: map_f t
            in  map_f
            end;

Such definitions are not always easy to read! However, depending on the implementation technique employed by the Standard ML system being used, factoring out the parameter in this way may lead to a more efficient implementation of map.

NEXT ·  UP ·  PREVIOUS ·  CONTENTS ·  INDEX