I like to expose myself to programming languages rooted in different paradigms so that I can expand my skill set, broaden my thinking and learn new ways to solve problems. Lately, I’ve been exploring the world of pure functional programming by studying Haskell.
My object-oriented mind finds the following fascinating:
naturalNumbers = [1..] -- [1,2,3,4,5,…]
This simple statement defines a list starting with 1 and increasing by 1 each step all the way to infinity. The result is not a range that can be enumerated to infinity (for example, 1..1.0/0 using Ruby’s Range class); it’s an actual list that goes to infinity.
In the languages I commonly work with, a statement like this is impossible. Why? When a statement such as the above is encountered, the value of the expression on the right side of the equals sign needs to be computed so that it can be written into the memory address of the variable specified on the left. The practice of evaluating the expression at the time it’s bound to a variable is known as eager evaluation.
Infinite lists and eager evaluation don’t mesh well as the set of values pertaining to an infinite list can’t be finitely computed. With eager evaluation, the above assignment would require that the full set of values making up naturalNumbers be written to memory, something that is impossible because that set has no end.
Haskell doesn’t have a problem with this assignment because it defaults to lazy evaluation. Instead of attempting to materialize the full set of values for naturalNumbers at the time of variable assignment, Haskell waits until values are needed from the list then only computes as many values as are requested. If the consumer wants the first five naturalNumbers, Haskell only calculates the first five naturalNumbers. The fact that naturalNumbers goes to infinity doesn’t cause Haskell to attempt to evaluate to infinity because a finite number of values was requested.
Additional lazy operations can be applied to this list, again with the results being computed only when values are retrieved. Below, we apply *2 (“times two”) to the elements in naturalNumbers, producing an infinite list containing the double of each natural number.
double x = map (*2) x -- applies *2 to each value in list x
-- whether x is finite or infinite is irrelevant
doubledNaturalNumbers = double naturalNumbers
Lazy evaluation also allows lists to be created that reference themself:
everRepeating = 1 : 2 : 3: everRepeating -- [1, 2, 3, 1, 2, 3, 1, 2, 3, …]
In Haskell, “:” is used to join an element to the head of a list. For example, 5 : [6, 7] adds “5” to the front of the list [6, 7], producing [5, 6, 7]. In the above example, “:” is used several times to place 1, 2 and 3 in front of the list everRepeating (yes, that’s correct—the list definition refers back to itself!). So, everRepeating = 1 : 2 : 3: everRepeating becomes everRepeating = 1 : 2 : 3: 1 : 2 : 3 : everRepeating which becomes everRepeating = 1 : 2 : 3: 1 : 2 : 3 : 1 : 2 : 3 : everRepeating and so on ad infinitum. However, the computations to ad infinitum don’t occur automatically because of lazy evaluation; instead, only as much of the list as a consumer requests is assembled.
In closing, consider this intriguing definition of a Fibonacci sequence:
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
zipWith walks in parallel over two lists, applying the function specified as its first argument between the first value from each list, then the second value from each list, and so on, returning the results as a list. So, zipWith (+) [1,2] [3,4] adds 1 to 3 and 2 to 4 to come up with the list [4, 6].
fibs’s first and second values are easy to determine because they are hard-coded: 1 and 1. For the third value, zipWith asks for the first value of fibs and the first value from fibs‘s tail (a list’s tail is the list with its first value removed). These values (1 and 1) are added together to produce fibs’s third value (1 + 1 = 2). zipWith then asks for the second value of fibs (1) and the second value of fibs‘s tail—which is fibs‘s third value (2), which was the value just outputted by zipWith! These are added together to produce fibs‘s forth value (1 + 2 = 3) which zipWith consumes when it computes fibs’s fifth value (2 + 3 = 5). Since zipWith’s list arguments point back to fibs, zipWith ends up consuming values it generates!
Fascinatingly mind-stretching, isn’t it?!