Yet Another Haskell Tutorial/Type basics/Solutions
Simple Types
editString
or[Char]
- type error: lists are homogenous
Num
{a}=> (a, Char)
Int
- type error: cannot add values of different types
Polymorphic Types
editThe types:
(a,b) -> b
[a] -> a
[a] -> Bool
[a] -> a
[[a]] -> a
Type Classes
editMotivation
editEquality Testing
editThe Num Class
editThe Show Class
editFunction Types
editLambda Calculus
editHigher-Order Types
editThat Pesky IO Type
editExplicit Type Declarations
editFunctional Arguments
editThe types:
a -> [a]
. This function takes an element and returns the list containing only that element.a -> b -> b -> (a,[b])
. The second and third argument must be of the same type, since they go into the same list. The first element can be of any type.(Num a) => a -> a
. Since we apply(+)
toa
, it must be an instance ofNum
.a -> String
, ora -> [Char]
. This ignores the first argument, so it can be any type.(Char -> a) -> a
. In this expression,x
must be a function which takes aChar
as an argument. We don't know anything about what it produces, though, so we call ita
.- Type error. Here, we assume
x
has typea
. Butx
is applied to itself, so it must have typeb -> c
. But then it must have type(b -> c) -> c
, but then it must have type((b -> c) -> c) -> c
and so on, leading to an infinite type. (Num a) => a -> a
. Again, since we apply(+)
, this must be an instance ofNum
.
Data Types
editPairs
editThe definitions will be something like:
data Triple a b c = Triple a b c tripleFst (Triple x y z) = x tripleSnd (Triple x y z) = y tripleThr (Triple x y z) = z
The code, with type signatures, is:
data Quadruple a b = Quadruple a a b b firstTwo :: Quadruple a b -> [a] firstTwo (Quadruple x y z t) = [x,y] lastTwo :: Quadruple a b -> [b] lastTwo (Quadruple x y z t) = [z,t]
We note here that there are only two type variables, a
and b
associated with Quadruple
.
Multiple Constructors
editThe code:
data Tuple a b c d = One a | Two a b | Three a b c | Four a b c d tuple1 (One a ) = Just a tuple1 (Two a b ) = Just a tuple1 (Three a b c ) = Just a tuple1 (Four a b c d) = Just a tuple2 (One a ) = Nothing tuple2 (Two a b ) = Just b tuple2 (Three a b c ) = Just b tuple2 (Four a b c d) = Just b tuple3 (One a ) = Nothing tuple3 (Two a b ) = Nothing tuple3 (Three a b c ) = Just c tuple3 (Four a b c d) = Just c tuple4 (One a ) = Nothing tuple4 (Two a b ) = Nothing tuple4 (Three a b c ) = Nothing tuple4 (Four a b c d) = Just d
The code:
fromTuple :: Tuple a b c d -> Either (Either a (a,b)) (Either (a,b,c) (a,b,c,d)) fromTuple (One a ) = Left (Left a ) fromTuple (Two a b ) = Left (Right (a,b) ) fromTuple (Three a b c ) = Right (Left (a,b,c) ) fromTuple (Four a b c d) = Right (Right (a,b,c,d))
Here, we use embedded Either
s to represent the fact that there
are four (instead of two) options.
Recursive Datatypes
editThe code:
listHead (Cons x xs) = x listTail (Cons x xs) = xs listFoldl f y Nil = y listFoldl f y (Cons x xs) = listFoldl f (f y x) xs listFoldr f y Nil = y listFoldr f y (Cons x xs) = f x (listFoldr f y xs)
Binary Trees
editThe code:
elements (Leaf x) = [x] elements (Branch lhs x rhs) = elements lhs ++ [x] ++ elements rhs
The code:
treeFoldr :: (a -> b -> b) -> b -> BinaryTree a -> b treeFoldr f i (Leaf x) = f x i treeFoldr f i (Branch left x right) = treeFoldr f (f x (treeFoldr f i right)) left elements2 = treeFoldr (:) []
or:
elements2 tree = treeFoldr (\a b -> a:b) [] tree
The first elements2
is simply a more compact version of the
second.
The code:
treeFoldl :: (a -> b -> a) -> a -> BinaryTree b -> a treeFoldl f i (Leaf x) = f i x treeFoldl f i (Branch left x right) = treeFoldl f (f (treeFoldl f i left) x) right elements3 t = treeFoldl (\i a -> i ++ [a]) [] t
Enumerated Sets
editThe Unit type
editContinuation Passing Style
editIt mimicks neither exactly. Its behavior most closely resembles
foldr
, but differs slightly in its treatment of the initial
value. We can observe the difference in an interpreter:
Example:
CPS> foldr (-) 0 [1,2,3] 2 CPS> foldl (-) 0 [1,2,3] -6 CPS> fold (-) 0 [1,2,3] -2
Clearly it behaves differently. By writing down the derivations of
fold
and foldr
we can see exactly where they diverge:
foldr (-) 0 [1,2,3] ==> 1 - foldr (-) 0 [2,3] ==> ... ==> 1 - (2 - (3 - foldr (-) 0 [])) ==> 1 - (2 - (3 - 0)) ==> 2 fold (-) 0 [1,2,3] ==> fold' (-) (\y -> 0 - y) [1,2,3] ==> 0 - fold' (-) (\y -> 1 - y) [2,3] ==> 0 - (1 - fold' (-) (\y -> 2 - y) [3]) ==> 0 - (1 - (2 - 3)) ==> -2
Essentially, the primary difference is that in the foldr
case,
the "initial value" is used at the end (replacing []
), whereas
in the CPS case, the initial value is used at the beginning.
The function map
in CPS:
map' :: (a -> [b] -> [b]) -> [a] -> [b] map' f [] = [] map' f (x:xs) = f x (map' f xs) map2 :: (a -> b) -> [a] -> [b] map2 f l = map' (\x y -> f x : y) l
Point elimination:
map2 f = map' (\x y -> (:) (f x) y) map2 f = map' (\x -> (:) (f x)) map2 f = map' (\x -> ((:) . f) x) map2 f = map' ((:) . f)
The function filter
in CPS: (needs to be double checked)
filter' :: (a -> [b] -> [b]) -> [a] -> [b] filter' f [] = [] filter' f (x:xs) = f x (filter' f xs) filter2 :: (a -> Bool) -> [a] -> [a] filter2 f l = filter' (\x y -> if (f x) then x:y else y) l