Implementing an Iseq-conforming linked list in Clojure

Date

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:

  1. Whether empty can return nil, or does it have any other constraints?
  2. Similarly, should equiv be programmed against the ISeq interface? Should I provide equality for any other ISeq? If so, is there a default implementation somewhere? Seems like there could be.
  3. What's the difference between next and more?
  4. When representing an empty sequence I want to use a particular type as an indicator. It seems PersistentList follows this pattern, evaluating (type '()) returns clojure.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)
        ))
  )