带引用的 Haskell 数据类型

Haskell Data Type With References

提问人:Craig 提问时间:10/15/2013 最后编辑:dfeuerCraig 更新时间:12/28/2014 访问量:861

问:

我正在实现 Ukkonen 的算法,该算法要求树的所有叶子都包含对同一整数的引用,我正在 Haskell 中这样做以了解有关该语言的更多信息。但是,我很难写出执行此操作的数据类型。

-- Node has children, indexes of info on the edge
-- to it, and an optional suffix link.

-- Leaf has a beginning index of the info, but the
-- end index is always an incrementing variable index.
data STree = Node [STree] (Int, Int) (Maybe STree)
           | Leaf (Int, ??? )

如何将引用放在类型声明中?Leaf

哈斯克尔 参考 可变 后缀树 状态单子

评论

0赞 luqui 10/15/2013
请参阅 Data.IORef
0赞 Craig 10/15/2013
谢谢!我正在查看 ST ref,但不知道如何处理类型中的 s
1赞 J. Abrahamson 10/15/2013
仍然是抽象的,你只要忽略它,它就会被消耗掉。它存在的原因是防止您在 之外查看 ST 内部计算。srunSTrunST
2赞 luqui 10/15/2013
@user2876621,这将是.这是使用可变引用进行算法的更“道德”的方式,但如果你迷路了,在你开始时使用并没有什么坏处。data STree s = Node [STree s] (Int, Int) (Maybe (STree s)) | Leaf (Int, STRef s Int)IORef
1赞 dfeuer 12/28/2014
@leftaroundabout,zbh.uni-hamburg.de/pubs/pdf/GieKur1995a.pdf 似乎相当深入地研究了纯函数式(和其他)后缀树算法。他们似乎认为不可能实现线性时间构建,但显然他们的(渐近低效)算法由于局部性而实现了良好的实际性能。hackage.haskell.org/package/suffixtree-0.2.2.1/docs/......似乎是基于此。

答: 暂无答案