Monday, May 26, 2008

No Or-Patterns in Haskell?

I ran across Chris Okasaki's excellent Red-Black Trees in a Functional Setting article a few weeks back.  Excellent functional take on Red-Black trees - so much easier to understand than the imperative explanations I've seen elsewhere.  Highly recommended.  

The example code in the article is in Haskell.  I've been learning OCaml for several months now and reading an article like this helps me learn a bit of Haskell along the way.   I did a translation of the code in the article into OCaml which lets me compare and contrast the languages.   Here's my OCaml translation:




(* RedBlack trees in OCaml *)
(* see Okasaki paper: Functional Pearls: Red-Black Trees in a Functional
Setting *)
type color = R | B ;;

type 'a tree = E | T of color * 'a tree * 'a * 'a tree ;;

let rec member x t = match t with
E -> false
| T( _, a, y , b) -> ( if x = y then true else
if x > y then (member x b) else
(member x a) ) ;;


let makeBlack node = match node with
E -> node
| T( _, a, y, b) -> T( B, a, y, b) ;;


let rec balance t = match t with
T(B, T(R, T(R, a,x,b), y, c), z, d) | T( B, T(R,a,x,T(R,b,y,c)),z,d) |
T(B,a,x, T(R,T(R,b,y,c),z,d) ) | T(B,a,x,T(R,b,y,T(R,c,z,d))) ->
T(R, T(B,a,x,b), y, T(B, c,z,d))
| _ -> t ;;

let rec insert x s =
let rec ins s = match s with
E -> T( R, E, x, E)
| T(c, a, y, b) -> ( if x = y then T(c,a,y,b ) else
if x > y then ( balance (T(c,a,y,(ins b))) ) else
( balance (T(c,(ins a),y,b)) ) ) in
makeBlack( ins s) ;;





Notice that in the balance function there are four patterns which lead to the same result. OCaml handles this nicely without repetition of code. However it seems that the Haskell version requires that the result be repeated for each of these cases as Okasaki notes in his article. His article was written in 1993 and he mentions that in the future Haskell could have or-patterns, but from what I can tell by googling around a bit and asking on the PDX_func mailing list this feature is still not in Haskell. So here's a situation where I definitely can say that I prefer the (OCa)ML solution. I'm sure there are other things to prefer in Haskell, though, like type classes.

2 comments:

Jon Harrop said...

AFAIK, Haskell never officially got or-patterns. This is quite a tame application of them though. They can be far more useful than they are here because they can be nested to any depth, e.g. (1|2|3)::xs -> ...

Jon Harrop said...

PS: If you want examples of things you can do with pattern matching that OCaml cannot express, check out my bubble sort in a Mathematica pattern and active patterns in F# (aka view patterns).