Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
An immutable trie idea
(ns alexandergunnarson.immutable-trie)
(defrecord TrieNode
[val complete? a b c d e f g h i j k l m n o p q r s t u v w x y z])
(defn node
([val] (node val false))
([val complete?]
(TrieNode. val complete?
nil nil nil nil nil
nil nil nil nil nil
nil nil nil nil nil
nil nil nil nil nil
nil nil nil nil nil nil)))
; ti:me
; --:cket
(assoc (node \t)
:i (assoc (node \i)
:m (assoc (node \m)
:e (node \e true))
:c (assoc (node \m)
:k (assoc (node \k)
:e (assoc (node \e)
:t (node \t true))))))
; We could have represented the Trie using arrays,
; but not if we wanted to have the Trie behave immutably and
; be postwalkable etc., then it's not a good idea
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.