Haskell自引用图数据结构相关技术问题咨询

你提供的代码如下：

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

针对你的三个问题解答如下：

1. 这段代码会创建多少个Node实例？
   总共会创建3个Node实例。因为refs包含3个NodeRef，allNodes = map deref' refs会调用三次deref'，每次生成一个Node。得益于Haskell的惰性求值，这三个Node会互相引用形成循环，但不会重复创建，整个结构里只有这三个实例。

2. 运行showme函数时，每一步是否会生成新的Node？
   不会。showme只是对已有的Node结构进行遍历和模式匹配，每次取出name和target（target是已经存在的Node引用），全程不会创建新的Node实例。Haskell的纯函数特性保证数据不可变，showme作为纯函数只做读取和组合操作。

3. 构建带有循环引用的数据结构的正确方式是什么？
   在Haskell里构建循环引用有几种常用的正确方式：

• 惰性递归绑定：直接在let或where块里定义互相引用的值，比如：

  let zero = Node "Zero" one
      one = Node "One" two
      two = Node "Two" zero
  in zero
  

  这种方式利用Haskell的惰性求值，无需借助索引就能直接创建循环结构。
• 使用fix函数：fix函数可以创建自递归的值，适合单节点自循环的场景，比如：

  import Data.Function (fix)
  selfLoop = fix (\node -> Node "Self" node)
  

• 可变引用（IORef/STRef）：如果需要在IO或ST monad中动态构建或修改循环结构，可以用可变引用，比如：

  import Data.IORef
  makeLoop :: IO Node
  makeLoop = do
      zeroRef <- newIORef undefined
      oneRef <- newIORef undefined
      twoRef <- newIORef undefined
      writeIORef zeroRef (Node "Zero" =<< readIORef oneRef)
      writeIORef oneRef (Node "One" =<< readIORef twoRef)
      writeIORef twoRef (Node "Two" =<< readIORef zeroRef)
      readIORef zeroRef
  

  这种方式适合需要动态调整结构的场景，纯函数场景下更推荐前两种惰性绑定的方式。

内容的提问来源于stack exchange，提问作者Chirmol Studio