我试图建立一个图表的数据结构。
下面的代码看起来像预期的那样工作：
data NodeRef = NodeRef String Int -- NodeRef name targetIndex
data Node = Node String Node -- Node name targetNode
ref0 = NodeRef "Zero" 1
ref1 = NodeRef "One" 2
ref2 = NodeRef "Two" 0
refs = [ref0, ref1, ref2]
deref :: [NodeRef] -> Node
deref refs = head allNodes
where
deref' (NodeRef name targetIndex) = Node name (allNodes !! targetIndex)
allNodes = map deref' refs
showme :: Node -> Int -> [String]
showme _ 0 = []
showme (Node name target) count = name : showme target (count - 1)
main :: IO()
main = print $ showme (deref refs) 100不过，我有几个问题：
创建了多少个Node“示例”？
当我运行“showme”时，我是否在每一步都创建了更多的节点？
构建具有循环引用的数据结构的正确方法是什么？
非常感谢你的回答。
1条答案
按热度按时间tv6aics11#
创建了多少个Node“示例”？
一般来说，当你写一个数据构造函数，如
NodeRef或Node，这表示一个计算，将分配这样一个值-cf。new Node(…)在典型的命令式/OOP语言中。当你用let或where写一个变量绑定时，再次提到这个名字将引用相同的值。顶级绑定，或者不依赖于任何参数的
where绑定，也被称为“常量应用形式”（CAF）。因此，ref0、ref1、ref2和refs都是CAF，任何提到例如ref0将引用相同的NodeRef值。在每次调用
deref时，它分配一个列表allNodes，该列表包含的Node值与输入列表refs中的NodeRef值一样多-在本例中为3个。表达式allNodes !! targetIndex指的是同一个共享allNodes列表的索引。最后，由于
deref返回head allNodes，只有那些实际连接到头节点的节点才能保持可达，其他节点将被垃圾收集。当我运行“showme”时，我是否在每一步都创建了更多的节点？
showme分配一个列表“cons”单元格的数量(:)，该数量等于count参数。或者，如果count为负，它将继续递减，直到环绕Int的范围并返回到0-您可以使用<=的保护，或者pred而不是- 1来使用检查的递减。它不复制节点本身，只操作对它们（及其字段）的引用。构建具有循环引用的数据结构的正确方法是什么？
你的方法在这里是正确的。如果你想使用这些循环数据结构，在遍历它们时，你需要小心不要使用天真的无界递归，以避免不终止。您也无法在不失去共享的情况下轻松地更改此数据结构（即，构建其修改版本）。因此，通常只使用
NodeRef中基于ID的表示，这是“可观察共享”的一个示例，存储在父结构（如IntMap）中。如果您想“冻结”表示，可以移动到Node。打结更常被用作一种方便，以避免在命令式语言中使用的显式变化和手动排序。只要这个数据结构不是循环的，那么你就可以写一个完整的数据结构的定义，然后让普通的惰性计算过程来填充它。