Haskell is cool (infinite self referencing lists)

I’m currently taking CSE 505:Programming Languages at the University of Washington for my masters degree in computer science. We are using Scala at work, a language that incorporates a lot of advanced programming language constructs, so I felt that work and school would synergize well together. As luck would have it, we are learning Haskell for class, and its pretty obvious that a lot of the Scala design and syntax is inspired by Haskell. I’ve been pretty amazed at how expressive a purely functional programming language is compared to a hybrid language like Scala that incorporates both OOP and functional paradigms into its design.

Take for example, lists. In Haskell, you can define data types that are self referencing recursive types. This is not limited to just data types though, you can do the same for lists as well! In the ghci REPL, you can type:

Prelude> let ones = 1:ones

This does exactly what it looks like. “ones” is a list variable that recursively references itself. It is the number one appended to itself over and over again. In fact, if you then type “ones” in ghci, it will print out an infinite list of ones. The beauty here is that Haskell does not evaluate the “ones” list until you actually do something with it. This lazy eval lets you literally work with lists of infinite length! You can then type something like:

Prelude> take 10 ones

which will evaluate to a list with ten 1’s:

[1,1,1,1,1,1,1,1,1,1]

You can also use functions that combine lists. zip takes two lists and produces a single list of pairs, where each nth pair in the list consists of the nth element from lists one and two. If one of the lists has more elements than the other, the resulting list has length equal to that of the shorter list. The extra elements are not paired up with anything and discarded. zipWith is similar to zip. It zips a pair of lists and takes in an additional function parameter that is then applied to each pair in the list. This function takes in two arguments and returns just one.

Prelude> let twos = zipWith (+) ones ones
Prelude> take 10 twos

This prints out
[2,2,2,2,2,2,2,2,2,2]

This leads up to the canonical “hello world” example in Haskell: the one line definition of the fibonacci sequence.

Prelude> let fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

So what exactly is going on here? The tail function returns a list with every element in the original except the first one. To see how the statement works, first recall that zipWith ignores extra elements. So you can think of the above statement as being built out as follows:

Prelude> zipWith (+) [0, 1] [1]
[1]

0:1 are then prepended to [1] which produces [0,1,1]

Prelude> zipWith (+) [0,1,1] [1,1]
[1,2]

0:1 are prepended to [1,2] which produces [0,1,1,2]

Prelude> zipWith (+) [0,1,1,2] [1,1,2]
[1,2,3]

0:1 are prepended to [1,2,3] which produces [0,1,1,2,3]

Prelude> zipWith (+) [0,1,1,2,3] [1,1,2,3]
[1,2,3,5]

0:1 are prepended to [1,2,3,5] which produces [0,1,1,2,3,5] and so on, repeat an infinite number of times.

Note that each recursion adds just one new element to the list, which is the sum of the last and second to last elements in the list. This is exactly the definition of the fibbonacci sequence.

I can interact with this infinite list just like I could any other list. If I wanted to get the 100th element in the sequence, I can type the following and find out that the answer is 354224848179261915075:

Prelude> fibs !! 1000

Awesome.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>