[Haskell] Why functional programming matters

[Zsolt Dollenstein]

Hi!

My personal favourite is a neat (read: efficient and mostly write-only)
way to balance AVL trees which I learned at a Haskell course on my
university.

This is the first implementation which comes to one's mind when playing
with Trees:

> data Tree a = L | N (T a) a (T a)

Balanceness is defined in terms of a tree's height:

> height :: T a -> Int
> height L = 0
> height (N l a r) = 1 + max (height l) (height r)

This gets the difference of the subtrees' heights: (Note that it could
return a negative value, too.)

> skew :: T a -> Int
> skew L = 0
> skew (N l a r) = (height l)-(height r)

Our tree is balanced iff the skew is at most 1 for every subtree:

> balanced :: T a -> Bool
> balanced L = True
> balanced t@(N l a r)
>             | abs (skew t) <= 1 	= balanced l && balanced r
>             | otherwise 		= False

Now the interesting part. What if a tree is not balanced? Here do
rotations come into the picture. There are several types of rotations
which usually need some attention and are awkward to code in an
imperative language. Of course one can do it in a functional language
almost as awkward as in an imperative one, but the point is to use
pattern matching like shown below:

> rightRot :: T a -> T a
> rightRot (N (N x a y) b z) = N x a (N y b z)
> rightRot a = a

This is one of the simplest cases which makes it relatively easy to
read. The thing is that this is a really fast implementation achieved
at almost no effort.

Also, it doesn't get harder than this:

> leftRightRot :: T a -> T a
> leftRightRot (N (N x a (N y b z)) c v) = N (N x a y) b (N z c v)
> leftRightRot a = a

which can also be written as:

> leftRightRot (N x a y) = rightRot (N (leftRot x) a y)


So I think this was the moment when I made up my mind to commit myself
to Haskell & FP.

Cheers,
Zsolt





-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 481 bytes
Desc: not available
Url : http://www.haskell.org/pipermail/haskell/attachments/20080123/06b5561b/signature.bin