使用 map/reduce 反转列表

Question

我正在学习函数式编程的概念并尝试问题练习。练习，使用 map/reduce 反转列表。我的解决方案：

lists = [ 1, 2, 3, 5 ,6]

def tree_reverse(lists):
    return reduce(lambda a, x: a + [a.insert(0,x)], lists, [])

print tree_reverse(lists)

输出：

[6, 5, 3, 2, 1, None, None, None, None, None]

我不明白为什么列表中的元素数量等于无。

编辑：针对嵌套列表的情况扩展问题。

 lists = [ 1 ,2 ,3 , [5,6,7], 8, [9, 0, 1 ,4 ]]

Answer 1

您的归约操作将 None 附加到列表 a 的末尾，因为 a.insert(0,x) 将 return None.

因此您正在就地修改列表 a，但同时附加了一个 None 值。

如果您重写 reduce 操作以使用 for 循环，它看起来像：

def reverse_list(lists):
    r = []
    for x in lists:
        val = r.insert(0,x)
        r = r + [val]  # val (the return value of r.insert) is None
    return r

Answer 2

在嵌套列表的情况下。我发布答案以供参考。

lists = [ 1 ,2 ,3 , [5,6,7], 8, [9, 0, 1 ,4 ]]

def tree_reverse(lists):
    return  reduce(lambda a, x: ( map(tree_reverse, [x]) if isinstance(x,list) else [x] ) + a  , lists , [] )

print tree_reverse(lists)

输出：

[[4, 1, 0, 9], 8, [7, 6, 5], 3, 2, 1]

Answer 3

起初，我不知道 Python 够好，但是当你将问题标记为 "functional-programming" 并且你说你想学习函数式编程的一般知识时，我想给一些你的问题的一般解释。首先，您应该重新考虑 map 和 reduce 操作的作用以及它们的期望。让我们从 map 函数开始。

列表的map 函数（在函数式编程中，您不仅有一个映射，每个泛型类型都有一个映射）对每个参数执行一个函数。该函数可以对单个参数进行操作并对其进行转换。这种转换的结果变成了一个新列表。一个重要的注意事项是您传递给 map 的函数只能看到一个元素，因此您不能使用 map 本身来转换整个列表。您只能转换列表中的每个元素。但是改变顺序需要至少有两个列表元素的想法，而地图只会有一个元素。这就是为什么反向逻辑不能在 map 中并且必须是 reduce 操作的一部分的原因。

另一方面，reduce 函数需要一个接受两个相同类型的东西的函数，并且 returns 一个相同类型的项目。例如，reduce 函数可以采用“+”函数。 “+”是一个函数，需要两个 int 和 return 一个新的 int。签名基本上是int + int = int。 reduce 的本质是取两个东西并将其变成一个新的项目。例如，如果你有更复杂的东西，比如 class "Foo"，那么你必须提供的函数 reduce 需要有签名 Foo * Foo -> Foo。意思是将 Foo 作为第一个和第二个参数，return 一个新的 Foo.

注意 reduce 如何使用该函数也很重要。假设您的列表 [1,2,3,4,5] 位于顶部让我们假设您有一个 accumulator function 需要两个 int 将它们相加。你能想到的会发生以下情况。

reduce 函数采用列表的前两个参数（在本例中为 1 和 2）
将这些传递给 accumulator function (1 + 2 = 3)
并用结果替换列表中的两个参数。 [3,3,4,5]
返回 1) 并重复该过程，直到您的列表只有一个项目
Return那个单品

所以你可以想象会发生以下情况

[1,2,3,4,5] -> 1 + 2 = 3
[3,3,4,5]   -> 3 + 3 = 6
[6,4,5]     -> 6 + 4 = 10
[10,5]      -> 10 + 5 = 15
[15]        -> Return just "15". Not a "[15]"

实际上，内部流程通常会有些不同。但是这个过程你可以想象会发生什么。请务必注意，您永远不会修改列表。您总是在该过程中创建新列表。另一个重要说明。在 reduce 函数的末尾，您有一个包含单个项目的列表。但是 reduce 函数不会 return 整个列表。它 return 只是单个元素。所以你得到 15 和 int 作为结果。您不会获得包含 15 的单个项目的列表。 Reduce 只会 return 那个单个元素。不管是什么。另一种思考方式。您总是会得到 accumulator function 的准确类型。如果你传递一个 accumulator function 需要两个 int 添加它们并且 returns 一个新的 int。您的 reduce 函数还将 return 和 int。如果你传递一个 accumulator function 需要两个 Foo class 和 return 一个新的 Foo。您的 reduce 函数也将 return 一个 Foo 作为其结果。 reduce 的 return 类型始终与 accumulator function 的类型相同。

