使用map / reduce反转列表 [英] Reverse list using map/reduce

问题描述

我正在学习函数式编程的概念并尝试进行问题练习。
练习，
使用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 ）
  

输出：

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

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

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

 列表= [1，2，3，[5,6,7]，8，[9,0,1,4]] 
  

首先，我不太了解Python，但是当您将问题标记为函数式编程时，并且您表示您希望一般性地学习关于函数式编程，我想对你的问题给出一些一般的解释。
首先，您应该重新考虑 map 和 reduce 操作的做法以及他们的期望。让我们从 map 函数开始。

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

另一方面， reduce 函数需要一个函数，它接受两个相同类型的东西，并返回一个单一项属于同一类型。例如reduce函数可以采用+函数。 +是一个函数，它接受两个 int 并返回一个新的 int 。签名基本上是 int + int = int 。减少的本质是把两件事情变成一件新事物。例如，如果你的例子有类似Foo的更复杂的东西，那么你必须提供的函数减少需要签名 Foo * Foo - > FOO 。意思是以 Foo 作为第一个和第二个参数，并返回一个新的 Foo 。

重要的是要注意 reduce 将如何与该函数一起使用。让我们假设你有顶层 [1,2,3,4,5] 顶部让我们假设你有一个累加器函数，它将两个 int 加在一起。你能想到会发生什么是以下几点。

1. reduce 函数接受列表的前两个参数（1和2在这种情况下）
   
2. 将它们传递给累加器函数（1 + 2 = 3）
   
3. 并用结果替换列表中的两个参数。 [3,3,4,5]


4. 返回到1）并重复该过程，直到您的列表只有一个项目


5. 返回单件物品

所以你可以想象会发生什么如下所示：

  [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]  - >仅返回15。不是[15]
  

实际上，内部过程通常有点不同。但是这是你可以想象发生什么的过程。请务必注意，您从不修改列表。你总是在那个过程中创建新的列表。另一个重要说明。在 reduce 函数的末尾，您有一个单个项目的列表。但是 reduce 函数不会返回整个列表。它只返回单个元素。所以你得到 15 和 int 作为结果。您不会收到包含 15 的单个项目的列表。 Reduce将只返回那个单个元素。不管是什么。另一种思考方式。你总是得到你的累加器函数的类型。如果传递一个带有两个 int 的累加器函数，则添加它们并返回一个新的 int 。你的reduce函数也会返回一个 int 。如果你传递了一个累加器函数，并且返回一个新的 Foo code>。你的 reduce 函数也会返回一个 Foo 作为结果。 reduce 的返回类型总是与您的累加器函数的类型相同。

现在让我们把所有这些片段放在一起。目标是扭转一个列表。第一件重要的事情是。你的结果类型将是 list 。这也意味着你传递给 reduce 的函数也必须返回一个 list 。但是由于输入始终与输出相同。您现在必须提供一个累加器函数，它接受两个列表，并返回一个新列表。

但现在让我们退后一步。如果直接使用列表[1,2,3,4,5]作为输入来减少会发生什么？简单的答案是，它不会起作用。 reduce 将包含您的列表的两个参数。但是你有什么是int列表。但是你的累加器函数期望两个列表不是两个int。为了解决这个问题，你现在可以做的就是将列表中的每一个单元转换成它自己的列表。那么我们如何变换列表中的每一个元素呢？对！使用 map ！所以你必须做的是以下几点。您首先将您的列表映射到列表的列表中。

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

现在你的reduce函数获得第一个列表的前两个元素。这意味着你现在有一个累加器函数，它获取 [1] 和 [2] 作为它的参数。两个单独的名单。但是你的累加器函数必须返回一个新的列表。如果不清楚，只是提醒累加器函数需要返回什么。

  int，int  - > int 
 float，float  - > float 
 Foo，Foo  - > Foo 
列表，列表 - >列表
  

因此，您现在必须做的是将这两个列表合并成一个新列表。换句话说，你必须追加/连接这两个列表。我不知道你如何在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]]  - >返回第一个元素[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]]  - >返回第一个元素[5,4,3,2,1] 
  

现在你得到的是你的反向列表。所以你有什么待办事项

1. 将每个元素映射到一个列表。因此，您可以获得列表


2. 使用reduce将列表中的每个列表以相反的顺序排列到新列表中。

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

  let list = [1; 2; 3; 4; 5] 
 
