Must Clojure circular data structures involve constructs like ref?

Question

Today I've seen some references to tying the knot and circular data structures. I've been out reading some answers, and the solutions seem to involve using a ref to point back to the head of the list. One particular SO question showed a Haskell example, but I don't know Haskell well enough to know if the example was using a the Haskell equivalent of a ref.

Is there a way to make a Clojure data structure circular without using a ref or similar construct?

Thanks.

Answer 1

I straightforwardly translated the Haskell example into Clojure:

user> (def alternates
          (letfn [(x [] (lazy-seq (cons 0 (y))))
                  (y [] (lazy-seq (cons 1 (x))))]
            (x)))
#'user/alternates
user> (take 7 alternates)
(0 1 0 1 0 1 0)

It works as expected. However I prefer the cycle function to mutually recursive functions using letfn:

user> (take 7 (cycle [0 1]))
(0 1 0 1 0 1 0)

Answer 2

It's impossible to create a circular reference using the standard Clojure immutable data structures and standard Clojure functions. This is because whichever object is created second can never be added to the (immutable) object which is created first.

However there are are multiple ways that you can create a circular data structure if you are willing to use a bit of trickery:

• Refs, atoms etc.
• Mutable deftypes
• Java objects
• Reflection trickery
• Lazy sequences

In general however, circular data structures are best avoided in Clojure.

Answer 3

I've used this before:

;; circular list operations
(defn rotate
   ([cl] (conj (into [](rest cl)) (first cl)))
   ([cl n] (nth (iterate rotate cl) (mod n (count cl)))))

The output is a vector but the input can be any sequence.