当我们尝试使用 foldr 附加两个列表时，为什么要切换列表顺序？

Question

我看到 post 解释了如何使用 foldr 添加两个列表。

但我不明白为什么我们必须切换列表的顺序。

append xs ys = foldr (\x y -> x:y) ys xs

第一步是

[y,x] (\x y -> x:y) foldr (\x y -> x:y) ys' xs'

我说的对吗？然后结果会把ys放在xs前面吗？

不应该吗

append xs ys = foldr (\x y -> x:y) xs ys

Answer 1

直觉是 foldr c n list "replaces" list 中的每个 : 和 c 以及最后的 [] 和 n.

要将 xs 附加到 ys，需要 "replace" xs 内的最终 [] 和 ys。相反 : 应替换为自身。

因此，我们得到 foldr (:) ys xs。

Answer 2

The first move would be
[y,x] (\x y -> x:y) foldr (\x y -> x:y) ys' xs'

这不是一个有效的 Haskell 表达式，但我认为你在这里的意思是你从每个列表中取出一个元素，然后以某种方式将它们插入前面。这不是 foldr 的工作方式——它不会遍历 z 参数的元素（在本例中为 ys）——事实上，该参数甚至不必是列表。

而是 foldr f z (x:xs') 展开如下：

x `f` foldr f z xs'

和 foldr f z [] 扩展为 z。

所以在你的情况下，第一步是：

x : foldr (\x y -> x:y) ys xs'

这将一直持续到我们到达空列表为止，在这种情况下，结果将是 ys。所以：

  foldr (\x y -> x:y) ys [x1, x2, ..., xn]
= x1 : foldr (\x y -> x:y) ys [x2, ..., xn]
= x1 : x2 : foldr (\x y -> x:y) ys [..., xn]
= ...
= x1 : x2 : ... : xn : foldr (\x y -> x:y) ys []
= x1 : x2 : ... : xn : ys

并且由此可以看出xs的元素放在了ys的前面。

Answer 3

第一步不会是那样。检查文件夹类型

    ghci>:t foldr
    foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b

为了简化起见，我们假设 t 为 []。在这种情况下，foldr 是：

给我一个函数 f，它接受一个 a 和一个 b 和 returns 一个 b。给我一个初始元素和一个 a 的列表。我会制作一个b。

因此，它的工作方式是：获取列表的最后一个元素并将 f 应用于该元素和生成 b 的初始值。获取列表的新的最后一个值并将 f 应用于该值和之前的结果...等等。

在你的例子中，初始元素实际上是一个列表，而且很乱。但是检查这个计算。请记住 [1,2,3] 用作初始值，因此我们不会 "loop" 超过它

    foldr (\x y -> x:y) [1,2,3] [4,5,6]
    foldr (\x y -> x:y) 6:[1,2,3] [4,5]
    foldr (\x y -> x:y) 5:6:[1,2,3] [4]
    foldr (\x y -> x:y) 4:5:6:[1,2,3] []

希望对您有所帮助！

当我们尝试使用 foldr 附加两个列表时，为什么要切换列表顺序？

Why switch the lists order when we try to append two lists by using foldr?

haskell

fold