Связывание в древовидных структурах

Поработав сейчас с длинными строками, я столкнулся с довольно большой проблемой при создании деревьев суффиксов в Haskell.

Некоторые алгоритмы построения (например, эта версия алгоритма Укконена) требуют установления ссылок между узлами. Эти ссылки «указывают» на узел в дереве. В императивных языках, таких как Java, C# и т. д., это не проблема благодаря ссылочным типам.

Есть ли способы подражать этому поведению в Haskell? Или есть совсем другая альтернатива?


haskell suffix-tree
person ThreeFx    schedule 27.12.2014    source источник
comment
Когда ничего не помогает, вы можете написать свой алгоритм с отслеживанием состояния с помощью ST и STRefs. Затем вы можете runST получить свое чистое дерево суффиксов в конце.   -  person chi    schedule 27.12.2014
comment
Почему алгоритм Укконена так популярен в последнее время в теге Haskell. Есть еще один вопрос, но без правильного ответа - только намеки в комментариях: stackoverflow.com/questions/19370296/   -  person phadej    schedule 27.12.2014
comment
Вам нужны только ориентированные ациклические графы? Вы можете использовать графики из этого пакета.   -  person user3237465    schedule 27.12.2014
comment
Один из стандартных приемов построения самореферентных структур называется завязыванием узла. Вам могут быть полезны ответы на этот вопрос: Как вы представляете график в Хаскеле?.   -  person Christian Conkle    schedule 27.12.2014
comment
О, и есть вопрос без ответа по аналогичной теме, в котором есть несколько комментариев, которые вы можете найти полезным.   -  person Christian Conkle    schedule 27.12.2014

Ответы (1)


arrow_upward
2
arrow_downward

Вы можете использовать значение, которое не определено до тех пор, пока не будет получен результат вычисления при построении данных в вычислении с помощью завязывание рекурсивного узла.

Следующее вычисление создает список значений, каждое из которых содержит общее количество элементов в списке, несмотря на то, что общее количество вычисляется той же функцией, которая строит список. Привязка 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)]

Эту идею можно применить к алгоритму Укконена, передав #, которые неизвестны, пока не будет известен весь результат.

Общая идея рекурсивной передачи результата в функцию называется наименьшей фиксированной точкой и реализована в 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
person Cirdec    schedule 27.12.2014