99 Problems

I ran across an awesome blog post today titled Programming Problems To Improve Your Language Skills. I never actually wrote anything in Haskell yet, but I thought that solving the Ninety-Nine Lisp Problems was a great way to start. That's the point of this post. There is, however, a goofy Scala snippet that's in order first.

Had it All Wrong

Development comes in spurts. Even though I'm in the middle of several personal projects, sometimes a simple change in pace really helps. I took a break from coding to dive in some Haskell (some break). I ran across an online book, published by Miran Lipovaca, that looked fun and interesting enough to learn the language: Learn You a Haskell for Great Good.

I read through five chapters last night, only to discover that I should have learned Haskell before learning Scala. I now see how much concepts Scala has pulled from Haskell. My opinions on the experience thusfar will be expounded on after the jump.

For the Great Good, Indeed

The more I understand about Haskell, the more I love it. Due to my time learning Scala, I feel very at home with the language. The point of this post is to observe similarities with the two, as I go about learning.

The last chapter I read was about recursion, something I understand very well at this point. As Miran describes, the poster child for Haskell is the quicksort implementation.

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

Now a side by side Scala implementation...

// Need this for Haskell like Ord type
implicit Ordered._

def quicksort[A: Ordering](ls: List[A]): List[A] = ls match {
  case Nil => Nil
  case x :: xs =>
    val (smaller, bigger) = xs partition(_ <= x)
    quicksort(smaller) ++ List(x) ++ quicksort(bigger)
}

The Breakdown

Time for a line by line comparison.

// Haskell
quicksort :: (Ord a) => [a] -> [a]  
// Scala
def quicksort[A: Ordering](ls: List[A]): List[A]

The first line is Haskell's way of defining a function. quicksort takes a single parameter, which is a list of type a defined to be Ord. It will return a list that is type a. More specifically, it will return a sorted one.

The Scala implementation does just as well.

// Haskell
quicksort [] = []  
// Scala
ls match {
  case Nil => Nil

The seeming redefinition of quicksort is simply constructing a pattern match. That bit of Haskell specifically states: Given an empty list, an empty list will be returned.

In Scala, you have to be a bit more explicit in your declaration of a pattern match, initiated by the keyword match. A match expression will return something (in this case, we've explicitly defined its type as a List[A], so we better do that). Staying true by our line by line analysis, should ls be Nil (or empty), return empty.

// Haskell
quicksort (x:xs) =   
// Scala
  case x :: xs =>

Should the input parameter be a non-empty list, extract the head of the list from its remainder, and do some work. A singleton list will be extracted thusly:

x:[]

Scala supports pattern matching and extraction in its pattern matching very similarly. If a Scala object defines an unapply method then you can take advantage of this behavior. Once again, we see how Scala caters to this way of thinking.

// Haskell
    let smallerSorted = quicksort [a | a <- xs, a <= x]  
        biggerSorted = quicksort [a | a <- xs, a > x]  
// Scala
    val (smaller, bigger) = xs partition(_ <= x)
// Optional rewritten like so
    val smaller = quicksort(xs.filter (_ <= x))
    val bigger = quicksort(xs.filter (_ > x))
// Scala for comprehensions
    val smaller = quicksort(for(a <- xs; if a <= x) yield(a))
    val bigger = quicksort(for(a <- xs; if a > x) yield(a))

Haskell is binding some variables to use in its in statement which we'll go into in a minute. Haskell has incredible list comprehensions. You can filter, pattern match, use let expressions, etc.

Scala's answer to Haskell's list comprehensions, is the for comprehension. For this example, though, it's a bit overkill. List's in Scala inherit from a Traversable type which comes with powerful operations: map, zip, filter, reduce, to name a few.

We're almost done.

// Haskell
    in  smallerSorted ++ [x] ++ biggerSorted
// Scala
    quicksort(smaller) ++ List(x) ++ quicksort(bigger)
// Or other implementations above
    smaller ++ List(x) ++ bigger

Haskell will now use the bindings set before and work. Haskell will do its work lazily, which is awesome.

Scala list concatenation with other Lists is done exactly the same way as Haskell.

Pretty cool. I'm looking forward to learning more.

-- Philip Cali