list - 我们可以将不可变列表视为树的对偶吗？

Question

我可能会绘制一个单词列表，例如：

this -> is -> a -> test

然后通过分享，我可能会画出两个列表：

this -> is -> a -> test
                     ^
                     |
that -> was -> a -> hard

现在，如果我反转箭头，我会得到一棵树，以 test 为根。这与图/类别理论中的对偶概念相同。因此，我可以将树和列表视为双重概念。

这是正确/有用的吗？

Answer 1

共享和懒惰允许你拥有任意的循环结构。例如，在 Haskell 中，定义

ones = 1 : ones

生成一个由单个顶点（对应于 1）和一个循环（在图论中，而不是编程意义上）组成的图。通过反转箭头，你会得到相同的结构，而且它不是一棵树（因为它有循环）。

所以，这在惰性语言中是不正确的。