I’m taking Stanford’s Programming Languages class, and I’m back in the happy fuzzy world of functional programming that started my computer science education back at Berkeley with Prof. Brian Harvey’s CS61A. Except this time around we’re doing it in Haskell!
Haskell, so far, has a couple of cool features that’s jumped out at me. (Features is not really the right word, rather, design decision?):
- Lazy Evaluation – this is the big, obvious one that really influences the idioms you use to write code
- Pattern Matching that’s so ridiculous that if I haven’t been writing Scala I would be completely lost, now I’m only 99% mind-blown.
- Cutesy math syntax (for example, list comprehension looks just like math notation: [x * 2 | x <- originalList]
- Multi-Branch functions. AKA, you can define multiple versions of a function (like overloading) and the correct one will be taken. Sounds like overloading, but it blows your mind combined with laziness, of which I’ll give an example in a second
- Functions are either curried or pattern-matched. So, pretty much all my functions can be partially applied.
- Convert prefix operators to infix using “ and infix operators to prefix using (). Neato
- Type Inference. I’m a huge believer in static typing with type inference these days. Eating cake while having cake is the best.
OK, that was a boring lame list of stuff that I’ll probably skip whenever I read this blog post. Notice how I blog to remember stuff.
Multi-Branch function example:
listLength  = 0
listLength (x:xs) = 1 + listLength xs
That’s just looks cool. Straight out of a math textbook.
Helper Functions Idiom:
Haskell (obviously) has nested functions, so you can write functions using local helper functions and accumulators inside the function’s scope. For example, you can write reverse in the “simple” functional manner like so:
reverse  = 
reverse (x:xs) = (reverse xs) ++ [x]
Using, naturally, the cons operator (:), the concatenate operator (++) and the list syntax . This is an inefficient algorithm, since it sweeps the list twice (once going down calling reverse on the cdr of the list, once sweeping back appending elements). Or, you can write reverse sweeping the list only once, using local scope and a helper function:
reverse xs =
let rev( , z) = z
rev( y:ys, z) = rev( ys, y:z )
in rev( xs,  )
That’s a whole lot in only 4 lines, but it only sweeps the list once to reverse it. As you can (kinda) tell, it keeps cons-sing (: operator) the first element of the rest of the list to the first element of the new list being built. That is, it puts the “next” element as the “first” element. This is how you reverse a list, if you think about it for a bit. Cool huh!
Multi-Branch Function Idiom using Laziness
Since the compiler picks the function branch that pattern matches (including type matches) what you’re calling the function on, you can write plenty of code using a haskell idiom that would epic-fail in other languages.
The idiom consists of writing a main function that generates (lazily) all possible points in the solution space and exhaustively searches through it, and writing a set of small “filter” branches of this function that guides the search to be efficient. The laziness prevents tons of temporaries, the branches guides the search.
For example, consider substring matching. You can say that finding whether a string is a substring of another string is the same as generating all suffixes of the string and checking whether your string is a prefix on any of these suffixes. Let’s just write that:
x `isSubString` s = or [x `isPrefixOf` t | t <- suffixes s ]
suffixes  = [""]
suffixes (x:xs) = (x:xs) : suffixes xs
mind blown! zomg! So, on the first line we say, x is a substring of s if x isPrefixOf t evaluates to true for all t in suffixes of s. then we define suffixes of the empty list as the empty string, and suffixes of a non-empty list as that list, cons’ed to the suffixes of everything but the first character of the input list. And that’s all you need, it won’t generate all options, it’ll lazily evaluate things, pattern-matching the type of list to the branch of the function, going nuts.
Define your own conditionals!
Since Haskell is lazy, you can write your own if statement or boolean operator and it’s just like the real thing! In fact, you can write your own eval function in about 10 lines.
Infinite data structures!
Of course, this just comes with laziness. Just implement prime number searching or whatever.
Lots of other cool stuff in here.