现在,在处理长字符串时,我在Haskell中创建后缀树时遇到了一个相当大的问题。
一些构造算法(如Ukkonen算法的此版本)需要在节点之间建立链接。这些链接“指向”树中的节点。在命令式语言中,例如Java,C#等,由于引用类型,这没有问题。
有什么方法可以在Haskell中模拟这种行为?还是有完全不同的选择?
您可以通过系结递归结来使用直到计算结果才确定的值才能用于计算中的数据构造。
以下计算将构建一个值列表,每个值都包含列表中的项目总数,即使总数是由构建列表的同一函数计算出来的。中的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)]
通过传入直到整个结果已知才知道的s,可以将此思想应用于Ukkonen的算法#
。
递归地传递结果到一个函数的总体思路被称为至少固定点,并且在实现Data.Function
由
fix :: (a -> a) -> a
fix f = let x = f x in x
我们可以写zipCount
在自由点式来讲zipWithAndCount
和fix
。
import Data.Function
zipCount :: [a] -> [(a, Int)]
zipCount = snd . fix . (. fst) . flip zipWithAndCount
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句