Posted on April 25, 2017 by Dave Taylor


In programming we attempt to model state with data structures. In many object oriented paradigms the focus is narrowed towards state of a data structure at a specific point in time through objects and primitives.

With streams that focus is shifted to the entire history of values, not specific changes. In short we stress the pipeline and transformation of data from beginning to end.

Thus, stream processing let’s us model state without side effects and requires the programmer to consider the whole life cycle of a system, often resulting in better code.

A non stream approach (Java) to calculate primes requires the implementer to manage the state of primes lists while the stream approach (Clojure) does not.

for(i = 2, x = 2; i <= n; i++) {
  for(x = 2; x < i; x++) {
    if(i % x == 0) {

  if(x == i) {
(filter prime? (iterate inc 1))

Streams as lists

“As a data abstraction, streams are the same as list. The difference is the time at which the elements are evaluated” - SICP

A simple implementation of a stream is as a lists. Unfortunately, implementing a stream strictly as a list requires the full time and space complexity of a data structure throughout it’s life cycle. Remember, we are not interested in snapshots of data structures at a point in time, but rather its whole history.

Intuitively, you can begin to understand the resources required.

Demand Driven

“If time is measured in discrete steps, then we can model a time function as a (possible infinite) sequence” - SICP

Efficiencies of processing via streams are realized through delayed evaluation.

Programs can be written with powerful and succinct abstractions like map, filter and apply without incurring the resource costs of a list implementation.

Resources are only allocated partially, and can require more as they are needed. This paradigm enables us to write code as if we were processing the complete history of a data structure, without the overhead.

We may also model sequences as if they were infinite while only having limited resources. From the implementers perspective the Clojure function repeat creates a stream that will repeat forever, and the function take will grab from that infinite list.

The complexity of managing these resources and the impossibility of providing them is completely hidden from the implementor.

(take 100 (repeat "Infinity"))

A non-cached fibonacci sequence in Java using recursion requires the full time plus space complexity of the sequence:

public static int fib(int n) {
  if (n <= 2) { 
    return 1;
  } else {
    return fib(n-1) + fib(n-2); 

While the Clojure version using delayed evaluation does not. Streams benefit from the efficiency gains of delayed evaluation, without requiring the implementer to worry about the intricacies of managing the resources.

(def fib (map first (iterate (fn [[a b]] [b (+' a b)]) [0 1])))