Yet Another Haskell Tutorial/Type basics/Solutions

From Wikibooks, open books for an open world
Jump to navigation Jump to search
Haskell
Yet Another Haskell Tutorial
Preamble
Introduction
Getting Started
Language Basics (Solutions)
Type Basics (Solutions)
IO (Solutions)
Modules (Solutions)
Advanced Language (Solutions)
Advanced Types (Solutions)
Monads (Solutions)
Advanced IO
Recursion
Complexity

Simple Types[edit | edit source]

  1. String or [Char]
  2. type error: lists are homogenous
  3. Num{a} => (a, Char)
  4. Int
  5. type error: cannot add values of different types

Polymorphic Types[edit | edit source]

The types:

  1. (a,b) -> b
  2. [a] -> a
  3. [a] -> Bool
  4. [a] -> a
  5. [[a]] -> a

Type Classes[edit | edit source]

Motivation[edit | edit source]

Equality Testing[edit | edit source]

The Num Class[edit | edit source]

The Show Class[edit | edit source]

Function Types[edit | edit source]

Lambda Calculus[edit | edit source]

Higher-Order Types[edit | edit source]

That Pesky IO Type[edit | edit source]

Explicit Type Declarations[edit | edit source]

Functional Arguments[edit | edit source]

The types:

  1. a -> [a]. This function takes an element and returns the list containing only that element.
  2. 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.
  3. (Num a) => a -> a. Since we apply (+) to a, it must be an instance of Num.
  4. a -> String, or a -> [Char]. This ignores the first argument, so it can be any type.
  5. (Char -> a) -> a. In this expression, x must be a function which takes a Char as an argument. We don't know anything about what it produces, though, so we call it a.
  6. Type error. Here, we assume x has type a. But x is 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) -> c and so on, leading to an infinite type.
  7. (Num a) => a -> a. Again, since we apply (+), this must be an instance of Num.

Data Types[edit | edit source]

Pairs[edit | edit source]

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, a and b associated with Quadruple.

Multiple Constructors[edit | edit source]

The 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 Eithers to represent the fact that there are four (instead of two) options.

Recursive Datatypes[edit | edit source]

The 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[edit | edit source]

The 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[edit | edit source]

The Unit type[edit | edit source]

Continuation Passing Style[edit | edit source]

It 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