Неизменяемая структура Три в F #

Question

Я играю с алгоритмом aho-corasick, чтобы попытаться немного улучшить свою работу с F #, и я наткнулся на проблему с реализациями Trie, все они изменчивы или не могут быть оптимизированы с помощью хвостового вызова.

Основная проблема, которую я вижу, заключается в том, что неизменяемые структуры данных должны создаваться «снизу вверх», поскольку вы не можете изменить то, на что они указывают, поэтому ваши параметры либо делают их изменяемыми, либо определяют узлы как вы идете вместе (т. е. рекурс в строительстве).

Есть ли способ создать неизменную структуру данных Trie с оптимизацией хвостовых вызовов в конструкции? (И не потерять эффективность при копировании.)

Answer 1

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

type Trie = 
 | Data of string * int * Trie * Trie 
 | Leaf 

let Insert start key value = 
  let rec inner current withNode = 
    match current with
    | Data (currentKey, currentValue, left, right) ->
      if key < currentKey then
        inner left (fun left -> Data (currentKey, currentValue, left, right))
      else 
        inner right (fun right -> Data (currentKey, currentValue, left, right))
    | Leaf -> withNode (Data (key, value, Leaf, Leaf))
  inner start (fun x -> x)

Удаление копий будет немного сложнее, если вы хотите придерживаться неизменных структур

Answer 2

Я сталкивался с этим постом во время поиска для моего поста с обзором кода , где я реализовал его в неизменном виде.

Это эффективно с использованием карт для ссылок, а не двоичных деревьев.