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

  • 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?


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:

  1. Collecting the result of each inner list, and
  2. 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 


:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: