proglang-09-24-2019.md

Type Classes and Overloading - Programming Languages - Sep 24th, 2019

The following function counts the occurrences of a string in a string array:

count :: String -> [String] -> Int
count _ [] = 0
count s (h:t) =
	if s == h then
		1 + count s t
	else
		count s t 

Let’s make this code work with any type:

count :: a -> [a] -> Int
count _ [] = 0
count s (h:t) =
	if s == h then
		1 + count s t
	else
		count s t 

The above function returns an error!

This is because the equals operator == cannot be used on Any value. This is because equality is not defined for every type like custom types.

For example: A binary search tree can have the same values, but different structures. Two trees could have the values 3, 5, 10 , but one tree could have 5 as its root and the other one could have 10 as its root. Are they equal?

So how do we fix this?

Typeclasses

We need to tell Haskell to only allow parameters that have an Eq typeclass like so:

count :: Eq a => a -> [a] -> Int
count _ [] = 0
count s (h:t) =
	if s == h then
		1 + count s t
	else
		count s t 

Run :info Eq in ghci to see the definition of Eq

Remember:

• Equality is ==
• Inequality is \=

Let’s make an Eq instance for Person:

data Person = Person String Int

instance Eq Person where
	-- Define a function for equality
	(Person name1 age1) == (Person name2 age2) =
		name1 == name2 && age1 == age2

If you don’t define the inequality operator, but do define equality then Haskell will assume the result should be the opposite of equality.

Let’s do quicksort in Haskell

quicksort :: [Int] -> [Int]
quicksort [] = []
quicksort (h:t) =
	-- get all the numbers in t that are less than or equal to h
	let lessThan = quicksort (filter (\n -> n <= x) xs)
		greaterThan = quicksort (filter (\n -> n > x) xs)
	in lessThan ++ [x] ++ greaterThan

How do we make the above quicksort generic?

We need to use the Ord typeclass. Ord stands for Ordering.

• Ord also implements the Eq typeclass

quicksort :: Ord a =>[a] -> [a]
quicksort [] = []
quicksort (h:t) =
	-- get all the numbers in t that are less than or equal to h
	let lessThan = quicksort (filter (\n -> n <= h) t)
		greaterThan = quicksort (filter (\n -> n > h) t)
	in lessThan ++ [h] ++ greaterThan

Let’s define an instance Ord for Person using the type compare

Compare can return three different types:

• GT (greater than
• LT (less than)
• EQ (equal)

instance Ord Person where
	compare (Person name1 age1) (Person name2 age2) =
		compare age1 age2

Now Person can be used with our quicksort function, but if you run in it in ghci you will get an error because ghci doesn’t now how to print a Person variable.

For printing, we have to implement the Show typeclass for Person.

instance Show Person where
	show (Person name age) = name ++ " " ++ show age

Here’s a shortcut for implementing all these instances for Person

data Person = Person String Int
	deriving (Eq, Ord, Show)

The default Ord that this creates looks like this:

instance Ord Person where
	compare (Person name1) (Person name2) =
		compare name1 name2
		-- INCOMPLETE 

Other typeclasses

• Read
  • This convert a string to any type like so: read "3.14" :: Float
  • readMaybe from the Text.Read package is better
• Num
  • Float, Int, Double are implements Num

---

Try to implement Eq, Ord, Show for our custom List type

(incomplete - to be continued next lecture)

data List a = Cons a (List a) | Null

instance Eq a => Eq (List a) where
	(Cons h1 (List t1)) == (Cons h2 (List t2)) =
		if h1 == h2 then t1 == t2
		else False
	(Null a) == (Null b) = True
	(Null a) == _ = False

instance Ord a => (List a) where
	compare (Cons h1 (List t1)) (Cons h2 (List t2)) =
		-- depends on how we wanna do it  

instance Show a => (List a) where
	compare 

#proglang-f19