Clojure Cons Cell

my-cons.clj

(def NIL (symbol "NIL"))

(deftype ConsCell [CAR CDR]
  clojure.lang.ISeq
  (cons [this x] (ConsCell. x this))  
  (first [this] (.CAR this))
  ;; next and more must return ISeq:
  ;; https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/ISeq.java
  (more [this] (if
                 (= (.CDR this) NIL)
                 clojure.lang.PersistentList/EMPTY
                 (.CDR this)))
  (next [this] (if
                 (= (.CDR this) NIL)
                 nil ;; next returns nil when empty
                 (.CDR this)))
  
  clojure.lang.Seqable
  (seq [this] this)
  
  ;; for some reason this marker protocol is needed otherwise compiler complains
  ;; that `nth not supported on ConsCell`
  clojure.lang.Sequential 
  
  clojure.lang.IPersistentCollection
  (count [this] (if
                 (= (.CDR this) NIL)
                  0
                  (inc (count (.CDR this)))))
  (empty [this] false)
  (equiv [this other] false))

(ConsCell. 5 10)
(rest (ConsCell. 5 10))
(rest (rest (ConsCell. 5 10)))
(next (ConsCell. 5 10))
(next (next (ConsCell. 5 10)))

;; I somewhat beat this into submission without fully understanding why certain things are
;; required or work the way they do.  I basically poked around for what protocols could potentially
;; be tied to a requirement to have `nth` and found sequential to be a possibility, so put that
;; marker protocol in and it worked.  No idea why it's required other than all seqs are assumed to be
;; sequential, so maybe they must be implemented together? 

;; Also, I know from experience that next should return nil vs an empty list (like rest does), so I made 
;; that change, but an unanticipated benefit was that it fixed an issue I was getting where returning the  
;; empty list (like in `more`), actually shows up in the Cons representation as the last item:

;; For example, defining next as so:

;; (next [this] (if
;;                  (= (.CDR this) NIL)
;;                  clojure.lang.PersistentList/EMPTY
;;                  (ConsCell. CDR NIL)))

;; gives you the following when you create a Cons:

;; (.ConsCell 10 20)
;; >> (5 10 nil)

;; If you do it like this:

;; (next [this] (if
;;                  (= (.CDR this) NIL)
;;                  clojure.lang.PersistentList/EMPTY
;;                  (ConsCell. CDR NIL)))

;; You get the expected:

;; (.ConsCell 10 20)
;; >> (5 10)

;; I assume the prior version is returning an empty list which gets converted to a seq at some point
;; and therefore shows up in the representation, but I'm fuzzy on the details.  Playing with deftypes 
;; is outside my comfort zone.