Modeling Software Algorithms using Lazy Sequences

If there is one thing I’d recommend any software engineer do to up her game, it’d be learn different languages. I think a great linguist once said that the vocabulary and richness of our thinking is shaped in no small part by language. There are words/phrases in French/German/Latin/Arabic that have no equivalent in English and the opposite is probably true as well.

Why do I bring this up? I think the same holds true for computer languages. I had recently been poking around with Haskell and it’s elaborate use of infinite sequences is liberally sprinkled all through the language.

Want to calculate the n-th prime? Your code would look something like:

take n [X | X <- [1..], is_prime(X)]

The real beauty lies in the “[1..]” which is just an infinite collection starting with one. In clojure, or a LISP the code would look like:

(take n (filter is-prime? (iterate inc 1)))

Here “(iterate inc 1)” is the same as “[1..]”. In my opinion, the Haskell representation is a lot nicer and easier to read.

Creating infinite sequences

The fundamental concept that needs to be grokked when you would like to create your own infinite sequence is a Generator. Basically, it’s a function you would keep calling to get the next value. If you know, Javascript here is some code that generates infinite numbers starting from a number you give it.

Here javascript’s closures are used to capture the “start” variable. And each call of “next()” returns the incremented value.

In clojure this same thing is accomplished by creating a “lazy-seq” which is basically a two element list. The first element is the value that should be returned when someone calls it and the second argument is a function to call to update the state of the lazy sequence.

The same code in clojure would look like:

Modelling fibonnaci numbers

Walk into any interview and probably the first thing they’ll ask you is to write a fibonacci generator to get the nth fibonacci number. The Haskell’ish way of modelling this would be:

take n [X | X <- (fibonacci_numbers)]

And then you write the “generator” for fibonacci numbers. So, in clojure this would look something like:

This is basically a function that takes the two most recent fibonacci numbers and returns a lazy-seq. The “lazy-seq” in turn returns the most recent number when called and for the next iteration it calls the fib function again this time passing in the most recent number and the sum of the two most recent numbers.

Want the nth fibonacci from this? Simple:

(last (take n (fib)))

That to me is really elegant.

TL;DR

I highly recommend you model your solution the Haskell way when you need to solve a problem. Something like so:

[X | X <- (all_students), is_sophomore(X) and major(X) == “economics”]

Now you are just left with implementing the “all_students” generator.