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

Question

我给自己设定了以下挑战（但失败了）：

我想写一个函数式映射 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

Answer 2

另一种方式：

let rec mapNested f lofls =
    match lofls with
    | []   -> []
    | h::t -> (map f h) :: (mapNested f t)
and map f lst = 
    match lst with
    | []   -> []
    | h::t -> (f h) :: (map f t)

Answer 3

一种尾递归方式

let mapNested f lofls =
    let rec map f lst acc =
        match lst with
        | []   -> List.rev acc
        | h::t -> map f t (f h :: acc)
    map (fun x -> map f x []) lofls []

Answer 4

如果这是一道家庭作业题（我相信这不是），答案取决于 "a nested map for lists".

的构成

像 map [] (map [] f) 这样的构造可以用流水线重写为 f |> map [] |> map []，或者用函数组合运算符重写为 (map [] >> map []) f，但仍可能被视为嵌套映射。

let mapNested f =
    let rec map acc g = function
    | [] -> List.rev acc
    | x::xs -> map (g x::acc) g xs
    f |> map [] |> map [] 
// val mapNested : f:('a -> 'b) -> ('a list list -> 'b list list)

这是展示您对 lambda 演算和 Y combinator 的掌握的机会。 map 函数作为参数的嵌套传递应该清楚地通过集合。

let rec Y f x = f (Y f) x

let map f acc g = function
| [] -> List.rev acc
| x::xs -> f (g x::acc) g xs

let map1 f =
    Y map [] f
// val map1 : f:('a -> 'b) -> ('a list -> 'b list)

let map2 f =
    Y map [] f
    |> Y map []
// val map2 : f:('a -> 'b) -> ('a list list -> 'b list list)

Answer 5

我不确定为什么这个问题被标记为 SML，但既然如此，下面是如何在 SML 中完成的：

首先，这是您明确要避免的惯用解决方案：

fun mapmap f = map (map f)

（如果不是ML的value restriction，你可以写val mapmap = map o map。）

如果您想使用显式递归编写 mapmap：

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

很难用一个显式递归函数编写此函数的一个原因是调用堆栈用于两件事：

收集每个内部列表的结果，并且
正在收集外部列表的结果。

调用堆栈的其中一种用途可以在累积参数中转换为显式堆栈。这就是例如定义了尾递归 rev：

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

mapmap 的接口中同样不需要累加参数，因此它可以隐藏在内部辅助函数中。因此，在内部和外部列表上执行显式递归的单个函数因这种显式簿记而变得复杂：

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

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

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

f#

functional-programming

sml

编辑