Being dynamically typed doesn't mean that there are no types. And in fact, pretending that there are no types gives raise to a number of problems, like unclear semantics of a function and such.
Let's explore an example from the heart of Clojure.
The work horse in the very low-level code of the sequence
library is the
lazy-seq macro. It returns an instance of
clojure.lang.LazySeq which encapsulates the abstract
instructions to realise the actual sequence according to the
body of the
Should this class implement the
To answer this question, we have to understand the types involved and what the semantics of the interface functions are.
First we have sequences—let's call the type “
either nothing –
nil – or something with a first element and
Seq of next elements. In particular there is not an empty
Seq! Clojure's interface to
c.l.ISeq with the
next on the Clojure side.
Let's use some mathematically inspired notation.
first : Seq → Object next : Seq → Seq
Seq represents a sequential view on some collection of things.
That's nice, but how do we get a
Seq in the first place?
Clojure's main factory for sequences is the – surprise! –
function. It may be used to construct a sequential view on an
instance of a given type. It works on
Sets,… In particular is
seq the identity on
Let's call elements in the domain of
seq : Seqable → Seq
This is not the end of the story, however. Why should only
physical things like
Vectors be a source for
Instead of providing the set of elements from which the view is
constructed, one could just as well provide some computation rule
to construct the sequence as it is needed. So one can eg. construct
a sequence of all natural numbers. Since these are infinite in size
they cannot be represented in a datastructure like a
Back in ye olden dayes this was done via
lazy-cons : →Object x →Seq → Seq
lazy-cons constructed from a thunk which evaluates to an
→Object) and a thunk which evaluates to a
→Seq) a sequence consisting of the
Object as first
element and the result of the second thunk as next elements. The
evaluation of the thunks is only done when necessary. That is when
next are called on the result of
lazy-cons returns a true
Seq. But there lies the rub. To
actually create a sequence via
lazy-cons you already have to
know, that there is at least one element! The decision how it looks
like might be delayed, but that there is something, you have to
This has implications. Consider the following example.
user=> (def x (drop-while odd? (iterate #(+ % 2) 1)))
drop-while was implemented by virtue of
this would send you in an infinite loop. Because you have to
know whether to return a
nil, you have to check
whether there is an even number in the input sequence or not.
To remedy this situation the interface of a sequence was modified.
Another function was added:
rest. *In fact:
rest was renamed
rest got a new meaning.*
To be truely lazy, you have to also delay the decision of whether there are next elements.
The outcome might be that there are no more elements. However, you
don't know, yet. So you can't return
nil. So, the return value
rest cannot be a
rest : Seq → Seqable
rest returns a
Seqable, ie. you can call
the return value to obtain again a
Seq. This is also reflected
in the new
lazy-seq constructor which replaces the old
lazy-seq : →Seq → Seqable
lazy-seq has “seq” in its name, it actually
doesn't return a sequence. And as such, I think it is a mistake
c.l.LazySeq to implement
Another example is the empty list
(). The empty list is not a
sequence! If it were,
seq would return
() again, which it
does not. It returns (correctly)
nil. Non-empty lists on the
other hand may serve as their own sequence. But this is merely
an implementation detail.
You are still awake? Wow! Congratulations.
This is a dry topic, but an important one. Even in a dynamically typed language like Clojure there are types. And it is important to understand their relationship. I think investing a bit of time in such considerations helps to get a deeper view into the problem domain.
Here the complete, consistent
Seq interface in all its glory.
Although Clojure does not fully adhere to it.
first : Seq → Object next : Seq → Seq rest : Seq → Seqable seq : Seqable → Seq lazy-seq : →Seq → Seqable ; and formerly lazy-cons : →Object x →Seq → Seq
Published by Meikel Brandmeyer on .