Friday, December 26, 2014

Think like a Fundamentalist, Code like a Hacker...


I've just finished Eric Meijer's Intro to Functional Programming on edX. Since the course was taught in Haskell, I also managed to get my feet wet with the language and now feel prepared to work through Learn You a Haskell and Real World Haskell.

One of the course's mantras has been "think like a fundamentalist, code like a hacker". The idea is to start with an approach that is fundamentally correct and iteratively refine the implementation. This is a pretty convincing philosophy for Haskell (and perhaps functional programming in general), since things like type checking and pattern matching facilitate reasoning about the correctness of programs. An interesting question that follows, however, is how to balance readability/clarity vs the efficiency of solutions that are fundamentally sound but "hacked".

There's a good example in Graham Hutton's Programming in Haskell called "Making Append Vanish" (chapter 13, section 6). We start with an example of a recursive function that reverses the elements of a list:

reverse              :: [a] -> [a]
reverse []            = []
reverse (x:xs)        = reverse xs ++ [x]


Because this solution using the ++ append operator is relatively inefficient (requiring quadratic time), Hutton demonstrates using induction that a linear time solution can be derived:

reverse              :: [a] -> [a]
reverse xs            = reverse' xs []


reverse'             :: [a] -> [a] -> [a]
reverse' [] ys        = ys
reverse' (x:xs) ys    = reverse' xs (x:ys)

At least for me, the second solution takes much longer to digest, and hence is less clear -- but it is demonstrably correct and far more efficient. I'm not sure if it's really fair to call the second solution "hacked". But it does illustrate an interesting aspect of the functional programming paradigm, which I'm looking forward to exploring further.