Неизменяемая структура Три в 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

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

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