Вы можете использовать значение, которое не определяется до результата вычисления при построении данных при вычислении на tying a recursive knot.
Следующее вычисление создает список значений, каждый из которых содержит общее количество элементов в списке, даже если общее число вычисляется одной и той же функцией, которая создает список. Связывание 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's algorithm пропусканием в #
с, которые не являются до тех пор, пока не будет известен весь результат.
Основная идея рекурсивного прохождения результат в функции называется наименьшей неподвижной точкой, и реализуется в 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
Когда все остальное не удается, вы можете написать свой алгоритм с использованием 'ST' и' STRef'. Вы можете «запустить ST», чтобы получить свое чистое суффиксное дерево в конце. – chi
Почему алгоритм Укконена настолько популярен в последнее время в теге Haskell, есть еще один вопрос, без правильного ответа, хотя - только подсказки в комментариях: http://stackoverflow.com/questions/19370296/haskell-data-type-with-references – phadej
Вам нужны только ориентированные ациклические графики? Графики можно использовать из пакета [this] (https://hackage.haskell.org/package/fgl). – user3237465