Skip to content

Typeclasses

Typeclasses

Question 1

  1. Num a => a. Because all of 1, 2 and 3 can be interpreted as any number, the entire expression can likewise be interpreted as any number.
  2. Show b => (a -> b) -> a -> String. The type of show is Show a => a -> String, in other words, any type that implements the Show typeclass can be converted into a String. Therefore, (show .) can receive any function a -> b where b implements Show, so that the result is a function that receives a and produces String
  3. Show a => (String -> b) -> a -> b. Similar to the above.
  4. Eq a => (a, a) -> Bool. The elements of the tuple must be amenable to equality comparisons, and therefore must be of the same type a where a implements Eq.

Question 2

The idea is to create a protocol that describes classes that have a to_list function. In the following solution, the protocol is called ToList.

from typing import Any
type Tree[a] = Empty | TreeNode[a]
type List[a] = Empty | ListNode[a]
@dataclass
class Empty:
def to_list(self) -> list[Any]:
return []
@dataclass
class ListNode[a]:
head: a
tail: List[a]
def to_list(self) -> list[a]:
return [self.head] + self.tail.to_list()
@dataclass
class TreeNode[a]:
l: Tree[a]
v: a
r: Tree[a]
def to_list(self) -> list[a]:
return self.l.to_list() + [self.v] + self.r.to_list()
class ToList[a](Protocol):
def to_list(self) -> list[a]:
raise
def flatten[a](ls: list[ToList[a]]) -> list[a]:
if not ls: return []
return ls[0].to_list() + flatten(ls[1:])
ls: list[ToList[int]] = [ListNode(1, Empty()), TreeNode(Empty(), 2, Empty())]
ls2: list[int] = flatten(ls)

Question 3

The smallest function can be implemented directly with the minBound method of the Bounded typeclass:

smallest :: Bounded a => a
smallest = minBound

The descending function can also be implemented directly with the Bounded and Enum methods. The idea is to construct a range (which requires Enum) starting from maxBound and enumerating all the way to minBound. You can either construct a range starting from minBound to maxBound and then reverse the list, or you can start from maxBound, followed by pred maxBound (pred comes from Enum), and end at minBound.

descending :: (Bounded a, Enum a) => [a]
descending = [maxBound,pred maxBound..minBound]

The average function can be implemented by converting the two terms to integers using fromEnum, then take the average, and use toEnum to bring it back to the desired term.

average :: Enum a => a -> a -> a
average x y = toEnum $ (fromEnum x + fromEnum y) `div` 2

Question 4

Any list of elements that can be ordered, i.e. any list over a type implementing Ord can be sorted!

import Data.List (splitAt)
mergesort :: Ord a => [a] -> [a]
mergesort ls
| len <= 1 = ls
| otherwise = let (l, r) = splitAt (len `div` 2) ls
l' = mergesort l
r' = mergesort r
in merge l' r'
where len :: Int
len = length ls
merge :: Ord a => [a] -> [a] -> [a]
merge [] x = x
merge x [] = x
merge l@(x : xs) r@(y : ys)
| x <= y = x : merge xs r
| otherwise = y : merge l ys

Question 5

Before we even begin, it will be helpful to decide what our typeclass will look like. The typeclass should be abstracted over the type of expression and the type from evaluating it. Therefore, it should be something like Expr e a, where eval :: e -> a. However, we know that e uniquely characterizes a, therefore we should add this as a functional dependency of our typeclass.

class Expr e a | e -> a
eval :: e -> a
-- for clarity
type IntExpr e = Expr e Int
type BoolExpr e = Expr e Bool

Then, our types will all contain types that implement the Expr typeclass.

First, to start we have numeric literals, which is straightforward.

data LitNumExpr = LitNumExpr Int
instance Expr LitNumExpr Int where
eval :: LitNumExpr -> Int
eval (LitNumExpr x) = x

AddExpr is more interesting. We require that the component expressions must be evaluated to an Int. As such, we constrain the component addends with IntExpr as follows:

data AddExpr where
AddExpr :: (IntExpr e, IntExpr e') => e -> e' -> AddExpr
instance Expr AddExpr Int where
eval :: AddExpr -> Int
eval (AddExpr e1 e2) = eval e1 + eval e2

To define EqExpr, we have to allow expressions of any type that evaluates to any type that is amenable to equality comparisons:

data EqExpr where
EqExpr :: (Eq a, Expr e a, Expr e' a) => e -> e' -> EqExpr
instance Expr EqExpr Bool where
eval :: EqExpr -> Bool
eval (EqExpr e1 e2) = eval e1 == eval e2

Finally, to define a CondExpr we must allow it to evaluate to any type, and thus should be parameterized.

data CondExpr a where
CondExpr :: (BoolExpr c, Expr e a, Expr e' a)
=> c -> e -> e' -> CondExpr a
instance Expr (CondExpr a) a where
eval :: CondExpr a -> a
eval (CondExpr c e1 e2) = if eval c then eval e1 else eval e2

Question 6

As per usual, we are going to define a typeclass Sequence that defines the methods @, len and prepend. The type parameters of Sequence is tricky. One possibility is for Sequence to be higher-kinded:

class Sequence e s where
(@) :: s e -> Int -> e
len :: s e -> Int
prepend :: s e -> e -> s e
instance Sequence [] a where
-- ...

However, this will not work when having Ints as sequences because Int is not a type constructor. Therefore, we will just let s be the full sequence type, and introduce a functional dependency s -> e so that the sequence type s uniquely characterizes the type of the elements of that sequence:

class Sequence e s | s -> e where
(@) :: s -> Int -> e
len :: s -> Int
prepend :: s -> e -> s

In which case, the Sequence instances for [a] and Int becomes quite straightforward:

instance Sequence a [a] where
(@) :: [a] -> Int -> a
(@) = (!!)
len :: [a] -> Int
len = length
prepend :: [a] -> a -> [a]
prepend = flip (:)
instance Sequence () Int where
(@) :: Int -> Int -> ()
i @ j
| j < 0 || j >= i = undefined
| otherwise = ()
len :: Int -> Int
len = id
prepend :: Int -> () -> Int
prepend = const . (+1)