- type error: lists are homogenous
=> (a, Char)
- type error: cannot add values of different types
(a,b) -> b
[a] -> a
[a] -> Bool
[a] -> a
[[a]] -> a
That Pesky IO TypeEdit
Explicit Type DeclarationsEdit
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
a, it must be an instance of
a -> String, or
a -> [Char]. This ignores the first argument, so it can be any type.
(Char -> a) -> a. In this expression,
xmust be a function which takes a
Charas an argument. We don't know anything about what it produces, though, so we call it
- Type error. Here, we assume
xis applied to itself, so it must have type
b -> c. But then it must have type
(b -> c) -> c, but then it must have type
((b -> c) -> c) -> cand so on, leading to an infinite type.
(Num a) => a -> a. Again, since we apply
(+), this must be an instance of
The 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,
b associated with
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
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
Eithers to represent the fact that there are four (instead of two) options.
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)
elements (Leaf x) = [x] elements (Branch lhs x rhs) = elements lhs ++ [x] ++ elements rhs
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 (:) 
elements2 tree = treeFoldr (\a b -> a:b)  tree
elements2 is simply a more compact version of the second.
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
The Unit typeEdit
Continuation Passing StyleEdit
It mimicks neither exactly. It's behavior most closely resembles
foldr, but differs slightly in its treatment of the initial value. We can observe the difference in an interpreter:
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
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) ) ==> 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.
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
map2 f = map' (\x y -> (:) (f x) y) map2 f = map' (\x -> (:) (f x)) map2 f = map' (\x -> ((:) . f) x) map2 f = map' ((:) . f)
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