现在让我们把所有这些碎片放在一起。目标是反转列表。第一个重要的是。您的结果类型将是 list。这也意味着您传递给 reduce 的函数也必须 return 一个 list。但是因为输入总是与输出相同。您现在必须提供一个包含两个列表的 accumulator function，并且 return 是一个新列表。

但现在让我们退后一步。如果直接使用列表“[1,2,3,4,5]”作为减少的输入会发生什么？简短的回答是，它不会起作用。 reduce 将采用列表中的两个参数。但是你拥有的是一个 int 列表。但是您的 accumulator function 需要两个列表而不是两个 int。要解决这个问题，您现在可以做的是尝试将列表中的每个元素都转换成它自己的列表。那么我们如何转换列表中的每个元素呢？正确的！用map！所以你要做的是以下几点。您首先将列表映射到列表列表中。

[1,2,3,4,5] -> [[1],[2],[3],[4],[5]]

现在您的 reduce 函数获取第一个列表的前两个元素。这意味着您现在有一个累加器函数，它获取 [1] 和 [2] 作为其参数。两个单独的列表。但是您的累加器函数必须 return 一个新列表。如果不清楚，就提醒一下累加器函数取什么和return.

int, int    -> int
float,float -> float
Foo,Foo     -> Foo
list,list   -> list

所以您现在要做的是将这两个列表合并为一个新列表。或者换句话说，您必须 append/concat 这两个列表。我不知道你是如何在 Python 中连接两个列表的，让我们假设这里的操作是“++”。所以如果你只连接第一个参数和第二个参数，你将得不到你想要的。

[[1],[2],[3],[4],[5]] -> [1]       ++ [2] = [1,2]
[[1,2],[3],[4],[5]]   -> [1,2]     ++ [3] = [1,2,3]
[[1,2,3],[4],[5]]     -> [1,2,3]   ++ [4] = [1,2,3,4]
[[1,2,3,4],[5]]       -> [1,2,3,4] ++ [5] = [1,2,3,4,5]
[[1,2,3,4,5]]         -> Return first element [1,2,3,4,5]

所以你要做的是将第二个参数与第一个参数连接起来。

[[1],[2],[3],[4],[5]] -> [2] ++ [1]       = [2,1]
[[2,1],[3],[4],[5]]   -> [3] ++ [2,1]     = [3,2,1]
[[3,2,1],[4],[5]]     -> [4] ++ [3,2,1]   = [4,3,2,1]
[[4,3,2,1],[5]]       -> [5] ++ [4,3,2,1] = [5,4,3,2,1]
[[5,4,3,2,1]]         -> Return first element [5,4,3,2,1]

现在你得到的是你的反向列表。所以你必须做的

将每个元素映射到一个列表。所以你得到一个list
使用 reduce 以相反的顺序将列表的每个列表连接到一个新列表中。

例如，在 F# 中，整个代码如下所示。

let list = [1;2;3;4;5]

let reversed =
    list
    |> List.map    (fun x -> [x]) // map every element to a list
    |> List.reduce (fun xs ys -> List.append ys xs) // Note ys ++ xs - reversed order for appending

printfn "%A" reversed
// prints: [5;4;3;2;1]

我认为您应该能够将其翻译成 Python。作为另行通知。做"map"然后"concat"操作（不反转）在函数式编程中也被命名为"bind"。

Answer 4

函数式编程语言通常会使用递归来实现迭代。

递归 tree_reverse 函数可能看起来像

def tree_reverse(lists):
    return tree_reverse(lists[1:]) + [lists[0]] if lists else []

如果你看一下 Haskell 它可能是这样实现的

reverse' :: [a] -> [a]  
reverse' [] = []  
reverse' (x:xs) = reverse' xs ++ [x]

其中 x 是列表的头部（第一个元素），xs 是尾部（列表减去头部），你可以看到 reverse' 被调用递归地反转这些元素并迭代构建反转列表。

使用 map/reduce 反转列表

Reverse list using map/reduce

python

reduce

dictionary

functional-programming