在不使用嵌套映射的情况下为列表列表实现映射功能

Question

我为自己设定了以下挑战(并且失败了):

我想编写一个map函数,map f lofls它接受一个函数,f 'a -> 'b和一个列表列表,lofls 'a list list并将这个函数应用于f列表列表的每个元素.我添加的约束是我不允许使用嵌套映射列表,我必须递归地执行它.

我尝试用F#来做,但任何语言都应该这样做.有任何想法吗？

编辑

这是我的尝试(虽然有效,但很难看,我也不喜欢使用rev ......)

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 []

(我也意识到这已经以更简洁的形式发布了)

Answer 1

让我们一步一步走,从简单到复杂.

这是您希望map函数具有的签名:

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

简单的解决方案是:

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

但那个不是递归的,它使用嵌套的地图.

递归解决方案可能是这样的:

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

这是递归的,虽然它仍然List.map在那里打电话.

那么,这是下一个级别:

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