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.

## Tuesday, April 12, 2011

## Friday, April 1, 2011

### 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 `List`

s is done exactly the same way
as Haskell.

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

-- Philip Cali