Type classes

Next topic to learn in CIS 194 was type classes. They’re quite similar to interfaces in some other languages and used for similar purpose: polymorphism.

Previous lessons had introduced me to type classes already. For example, in order to be able to compare two values, they have to belong to Eq type class. Eq declares, that every type that is instance of it, has two functions defined for it == and /=. They are used to compare two instances for equality or inequality. Many standard types, like Integer and Char belong to this type class.

Eq can be defined as:

class Eq a where
  (==) :: a -> a -> Bool
  (/=) :: a -> a -> Bool
  x == y = not (x /= y)
  x /= y = not (x == y)

So, it even comes with default implementations for the two functions (that are recursive). This means that it’s enough to declare only == or /= and default implementation will take care of the rest.

If we have an imaginary type Foo, we can make instance of the type class as following:

data Foo = Foo Integer
instance Eq Foo where
  (Foo a) == (Foo b) = a == b

The exercise was interesting. It evolved through multiple stages (as usual) where you had to implement a simple calculator. First a very concrete implementation with simple integers and then one using type class that you defined. After that there were series of different kinds of calculators using the type class, culminating with a hypothetical compiler for stack based calculator. I liked doing the exercise, as it wasn’t too convoluted or made up and showed power of type classes nicely.

Like, the type class that I defined was simple (literals, addition and multiplication):

class Expr a where
  lit :: Integer -> a
  add :: a -> a -> a
  mul :: a -> a -> a

And instance for integers was easy enough:

instance Expr Integer where
  lit a   = a
  add a b = a + b
  mul a b = a * b

But the neat trick was, that I could implement calculator using modulo 7 numbers (ie. no number was ever larger than 7), just by defining:

newtype Mod7 = Mod7 Integer deriving (Show, Eq)

instance Expr Mod7 where
  lit a = Mod7 $ a `mod` 7
  add (Mod7 a) (Mod7 b) = Mod7 $ (a + b) `mod` 7
  mul (Mod7 a) (Mod7 b) = Mod7 $ (a * b) `mod` 7

And for stack based virtual machine:

instance Expr VM.Program where
  lit a   = [VM.PushI a]
  add a b = a ++ b ++ [VM.Add]
  mul a b = a ++ b ++ [VM.Mul]

Pretty nifty, quite readable and very concise (without being obscure).

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s