树结构中的连接

Question

现在使用长字符串时，我在Haskell中创建后缀树时遇到了一个相当大的问题。

一些构造算法(作为Ukkonen算法的这版本)需要在节点之间建立链接。这些链接“指向”树中的一个节点。在命令式语言(如Java、C#等)中，由于引用类型，这是没有问题的。

在Haskell有什么方法来模仿这种行为吗？还是有一种完全不同的选择？

Answer 1

您可以在打结递归结计算中的数据构造中使用直到计算结果才确定的值。

下面的计算构建了一个值列表，每个值都包含列表中的项目总数，即使总数是由构建列表的相同函数计算的。let绑定在zipCount中将zipWithAndCount的一个结果作为第一个参数传递给zipWithAndCount。

zipCount :: [a] -> [(a, Int)]
zipCount xs = 
    let (count, zipped) = zipWithAndCount count xs
    in zipped

zipWithAndCount :: Num n => b -> [a] -> (n, [(a, b)])
zipWithAndCount y [] = (0, [])
zipWithAndCount y (x:xs) =
    let (count', zipped') = zipWithAndCount y xs
    in (count' + 1, (x, y):zipped')

运行此示例将生成一个列表，其中每个项目都包含列表中总项的计数。

> zipCount ['a'..'e']
[('a',5),('b',5),('c',5),('d',5),('e',5)]

这个想法可以通过传入直到知道整个结果才知道的Ukkonen算法来应用到#。

递归地将结果传递给函数的一般思想称为最小不动点，并在Data.Function中通过

fix :: (a -> a) -> a
fix f = let x = f x in x

我们可以用zipWithAndCount和fix的方式以无点数的方式编写zipWithAndCount.

import Data.Function

zipCount :: [a] -> [(a, Int)]
zipCount = snd . fix . (. fst) . flip zipWithAndCount