CODEWITHSUNDEEP
clojure
blackened
blackened

Reputation: 903

Clojure lazy-seq Natural Numbers

A popular online tutorial gives this example to build natural numbers:

(def infseq (map inc (iterate inc 0)))

For instance, (take 5 infseq) gives:

1 2 3 4 5

I can see what (iterate inc 0) does, but, as a whole, I do not understand what exactly is going on. (For example, this is not a normal function definition.)

Could somebody please explain?

Upvotes: 1

Views: 498

Answers (3)

Thumbnail
Thumbnail

Reputation: 13473

. For the purposes of the example, we could define map and iterate as follows: 

(defn iterate [f init]
  (lazy-cons init (iterate f (f init))))

(defn map [f [x & xs]]
  (lazy-cons (f x) (map f xs)))

... where lazy-cons is a version of cons that doesn't act until it has to. It used to be part of clojure.core, and might have been defined thus: 

(defmacro lazy-cons [x xs]
  `(lazy-seq (cons ~x ~xs)))

To understand these definitions, you'll need to get to grips with recursion, laziness, destructuring, and macros: quite a task! But do so and you'll really understand how clojure's sequence library, including iterate and map, works. It's how I learned.

The definition of iterate is valid. The one of map only works for a single endless sequence argument.

Upvotes: 2

Arthur Ulfeldt
Arthur Ulfeldt

Reputation: 91534

Let's break that expression down: 

(map inc (iterate inc 0)))

Is a list (the datastructure) with this structure:

(function-to-call function-passed-as-first-srgument another-list-as-second-arg)

Now let's explore it by examining it from the inside out!
That inner list:

(iterate inc 0)

has this strucute

(function-to-call function-passed-as-first-argument number)
  • the function being called is iterate, which creates infinite sequences by keeping track of it's internal state, and every time a new value is required to make the make the sequence longer, it takes the function passed as the first argument and calls it on the current state.
  • the function passed as the first argument is inc which takes a numbr and ads one
  • the third argument to iterate is the initial-state. where it should start.

so when this inner expression is evaluated it will immediately return a data structure representing a list without actually building that list yet. When the first value is read from that list it will return the initial value 0 , when the second value is asked for it will use the inc function to come up with the number 1. If the first or second values are needed again they will just be used as is, not recalculated.

so the first argument represents a contract to produce as many numbers as are required. This is in it's self the third argument to the original expression.

The initial expression takes that lazy list and makes a new lazy list.

this new lazy list is returned by the map function. 

(map inc (0 1 2 3 4 ... as many as you read ...))

which will apply inc to each of these just as it's read, and only at the moment it's read (actually it caches 20 or so items ahead to be a little faster) resulting in this sequence:

((inc 0) (inc 1) (inc 2) (inc 3) ... as much as you read from the sequence ...)

Which works out to:

(1 2 3 4 ... created lazily)

Which is the same result as these equivalent expressions, 

(rest (range))

(iterate inc 1)

and many other forms.

Upvotes: 2

Alan Thompson
Alan Thompson

Reputation: 29958

(take 5 (iterate inc 0)) => (0 1 2 3 4)

iterate repeatedly applys the inc function in a loop. You are starting with 0, so you get [0 1 2 3...]

(take 5 (map inc (iterate inc 0))) => (1 2 3 4 5)

(map inc <collection>) applies inc once time to each item in the collection, to the previous result is transformed to [1 2 3 4 ...]

(take 5 (range)) => (0 1 2 3 4)

range w/o any args starts at 0 and counts forever, same as the first example.

Since all of these collections are infinite in length, we need something like (take 5 <collection>) to limit the length of what is printed.

Upvotes: 1

Related Questions