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

Nice post, man. I bet Scala and Haskell are both influenced by ML.

ReplyDeleteGood for you learning Haskell. That's something I've wanted to do too

but never got into it. You are one passionate dude. Keep it up! This

will make you awesome.