让reverse = 
 list 
 |> List.map（fun x  - > [x]）//将每个元素映射到列表
 |> List.reduce（fun xs ys  - > List.append ys xs）// Note ys ++ xs  - 颠倒顺序以追加
 
 printfn％A颠倒
 //打印： [5; 4; 3; 2; 1] 
  

我认为您应该可以将其翻译为蟒蛇。作为进一步通知。在函数式编程中，做映射和concat操作（无反转）也称为绑定。

I am learning concepts of functional programming and trying out problem exercises. An exercise, Reverse a list using map/reduce. My solution:

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)

Output:

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

I don't understand why there are Nones equal to number of elements in list.

EDIT: Extending question for case of nested lists.

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

解决方案

At first, i don't know Python good enough, but as you marked the question as "functional-programming" and you stated you want to learn in general about functional programming i want to give some general explanation of your problem. At first, you should rethink what the map and reduce operation do and what they expect. Let's start with the map function.

A map function for a list (in functional programming you don't have only one map, you have one map for every generic type) executes a function on every single argument. That function can operate on that single argument and transform it. The result of this transformation is turned into a new list. One important note is that the function you pass to map only ever sees one element, so you cannot use map itself to transform a list as a whole. You only can transform every single element of a list. But changing the order needs the idea of having at least two elements of a list, and a map only ever gets a single element. This is the reason why the reverse logic cannot be in map and has to be part of the reduce operation.

The reduce function on the other hand expects a function that takes two things of the same type, and returns a single item of the same type. For example the reduce function could take the "+" function. "+" is a function that takes two int and returns a new int. The signature is basically int + int = int. The essence of reduce is to take two things and turn it into a single new item. If you for example had something more complex like a class "Foo", then the function you have to provide to reduce need to have the signature Foo * Foo -> Foo. Meaning take a Foo as first and second argument, and return a single new Foo.

It is also important to note how reduce will work with that function. Let's assume you have the List [1,2,3,4,5] on top let's assume you have an accumulator function that takes two int that just adds them together. What you can think of what will happen is the following.

1. The reduce function takes the first two arguments of your list (1 and 2 in this case)
2. Passes those to the accumulator function (1 + 2 = 3)
3. And replaces the two arguments in the list with the result. [3,3,4,5]
4. Go back to 1) and repeat that process until your List only have a single item
5. Return that single item

So what you can imagine what happens is the following

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

Actually the process internal usually works a little bit different. But this is the process you can imagine what happens. It is important to note that you never modify a list. You always create new lists in that process. Another important note. At the end of the reduce function you have a list of an single item. But the reduce function does not return the whole list. It returns just the single element. So you get 15 an int as a result. You don't get a list with a single item containing 15. Reduce will just return that single element. Whatever it is. One other way to think about it. You always get exactly the type back of your accumulator function. If you pass a accumulator function that takes two int adds them and returns a new int. Your reduce function will also return an int. If you pass an accumulator function that takes two Foo classes and returns a new Foo. Your reduce function will also return a Foo as its result. The return type of reduce is always the same as the types of your accumulator function.

Now let's take all those pieces and put them together. The goal is to reverse a list. The first important thing is. Your result type will be a list. That also means that the function you pass into reduce also have to return a list. But as the input are always the same as the output. You now have to provide a accumulator function that takes two lists, and returns a single new list.

But now let's step back. What happens if you use your list "[1,2,3,4,5]" directly as the input to reduce? The short answer is, it will not work. reduce will take two argument of your list. But what you have is a list of int. But your accumulator function expects two lists not two int. To solve that problem, what you now can do is try to convert every single element of the list into its own list. So how do we transform every single element of a list? Right! With map! So what you have to do is the following. You first map your list into a list of lists.

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

Now your reduce function gets the first two elements of your first list. It means you now have an accumulator function that gets [1] and [2] as its argument. Two separate lists. But your accumulator function has to return a single new list. If unclear, just remind what the accumulator function takes and return.

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

So what you now have to do is to combine those two lists into a single new list. Or in other words you have to append/concat those two lists. I don't knew exactly how you concat two lists in Python let's assume here the operation would be "++". So if you concat just the first argument and the second argument, you will not get what you want.

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

So what you have to do is to concat the second argument with the first one.

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

And now what you get is your reversed list. So what you have todo

1. map every element to a list. So you get a list of list
2. use reduce to concat every list of list into a new list in reversed order.

For example, in F# the whole code would look like this.

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]

I think you should be able to translate this to Python. As a further notice. Doing "map" and then a "concat" operation (without reversing) is also named "bind" in functional programming.

这篇关于使用map / reduce反转列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！