Search code examples
typesclojurerecordstrie

Which protocol to extend for Trie type?

I'm writing an implementation of a Trie data structure in Clojure and figured it would be best to use defrecord to create my own type which can overload the functions which operate on collections. How can I determine the name of the protocol to extend so that I can implement conj and other similar functions for my new Trie type?

Solution

  • If you want to implement a new data structure, you'll want to use deftype instead of defrecord, as the latter hardwires a certain implementation of map behaviour for the resulting types.

    As for clojure.core collection functions, most of them are based on interfaces rather than protocols. (ClojureScript does use protocols, however.) The simplest way to discover which interfaces may be relevant to a new data structure is to examine similar data structures that already exist:

    ;; all superclasses and interfaces of the class of {}, that is,
;; clojure.lang.PersistentArrayMap
(ancestors (class {}))

;; interfaces only
(filter #(.isInterface %) (ancestors (class {})))

    Since you're planning on implementing a trie, I'm guessing you want to implement a map or set. If so, data.avl implements all the relevant interfaces (and all the relevant protocols in the ClojureScript version) – you could have a look at the source.