I write this article as I bumble around trying to wrap my head around Clojure. This article serves mostly to document my journey to accomplish the simple task of implementing a linked list. On the face, this is relatively simple:
(defrecord RListNode [value next])
(defn r-first [ln] (:value ln))
(defn r-next [ln] (:next ln))
Now you can do the following:
(->RListNode 42 (->RListNode 12 nil))
=> #clj_brave_book.core.RListNode{:value 42, :next #clj_brave_book.core.RListNode{:value 12, :next nil}}
And to access the first element:
(r-first (->RListNode 42 (->RListNode 12 nil)))
=> 42
But that's not so useful, we can't run the following:
(map even? (->RListNode 42 (->RListNode 12 nil)))
Error printing return value (IllegalArgumentException) at clojure.core/even? (core.clj:1405).
Argument must be an integer: [:value 42]
Well maybe we need to use the same methods that map
relies on. We can look at
the (source map)
and see that it calls (seq coll)
. OK, looks like we'll need
at least seq
. Looking at seq
we see:
(def seq (fn ^:static seq ^clojure.lang.ISeq [coll] (. clojure.lang.RT (seq coll))))
OK... so what is ISeq
? It's an interface. And here is where I started
running into problems. Below I'll summarize the mistakes I made.
My Mistakes
Using defrecord
I used defrecord
when I should have been using deftype
. When trying to
use defrecord
I ran into an error where these methods would be redefined.
Here's an example.
(defrecord RListNode [value next]
Seqable
(seq [this] nil)
)
Duplicate method name "seq" with signature "()Lclojure.lang.ISeq;" in class file foo/core/RListNode
Why? I wasn't sure. It turns out that records automatically implement these protocols, so don't make good carriers for their redefinition.
(contains? (ancestors (defrecord Test [foo])) clojure.lang.Seqable)
=> true
So instead I switched to deftype
.
Using next as my field name
I used next
as my field name. By using a field named next
as in
(deftype ListNode [next])
Here's an example:
(deftype Foo [seq])
(.seq (Foo. 123))
=> 123
; Now try with a protocol
(deftype Bar [seq]
Seqable
(seq [this] 42))
(.seq (Bar. 123))
=> 42
Notice how .seq
returns 42 instead of 123. This becomes a problem when you
try to access a field when there's a duplicate method name defined in the
protocol. I could see this being a problem if you need to implement a protocol
defined by some third party library. I'm sure there's an answer to this, and
it's likely 'namespaces', but i haven't figured that out yet.
Forgetting about inheritance
I got lazy and forgot to look at base interfaces. This one is simple. I saw the
four methods on ISeq
and did not notice that ISeq
extended
IPersistentCollection
and Seqable
.
Using nil as a placeholder
Finally, the REPL's print method mislead me into thinking something was
broken. When first implementing the interfaces I added dummy return values to
the methods I was implementing. I didn't want to start writing logic until I
knew it was in the right place. So I set (first [this] nil)
and likewise
for next
. As a result, the REPL printed the method incorrectly.
(->ListNode 3 (->ListNode 2 (->ListNode 4 nil)))
=> (nil)
In the future I plan to use more recognizable values as placeholders. Perhaps
a keyword such as :no-implemented
, that will at least throw an exception.
Wishes
It would be nice if the three interfaces that make up a sequence were documented. I suppose I'm to subscribe to the holy church of Lisp and just know their behaviors because "they are obvious", but I don't. As I write this I am unsure of a couple things:
- Whether empty can return
nil
, or does it have any other constraints? - Similarly, should
equiv
be programmed against theISeq
interface? Should I provide equality for any otherISeq
? If so, is there a default implementation somewhere? Seems like there could be. - What's the difference between
next
andmore
? - When representing an empty sequence I want to use a particular type as an
indicator. It seems PersistentList follows this pattern, evaluating
(type '())
returnsclojure.lang.PersistentList$EmptyList
. However, I can't find a way to implement a type s.t. both types can reference each other. I can't find a way to later extend the class with the interface either.
Get on with it, let's see the code
Here is my, mostly complete, code. It doesn't work because in an effort to get the empty cases working... I introduced mutually recursive types.
(ns clj-playground.core
(:import (clojure.lang IPersistentCollection ISeq Seqable)
; I'm doing lots of work to get the empty case working. The code was much
; cleaner before.
(deftype EmptyListNode []
Seqable
(seq [this] this)
IPersistentCollection
(equiv [one two] (instance? EmptyListNode two))
(empty [this] (EmptyListNode.))
(count [this] 0)
ISeq
(first [this] nil)
(next [this] nil)
(more [this] nil)
; This is the problematic line, it causes a 'compile' error.
(cons [this var1] (ListNode. var1 this)))
(deftype ListNode [value link]
;ISeq
Seqable
(seq [this] nil)
IPersistentCollection
(equiv [one two] (and
(= (count one) (count two)) true))
(empty [this] (EmptyListNode.))
(count [this] (
loop [
total 0
node this
]
(if (= node (empty node))
total
(recur (inc total) (.link node))
)
))
ISeq
; Should return nil if empty
(first [this] (.value this))
; (.next (.next '(1))) fails, so does this.
(next [this] (if (= (.link this) (EmptyListNode. )) nil (.link this)))
(more [this] (.link this))
(cons [val1 this]
(if (= this (empty this))
(ListNode. val1 nil)
(ListNode. val1 this)
))
)