Haskell 无限列表上的元组解构在将元组作为参数解构时与使用 let 解构时的行为不同

Question

在尝试使用 foldr 实现 dropWhile 时，我想出的第一个算法是这个

dropWhile' :: (a -> Bool) -> [a] -> [a]
dropWhile' pred = fst . foldr (\cur (acc, xs) ->
    if pred cur
    then (acc, cur:xs)
    else (cur:xs, cur:xs)) ([], [])

虽然这行得通，但它会在不提供任何值的情况下导致无限列表发生堆栈溢出。因为我不确定，为什么这行不通，所以我一直在玩这个函数，直到我想出这个：

dropWhile' :: (a -> Bool) -> [a] -> [a]
dropWhile' pred = fst . foldr (\cur t -> let (acc, xs) = t in
    if pred cur
    then (acc, cur:xs)
    else (cur:xs, cur:xs)) ([], [])

如您所见，这一个与第一个之间的唯一区别是，我在这里解构 let 绑定中的元组 (acc, xs)，而不是直接在函数参数内部解构。出于某种奇怪的原因，此代码适用于无限列表。如果有人知道为什么会这样，请告诉我。

Answer 1

让 Haskell 中的表达式是惰性的：

Let Expressions

(...) Pattern bindings are matched lazily; an implicit ~ makes these patterns irrefutable.

相比之下，lambda 抽象脱糖为 case，从而使构造函数模式变得严格：

Curried applications and lambda abstractions

Translation: The following identity holds:

\ p1 … pn -> e = \ x1 … xn -> case (x1, …, xn) of (p1, …, pn) -> e

Answer 2

粗略地说，

\cur (acc, xs) -> use cur acc xs

在计算 use ... 之前强制立即计算第二个参数。在 foldr 中，这会在执行任何其他操作之前处理列表的尾部。如果列表是无限的，我们将陷入无限递归。

同样适用于

\cur t -> case t of (acc, xs) -> use cur acc xs

相反，

\cur t -> use cur (fst t) (snd t)

不会立即强制计算第二个参数 t，因为 Haskell 是惰性的。只有当 use 实际上需要它的第二个或第三个参数时， t 的计算才会触发。

等价地，我们可以写

\cur t -> case t of ~(acc, xs) -> use cur acc xs
-- or
\cur ~(acc, xs) -> use cur acc xs

同样的效果，使用 lazy/irrefutable 模式来延迟第二个参数的解构。当使用 let 和 where 时，（顶级）模式是隐式惰性的，所以我们也可以写

\cur t -> let (acc, xs) = t in use cur acc xs

Haskell 无限列表上的元组解构在将元组作为参数解构时与使用 let 解构时的行为不同

Haskell Tuple destructuring on infinite lists behaves differently when destructuring the Tuple as an argument than when destructuring using let

haskell

tuples

list

destructuring

lazy-evaluation

Let Expressions

Curried applications and lambda abstractions