What is the correct term for the following functional programming pattern?

Question

I've heard it referred to as a stream, as an infinite list, and sometimes even as a lazy sequence.

What is the correct term for the following pattern? (Clojure code shown)

(def first$ first)

(defn second$ [str]
  (cond
    (empty? str) ()
    true ((first (rest str)))))

(defn stream-builder [next_ n]
  (cons n (cons (fn [] (stream-builder next_ (next_ n))) ())))

(defn stream [str n]
  (cond
    (= 0 n) ()
    true (cons (first$ str) (stream (second$ str) (- n 1)))))

(def odd 
  (stream-builder (fn [n] 
        (+ 2 n))1))

(println (stream odd 23))

> (1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45)

Answer 1

Short answer: stream-builder returns a function that returns an infinite sequence/list, which must be evaluated 'lazily' (since you can't evaluate something infinitely long in finite time). In the Clojure world, you should probably call none of the things in your example "streams" to avoid confusion with another concept.

Longer answer:

An unfortunate side effect of the diversity of thought in programming languages is that we often use the same words for different meanings. All three words you mentioned ("Stream", infinite list", "lazy sequence") refer to processing elements in a serial fashion, and in Clojure we call these "Sequences". However, the nuances implied by each are slightly different.

A "stream" refers generally to some sequence of elements, and is nowadays often used in the context of finite character sequences. Often these character sequences come from a file, network source, or Unix pipe.

If a sequence is defined in a way that it has an infinite number of elements, we can call it an infinite sequence. Usually infinite sequences are represented internally as a linked list , so we may call these "infinite lists". Although, to be honest I would prefer to hear the term "infinite sequence" in the Clojure community so we are not tied to a particular implementation.

Finally, the nuance of "lazy sequence" in Clojure refers to a pattern of sequential evaluation on a data structure that occurs "on demand". In other words, the emphasis here is on the lazy nature of evaluation; the value of a particular element in the sequence is not actually computed until you ask for it.

In summary, in Clojure you should use the words:

• "list" to refer to something with a linked list implementation
• "lazy" to refer to things that evaluate on demand
• "infinite" to refer to sequences that aren't of finite size (and must therefore be lazy)
• "stream" to refer to a pipe-like (character) sequence from an external source

Answer 2

This is not an answer to your question, but in the interest of writing "nice" clojure code, I wanted to point out a few things with your example.

One of the benefits of the functional style is the ability to compose functions together. But if you take a look at the functions you've written, they individually don't do much without depending on functionality provided elsewhere.

For example, stream-builder just returns a two-element list of n and an anonymous function to handle pseudo-recursion.

My guess is that you were trying to go for a lazy sequence, but doing it that way requires support functions that are aware of the implementation details to realize the next element, namely, stream and second$. Thankfully you can instead accomplish it as follows:

(defn stream-builder [f x] ; f is idiomatic for a function arg
  (lazy-seq                ; n is idiomatic for a count, so use x instead
    (cons x 
      (stream-builder f (f x)))))

The above will actually return an infinite sequence of values, so we need to pull out the limiting behavior that's bundled inside stream:

(defn limit [n coll] ; coll is idiomatic for a collection arg
  (lazy-seq          ; flipped order, fns that work on seqs usually take the seq last
    (when (pos? n)
      (when-let [s (seq coll)]
        (cons (first s) 
          (limit (dec n) (next s)))))))

The above will lazily return up to n elements of coll:

user=> (limit 5 (stream-builder inc 1))
(1 2 3 4 5)

In the end, each function does one thing well, and is composable with other functions:

Finally, you defined odd to be the lazy sequence of odd integers. The danger is that sequence is going to stick around as it gets realized (this is known as "holding onto the head" of a sequence). This can unnecessarily take up excess memory to hold onto every element ever realized, and prevents garbage collection.

To solve this, either do not def the lazy sequence, or def it with the limit, e.g.:

(def odds (limit 23 (stream-builder #(+ 2 %) 1)))

For future reference, what we have just written is available in the core lib as iterate and take, respectively:

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