haskell - 无法理解 Haskell 中 `foldr` 和 `map` 的行为

Question

我有一个函数 prefixes，给定 [1, 2, 3]，返回前缀 [[1], [1, 2]， [1, 2, 3]]。定义如下:

prefixes :: Num a => [a] -> [[a]]
prefixes = foldr (\x acc -> [x] : (map ((:) x) acc)) []

我花了将近两天的时间试图理解为什么会这样。当我在脑海中调试它时，我想象这是对于 prefixes [1, 2, 3]:

foldr call|__________________________________________________________________________
    1     | [1] : (map ((:) 1) [])
          |
          |         where x = 1 and acc = []
          |         returns acc = [[1]]
          |
    2     | [2] : (map ((:) 2) [[1]])
          |
          |         where x = 2 and acc = [[1]]
          |         and (map ((:) 2) [[1]])
          |                  returns acc = [[1, 2]]
          |         and [2] : [[1, 2]]
          |                  returns [[2], [1, 2]]
          |
    3     | [3] : (map ((:) 3) [[2], [1, 2]])
          |
          |         where x = 3 and acc = [[2], [1, 2]]
          |         and (map ((:) 3) [[2], [1, 2]])
          |                  returns acc = [[2, 3], [1, 2, 3]]
          |         and [3] : [[2, 3], [1, 2, 3]]
          |                  returns [[3], [2, 3], [1, 2, 3]]
          |

然后函数终止并返回 [[3], [2, 3], [1, 2, 3]]。但显然这不会发生。它返回 [[1], [1, 2], [1, 2, 3]]。

在 Ghci 中，我发现了这个:

Stopped in Main.prefixes, ex.hs:21:20-63

_result :: [a] -> [[a]] = _
[ex.hs:21:20-63] *Main> :step

Stopped in Main.prefixes, ex.hs:21:37-59

_result :: [[Integer]] = _
acc :: [[Integer]] = _
x :: Integer = 1

[ex.hs:21:37-59] *Main> :step

[[1]

Stopped in Main.prefixes, ex.hs:21:44-58

_result :: [[Integer]] = _
acc :: [[Integer]] = _
x :: Integer = 1

[ex.hs:21:44-58] *Main> :step
Stopped in Main.prefixes, ex.hs:21:37-59

_result :: [[Integer]] = _
acc :: [[Integer]] = _
x :: Integer = 2

[ex.hs:21:37-59] *Main> :step
,
Stopped in Main.prefixes, ex.hs:21:49-53

_result :: [Integer] -> [Integer] = _
x :: Integer = 1

[ex.hs:21:49-53] *Main> :step
[1,2]
Stopped in Main.prefixes, ex.hs:21:44-58

_result :: [[Integer]] = _
acc :: [[Integer]] = _
x :: Integer = 2

[ex.hs:21:44-58] *Main> :step
Stopped in Main.prefixes, ex.hs:21:37-59

_result :: [[Integer]] = _
acc :: [[Integer]] = _
x :: Integer = 3

[ex.hs:21:37-59] *Main> :step
,
[1Stopped in Main.prefixes, ex.hs:21:49-53

_result :: [Integer] -> [Integer] = _
x :: Integer = 2

[ex.hs:21:49-53] *Main> :step
,2,3]
Stopped in Main.prefixes, ex.hs:21:44-58

_result :: [[Integer]] = _
acc :: [[Integer]] = _
x :: Integer = 3

[ex.hs:21:44-58] *Main> :step

]

我的解释是:

__lines___|__________________________________________________________________________
 21:37-59 | [1] : (map ((:) 1) acc)           ->  [[1]
          |        
          |              
          |
 21:44-58 |       (map ((:) 1) acc)           ->  does nothing, as acc = []
          |                                                 
          |              
          |
 21:37-59 | [2] : (map ((:) 2) acc)           ->  ,
          |         
          |              
          |
 21:49-53 |            ((:) 1)                ->  [1, 2]
          |            
          |                 
          |
 21:44-58 |       (map ((:) 2) acc)           ->  outputs nothing
          |         
          |              
          |
 21:37-59 | [3] : (map ((:) 3) acc)           ->  ,[1
          |         
          |              
          |
 21:49-53 |            ((:) 2)                ->  , 2, 3]
          |             
          |
 21:44-58 |       (map ((:) 3) acc)           ->  ]
          |

正在打印 [[1], [1, 2], [1, 2, 3]]。有人可以解释为什么在评估第 49-53 行时，x 是之前 foldr 调用的 x 值吗？

我知道 (map ((:) x) acc) 可以扩展为 (foldr ((:) . ((:) x)) [] acc)，如 map f = foldr ((:) . f) []。所以我把函数重写成如下

prefixesSolution :: Num a => [a] -> [[a]]
prefixesSolution = foldr (\x acc -> [x] : (foldr ((:) . ((:) x)) [] acc)) []

这也行得通。现在，lambda 传递给第二个 foldr ((:) . ((:) x)) 我想可以重构为 (\element accumulator -> (元素:累加器) . ((元素:累加器) x)).但这不起作用:Couldn't match expected type ‘a -> a0 -> b0’ with actual type ‘[[a]]’。我所做的所有这些都是为了准确指出正在发生的事情。

我也不明白传递给 map ((:) x) 的函数。

对于这篇文章的复杂性，我深表歉意。在这一点上，我什至不知道我不知道什么。如果有人能清楚地引导我完成这个功能，我将非常感激。

Answer 1

foldr 从列表末尾开始累积。

最初 acc = [](使用 foldr 的第二个参数)。

从最后开始，我们应用给定函数 \x acc -> [x] : (map ((:) x) acc) with x = 3 :

[3] : map (3 :) []
= [[3]]

使用 acc = [[3]]，添加前面的元素，x = 2:

[2] : map (2 :) [[3]]
= [[2], [2,3]]

使用 acc = [[2], [2,3]]，添加前面的元素，x = 1:

[1] : map (1 :) [[2], [2,3]]
= [[1], [1,2], [1,2,3]]

您仍然可以“从左到右”计算 foldr，但在那种情况下，请记住 acc 是用“下一个递归调用”实例化的。

foldr f b (x : xs) = f x (foldr f b xs)

prefixes [1,2,3]
= [1] : map (1 :) (prefixes [2,3])    -- acc = prefixes [2,3], the next recursive call
= [1] : map (1 :) ([2] : map (2 :) (prefixes [3]))
...