I’ve been playing around with Haskell a bit. I have to admit, that although I was originally pretty frustrated with the language, I’m really beginning to like it. It’s like a fine wine: it gets better with time, and it’s an acquired taste.
The coolest thing I’ve found so far is how infinite lists work, and more importantly, how they’re specified and represented in the language. I have an undergrad degree in mathematics, so thinking about and reasoning in set notation comes very naturally to me.
Here’s an example of set notation:
For those of you who are less math savvy, you’d read this as “2*x, such that x belongs to the Natural Numbers (the non-negative integers) and x^2 > 3”
This same notation actually works well in Haskell. The set itself is specified by the line:
ourSet = [ 2*x | x <- [0..], x^2 > 3 ]
This is a pretty natural way to represent the set, as it almost looks like the way your favorite math professor would write it on the chalkboard. Here’s a small example program:
The [0..] is just saying to “sample x from the (infinite) list [0,1,2,...]“. It’s also nice that this abstraction truly works: it represents an infinite list. Just how the mathematical set would be infinite too. In terms of abstraction, it doesn’t get much better than this! The abstractions that we’ve been taught in Mathematics directly translate to this language. I can just type it like I’d write it on paper, and it has the same semantics.
This program outputs 4 6 8 10 12 14 16 18, as expected. The variable ourSet is actually an infinite list, so the takeWhile just tells Haskell to stop evaluating the list if an item in the list is greater than or equal to 20. We obviously can’t print out something that is infinite, so we have to tell Haskell to stop evaluating somewhere. The rest of the code isn’t particularly relevant, it’s just telling Haskell to print the list to the command line.
Seems pretty sweet, right? So let me explain a bit about what frustrated me at first. What if we switch the predicate such that we are looking for x^2 < 3 (instead of x^2 > 3)? Well, this should just yield the set {0^2, 1^2} = {0, 2}, since only 0^2 < 3 and 1^2 < 3. After we get to x > 1, the predicate fails, since 2^2 < 3 is not true. Similarly, it will continue to fail, since [0,1,2,...] is always increasing, and the square function is also increasing as x increases. So, if we know that x = 2 will fail the predicate, then anything greater than 2 will also fail the predicate. Let’s see it in Haskell:
Note that it’s almost the same as the original, except we switched a > with a < on the third line, and we can just print out the set directly since the set is clearly finite…right? It turns out this code produces an infinite loop. I find this frustrating, since any human looking at this can certainly tell the set specified is not infinite. I think Haskell could, too (bounded above by a constant, and generating values from a monotonically increasing function should always yield a finite set). I thought that’s what this amazing type system was for. We should be able to do things like this in our code and it just works because our abstractions are solid…not leaky. This is, by definition, a leaky abstraction.
I fully understand why it loops forever. It is pulling values from the list [0,1,2,...], and checking to see if they satisfy x^2 < 3. Here’s an example that gives the desired set:
The !! 0 returns the first item in the list (computer scientists start counting at 0), and !! 1 returns the second item in the list. If you try to evaluate (ourSet !! 2), the code will loop forever. Haskell will test if 2^2 < 3, which is false. Next it will test if 3^2 < 3, which is false. Next it will test 4^2 < 3, which is false, ad infinitum. Like I mentioned earlier: it should be possible in this particular case for Haskell to stop evaluating since the set we are testing against is monotonically increasing, and we are bounded above. Monotonically increasing simply means that the list [0,1,2,...] is always increasing and will never decrease. Similarly, x^2 is always increasing and never decreasing for x >= 0. So why doesn’t Haskell stop evaluating the predicate? Well, for a general predicate, it is not possible to stop evaluating and maintain correctness (see the Halting Problem for more information). But we have a specific predicate that should certainly yield a finite set, and if the abstraction is solid, this means Haskell won’t loop infinitely when we specify this set.
Although this behavior didn’t work like I had hoped by default, I’m confident you could get it to work with your own functions/types that you implement (i.e. creating a type representing monotonic sequences and creating a type representing “constant bounds”). Admittedly I haven’t tried this yet, I’m trying to just focus on solving the first 25 Project Euler problems first to learn more about the language. The abstractions seem really powerful, and things tend to compose nicely by default as a consequence of the language being “purely” functional. It just turns out this one is a little bit leaky ;).
Overall Haskell is pretty slick. I’m really looking forward to learning more about Haskell’s features!
Matt Messersmith's Blog 
Leave a Reply