Coursera:progfun-2012, Week 3

gistfile1.lhs

This is an example of implementing set with binary tree, original Scala code:

abstract class IntSet {
	def incl(x: Int): IntSet
	def contains(x: Int): Boolean
	def union(other: IntSet): IntSet
}

class Empty extends IntSet {
	def contains(x: Int): Boolean = false
	def incl(x: Int): IntSet = new NonEmpty(x, new Empty, new Empty)
	def union(other: IntSet): IntSet = other
}

class NonEmpty(elem: Int, left: IntSet, right: IntSet) extends IntSet {
	def contains(x: Int): Boolean =
		if (x < elem) left contains x
		else if (x > elem) right contains x
		else true

	def incl(x: Int): IntSet =
		if (x < elem) new NonEmpty(elem, left incl x, right)
		else if (x > elem) new NonEmpty(elem, left, right incl x)
		else this

	def union(other: IntSet): IntSet =
		((left union right) union other) incl elem
}

I was (and always, every single example) wondering: can I implement it in Haskell? Yes.

> data IntSet = Empty | NonEmpty Int IntSet IntSet deriving (Eq, Ord)

> instance Show IntSet where
>   show Empty            = "."
>   show (NonEmpty x l r) = "{" ++ show l ++ show x ++ show r ++ "}"   

> contains :: IntSet -> Int -> Bool
> contains Empty _ = False
> contains (NonEmpty x left right) x' | x > x'    = left `contains` x'
>                                     | x < x'    = right `contains` x'
>                                     | otherwise = True

> include :: IntSet -> Int -> IntSet
> include Empty x = NonEmpty x Empty Empty
> include set@(NonEmpty x left right) x' | x > x'    = NonEmpty x (left `include` x') right
>                                        | x < x'    = NonEmpty x left (right `include` x')
>                                        | otherwise = set

> union :: IntSet -> IntSet -> IntSet
> union Empty other = other
> union (NonEmpty x left right) other = left `union` right `union` other `include` x

Sample results:

λ (NonEmpty 3 Empty Empty) `include` 4
{.3{.4.}}
it :: IntSet

λ let s = NonEmpty 2 (NonEmpty 1 Empty Empty) (NonEmpty 3 Empty Empty) `include` 4 `include` (-1) `include` (-2) in s `union` s == s
True
it :: Bool

One thing I really like about Haskell is its concise & elegant syntax, comparing to 
the original code, I simply LOVE this one.

I think choosing Scala as a language used in "Functional Programing Principles" is 
not a very good idea, it brings terms like "object", "sub-classing" in sight, while 
the true topic is functional programming. I guess what the lecturer really want to 
express is the concept of type & typing. 

Haskell lets you hit the purist part of functional programming, along with the 
beauty of type. I would personally recommend everyone taking the class to take a 
look at Haskell.