Implement a map functional for a list of lists without using nested maps

Question

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)

Answer 1

Lets go step by step, from simple to complex.

This is the signature that you want your map function to have:

('a -> 'b) -> 'a list list -> 'b list list

The simple solution is this:

let map0 (f:'a -> 'b) (lofls:'a list list) : 'b list list = lofls |> List.map (List.map f)

But that one is not recursive and it uses nested maps.

A recursive solution could be this:

let rec map1 (f:'a -> 'b) (lofls:'a list list) : 'b list list =
    match lofls with
    | []      -> []
    | l::rest -> (List.map f l) :: map1 f rest

It is recursive although it is still calling List.map in there.

So, here is the next level:

let rec map (f:'a -> 'b) (lofls:'a list list) : 'b list list =
    match  lofls                    with
    | [          ]         -> [              ]
    | [          ] :: rest -> [              ] :: (rest |> map f)
    | ( e::restl ) :: rest -> 
    match  restl   :: rest |> map f with
    | [          ]         -> [              ]
    | [          ] :: rest -> [ f e          ] ::  rest
    | (    restl ) :: rest -> ( f e :: restl ) ::  rest