Recently in haskell Category

Ola niños. Hope you recover from the shock of seeing a new entry on this blog. Haven't been here in a while. Looks like this is all still up and running. I'm surprised I still remember my mt password.

So why this entry ? Well, I've done another thing I haven't done in a while: I wrote yet another note in LaTeX solving some simple problem in a pompous way. I used Scala to implement the solution. Scala is coming along nicely, it feels natural to me and it has some powerful abstractions and features. There's definitely a buzz about it. A book on it is now available, the Eclipse plugin behaves well and there are open source projects that use it.

Got these from the scala mailing list: interesting functional programming algorithms (scala enthusiasts are porting them over from haskell)

Finger Trees: A Simple General-purpose Data Structure

Bryan Ford. Packrat Parsing: a Practical Linear-Time Algorithm with Backtracking. Master's Thesis, MIT, 2002.

This is an example why functional programming is so expressive: data structures are equivalent to the constructor expressions that created them. Combine this with pattern matching on these constructor expressions and your program becomes a mathematical function definition instead of tons of boilerplate "getter/setter", "do this then do that" boredom.

Consider this little exercise:

Given a list start from the beginning of the list and swap list element pairs. Tail elements not forming a pair stay unchanged.
Examples:

[1,2,3,4,5,6,7] -> [2,1,4,3,6,5,7]
[1] -> [1]
[] -> []

In Scala you write:

  def swapPairs[a](xs:List[a]):List[a] = xs match {
    case Nil => xs
    case List(x) => xs
    case x :: y :: ys => y :: x :: swapPairs(ys)
  }

This is exactly how you would think about the problem: if the list starts with at least two elements swap those and consider the rest list. Trivial example, true.

You could probably write a pretty simple program in an imperative language like Java to solve the same thing but I suspect it would still contain a lot more handholding code, you would have to spell it out more to the machine and tell it step by step what you want: take the value from here and put it there...etc.

Scala By Example has a better showcase of this language feature: working with abstract syntax trees generated by a parser.

I stumbled upon the Scala Programming Language a while ago. So far it seems like a dream come true: a functional/object-oriented language with first-class functions, currying, anonymous functions, lazy evaluation, constructor decomposition and pattern matching, a modern and powerful type system (for more on types look here and here) and on top of that transparent access to the rich Java world of code because it runs in the Java VM. The tools are still in a basic stage but this will hopefully change soon too.

I played a little with it, ported my Haskell code snippets to it and it's cool. So I thought I should try a more useful example that actually solves a need: I'm a big fan of Delicious Library but it always bugged me that it didn't export to Bibtex. Luckily DL keeps its data in a xml file so I wrote a little scala program that does the exporting to Bibtex. It's pretty basic and doesn't deal with encodings and escaping funny characters to the TeX syntax but it does a decent enough job for my books collection.

An interesting side problem to the bridge crossing puzzle is to find and generate all the possible ways of crossing the bridge under the constraints of the puzzle.

Here's how it can be solved.