Typeclasses
Typeclasses
Question 1
Num a => a. Because all of1,2and3can be interpreted as any number, the entire expression can likewise be interpreted as any number.Show b => (a -> b) -> a -> String. The type ofshowisShow a => a -> String, in other words, any type that implements theShowtypeclass can be converted into aString. Therefore,(show .)can receive any functiona -> bwherebimplementsShow, so that the result is a function that receivesaand producesStringShow a => (String -> b) -> a -> b. Similar to the above.Eq a => (a, a) -> Bool. The elements of the tuple must be amenable to equality comparisons, and therefore must be of the same typeawhereaimplementsEq.
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]
@dataclassclass Empty: def to_list(self) -> list[Any]: return []
@dataclassclass ListNode[a]: head: a tail: List[a] def to_list(self) -> list[a]: return [self.head] + self.tail.to_list()
@dataclassclass 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 => asmallest = minBoundThe 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 -> aaverage x y = toEnum $ (fromEnum x + fromEnum y) `div` 2Question 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 ysQuestion 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 claritytype IntExpr e = Expr e Inttype BoolExpr e = Expr e BoolThen, 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) = xAddExpr 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 e2To 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 e2Finally, 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 e2Question 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 -> sIn 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)