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.

LINQ and Functional Object-Oriented Programming

It took me a while to come around to the "functional turn" in object-oriented programming. This includes the growth of Clojure and Haskell, as well as Microsoft's new LINQ and F# languages. I've been familiar with functional languages like LISP for some time, but it was hard for me to see how such an austere and limited paradigm could be fruitfully imported into the world of polymorphic objects. Furthermore, as someone well familiar with the dangers of bad SQL programming, the last thing I wanted was to allow a Zelda character to write my queries for me.

I haven't changed my mind about using LINQ to access a database, because database performance is too important to me. However, I have found LINQ to be extremely useful for shredding and joining data into custom data structures made up of generic data types. I do this to pass information between layers of abstraction, such as through WCF, or between classes. For example, you could turn a data table into a list of dictionaries, which could be serialized easily into a custom contract. You could then shred that returned structure into whatever you want, such as key value pairs in an IEnumerable of an anonymous type defining points in a chart.

Many of the recent changes to the C# language have been to make it more functional. C# 4.0 is mostly about dynamic typing, but 3.5 is all about LINQ--or rather, the typing and syntactical changes that make LINQ possible. If you've been away from C# for a few years, the language might look almost completely alien to you due to the introduction of Lambda expressions, expression trees, extension methods, implicit typing, nullable types, anonymous types, and anonymous functions. These features let you do pretty much anything you want with data on the fly.

var Points =
   from DataRow dr in dt.Rows
   where (String)dr["Program"].Trim() == Program
   select new
   {
        Date = (DateTime)dr["Date"],
        Value = Convert.ToDouble(dr[Metric] ?? 0.0)
   };

Though applications like this are where I use LINQ primarily, I can see its attraction for database querying. One of the ugliest and most difficult-to-debug pieces of OO code is SQL statements defined as string literals in application code. It's particularly ugly in VB.NET, since you have to include ampersands and end-of-line characters. The solution has always been to used stored procedures for all data access, but this best practice is not always practiced. LINQ provides you with strong typing, which is nothing to sneeze at. One of the biggest problems with SQL is its lack of type checking, especially when creating dynamic SQL. You could create some really cool data access classes that use LINQ instead of dynamic SQL.

Whether or not you use C#'s LINQ or Java's Clojure, the functional turn in object-oriented programming is interesting for its own sake. On the one hand, languages are becoming more and more flexible and intuitive. They allow you to do a lot with a few lines, and in an intuitive manner that abstracts away details. On the other hand, languages are becoming more complicated than ever. In reading Jon Skeet's C# in Depth, I kept thinking how much more information it provided than I needed to get the job done. I'll be very interested to see how further hybridizations of language provide ever more useful tools, especially for manipulating data.