haskell - Haskell 中这个循环链表上的 "tying the knot"是如何工作的？

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

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

“x 的值是多少？”答:我们需要对 mkDList [1] 进行模式匹配。第一的。

“mkDList 的值是多少？”答:first .

“first 的值是多少？”答:this .

“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 这样的电话它的参数实际上不需要值；它只需要占位符来跟踪什么值 first和 last当他们被评估时，最终会得到。这些占位符称为“thunk”，它们代表未评估的代码片段。他们让我们引用尚未填充任何内容的框，我们可以将空框传递给 go安全地知道有人会在其他人试图查看它们之前填充它们。 (事实上​​， go 本身从不这样做；它只是不断地传递它们，直到 mkDList 之外的人试图查看它们。)