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)，而不是直接在函数参数中解构。出于某种奇怪的原因，这段代码可以处理无限长的列表。 如果有人知道为什么会这样，请告诉我。

- Prophet

Answer 1

Haskell中的let表达式是惰性求值的:

Let表达式

(...) 模式绑定是惰性匹配的；一个隐式的 ~ 使这些模式无法拒绝。

相比之下，lambda抽象将desugar到case，从而使构造器模式成为严格匹配:

Curried应用和lambda抽象

翻译：以下等式成立:

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

- Li-yao Xia

---

...而且你可以使用暗示的~来显式地延迟lambda的模式，并获得两个世界的最佳效果（在无限列表上让let表现良好，lambda的美学更好）。\cur ~(acc, xs) -> if ... - Daniel Wagner

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)

由于Haskell是惰性的，use函数不会立即强制求值第二个参数t。只有当use实际需要其第二个或第三个参数时，才会触发对t的求值。

等效地，我们可以这样写：

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

同样地，使用一种懒惰/不可反驳的匹配模式来延迟第二个参数的解构。当使用let和where时，(顶层)模式会隐式地变为懒惰模式，因此我们也可以这样写：

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

- chi