Haskell中这个循环链表上的"绑结"如何工作？

Question

我正在学习Haskell,正在阅读Tying the Knot关于如何构建循环链表.在代码中

data DList a = DLNode (DList a) a (DList a)
mkDList :: [a] -> DList a
mkDList [] = error "must have at least one element"
mkDList xs = let (first,last) = go last xs first
         in  first
         where go :: DList a -> [a] -> DList a -> (DList a, DList a)
               go prev []     next = (next,prev)
               go prev (x:xs) next = let this        = DLNode prev x rest
                                         (rest,last) = go this xs next
                                     in  (this,last)

我试图通过一个叫做结的"小技巧"(!)来理解他们将最后一个元素链接到第一个元素的调用:

mkDList xs = let (first,last) = go last xs first

但我很难看到它是如何工作的.什么是"go"最初被称为？根据文章中的评论,"go""传回"的第一个结果如何？

谢谢!

Answer 1

由于 Haskell 是惰性的，所以直到绝对必要时才会评估值。我们可以使用等式推理来演练一个简单的例子，看看这会给我们带来什么。

从最简单的示例开始：单元素列表。

mkDList [1] == let (first, last) = go last [1] first in first

看来你不能打电话go，因为你还不知道last和first等于什么。但是，您可以将它们视为未评估的黑匣子：它们是什么并不重要，只要您可以使用它们进行等式推理即可。

-- Just plug last and first into the definition of go
-- last2 is just a renaming of the argument for clarity
go last [1] first == let this = DLNode last 1 rest
                         (rest, last2) = go this [] first
                     in (this, last2)

go让我们尝试以相同的方式评估下一次调用。

go this [] first == (first, this)

方便的是，我们不需要想象任何新的黑匣子；我们不需要想象任何新的黑匣子。go只是以稍微重新包装的方式评估其原始参数。

好的，现在我们可以回到原来的方式，并用go它的评估替换递归调用。

go last [1] first == let this = DLNode last 1 rest
                         (rest, last2) = (first, this)
                     in (this, last2)

我们将把它代入我们原来的方程mkDList：

mkDList [1] == let (first, last) = let this = DLNode last 1 rest
                                       (rest, last2) = (first, this)
                                   in (this, last2)
               in first

这看起来不太有帮助，但请记住，我们实际上还没有打电话 mkDList；我们只是使用等式推理来稍微简化它的定义。特别是，没有对 的递归调用go，只有一个let表达式嵌套在另一个表达式中。

由于 Haskell 是懒惰的，所以除非绝对必要，否则我们不必评估任何这些，例如当我们尝试对返回值进行模式匹配时mkDlist [1]：

let (DLNode p x n) = mkDList [1] in x

为了评估这个表达式，我们只需要问以下问题：

1. “有什么价值x？” 答案：我们需要首先进行模式匹配mkDList [1]。
2. “有什么价值mkDList？” 回答：first。
3. “有什么价值first？” 回答：this。
4. “有什么价值this？” 回答：DLNode last 1 rest

此时，您已经有足够的信息来查看 和x == 1，last并且rest不需要进一步评估。不过，您可以再次进行模式匹配以查看例如p是什么，并发现

p == last == last2 == this == DLNode last 1 rest

和

n == rest == first == this == DLNode last 1 rest

神奇的是，像这样的调用实际上不需要(first, last) = go last xs first其参数的值；它只需要占位符来跟踪什么值以及在评估时最终会得到什么值。这些占位符称为“thunk”，它们代表未评估的代码片段。他们让我们参考尚未装满任何东西的盒子，我们可以将空盒子传递到保险箱，因为我们知道有人会在其他人试图查看它们之前将它们装满。（事实上​​，它本身从来不会这样做；它只是不断地传递它们，直到外面有人试图查看它们。）firstlastgogomkDList