Borges, Haskell, Euler

In one of my favorite Borges stories, he describes the imaginary people of Tlön who speak a language that has no nouns.  They have only impersonal verbs, adverbs, and prepositions.  Instead of saying, 'The moon rose above the river,' they would say something like, 'Upward, behind the onstreaming it mooned.'  The story explores the ways in which language shapes what we do and how we think.  Borges writes, 'For the people of Tlön, the world is not an amalgam of objects in space; it is a heterogeneous series of independent acts.'  This raises the question: how would your life be different if you didn't have a word for 'you' or 'I'?

You don't have to merely ponder this if you learn a functional language like Haskell (named after mathematician Haskell Curry).  I've taken a deep dive into Haskell, though I still feel like one of the early explorers trying to understand Tlön.  If you're used to thinking in terms of 'objects in space'--that is, if you mostly work in object-oriented languages--Haskell is very weird at first.  You'll have to start thinking in terms of functions.  Even basic units, like the number 5, are really functions that return the value 5 and which can then be passed to other functions.

Check out this implementation of the Quicksort algorithm, taken from Miran Lipovača's awesomely-named book Learn You a Haskell for Great Good!:

quicksort :: (Ord a) => [a] -> [a]
quicksort [] = []
quicksort (x:xs) =
    let smallerSorted = quicksort [a | a <- xs, a <= x]
        biggerSorted = quicksort [a | a <- xs, a > x]
    in  smallerSorted ++ [x] ++ biggerSorted

This code declares a function quicksort, which takes a list and returns a list of things that can be ordered.  It recursively calls itself, so the base case is an empty list.  It grabs the first item from the list and uses it as the pivot to generate two other lists of all items greater and smaller that it.  Then it concatenates and returns the sorted sublists.  Voila!

You might wonder why it's useful to learn a language like Haskell.  I personally haven't seen any production Haskell code, though you can find some cases of it.  I wanted to learn Haskell because it is a purely functional language, and I thought it would help me better understand some of the ways functional programming is creeping into OOP.  For example, Java 8 will have closures, the Clojure language is gaining popularity, and C# makes heavy use of lambdas and extension methods in LINQ.

I have also heard that learning Haskell will make you a better programmer.  I do think it's hard to really know any language unless you know what else is out there, just like I think it's a bad idea to maintain a belief in something if you don't consider other beliefs, whether it's politics, religion, or anything else where reasonable people disagree.  However, I'm not sure what Haskell or other functional languages teach besides recursion.  You really have to be comfortable with recursion to do any amount of functional programming.  For example, you could write a function to check if a list or string of characters is a palindrome in the following way:

isPalindrome :: (Eq a) => [a] -> Bool
isPalindrome ([]) = True
isPalindrome ([x]) = True
isPalindrome (x:y) = 
    if x == z && isPalindrome w then True else False
    where z = last y
          w = init y

Haskell is great for problems where you can break a task into a series of mathematical equivalences.  It's hard for me to imagine trying to solve Project Euler problems without Haskell.  I've done about 25 of these for practice, and I highly recommend poking around in them.  Problem 20, for example, asks you to sum the digits of 100!.  This can be done in one line of Haskell.  Problem 9, which asks you to find a Pythagorean triangle where a + b + c = 1000, can also be done in one line.  First you generate three lists of numbers (a, b, and c) from 1 to 500 or so.  Then you get a list where a² + b² = c².  Then you get a list where a + b + c = 1000.  Finally, you filter out all the items where a < b < c to get a unique tuple. 

I've written before that you have to be careful with functional languages because they abstract away the implementation from the code.  In the Pythagorean example above, for example, you do not have to write a series of for loops.  It's easy to write code that will take days or years to finish in Haskell.  I speak from experience.  (For fun, try running last [1..]).   But this kind of abstraction can be beneficial, as the logical nature of Haskell highlights the logic of your thought process.  One of the most important things I've learned in working with Haskell, especially on problems dealing with huge numbers, is just how important it is to have a good algorithm.  Because Haskell programming is nothing but functional logic, it's easy to concentrate on the essentials.