- A+

I set myself the following challenge (and failed):

I want to write a map functional, `map f lofls`

, that takes a function, f `'a -> 'b`

and a list of lists, lofls `'a list list`

and applies the function `f`

on every element of the list of lists. The constraint that I added is that I am not allowed to used nested maps for lists, and I have to do it recursively.

I tried to do it in F# but any language should do. Any ideas?

## Edit

Here is my attempt (which works but is ugly and I am not a fan of the use of rev either . . .)

`let map f lis = let rec map2 f lis aux = match (lis, aux) with |([], []) -> [] |([], aux) -> [aux] |(hd::tl, aux) -> match hd with |[] -> (List.rev aux) :: (map2 f tl []) |x::xs -> map2 f (xs::tl) ( (f x) :: aux ) map2 f lis [] `

(I also realised that this has been posted in a more concise form already)

I'm not sure why this question is tagged with SML, but since it is, here is how it can be done in SML:

First, this is the idiomatic solution that you're explicitly avoiding:

`fun mapmap f = map (map f) `

*(You could write val mapmap = map o map if it weren't for ML's value restriction.)*

And if you'd like to write `mapmap`

using explicit recursion:

`fun mapmap f [] = [] | mapmap f (xs::xss) = map f xs :: mapmap f xss and map f [] = [] | map f (x::xs) = f x :: map f xs `

One reason behind why this function is hard to write with a single explicitly recursive function is that the call stack is used for two things:

- Collecting the result of each inner list, and
- Collecting the result of the outer list.

One of those uses of the call stack can be turned into an explicit stack in an accumulating argument. This is how e.g. a tail-recursive `rev`

is defined:

`fun rev xs = let fun aux [] acc = acc | aux (x::xs) acc = aux xs (x::acc) in aux xs [] end `

The accumulating argument similarly isn't needed in the interface to `mapmap`

, so it can be hidden in an inner helper function. So a single function that performs explicit recursion on both the inner and the outer list is complicated by this explicit bookkeeping:

`fun mapmap f xss = let fun aux f [] _ = [] | aux f ([]::xss) ys = rev ys :: aux f xss [] | aux f ((x::xs)::xss) ys = aux f (xs::xss) (f x :: ys) in aux f xss [] end `