A Haskell Walkthrough | Study with Ch'i YU

Brief solutions of most chapters in Programming in Haskell.

Hutton, G., 2007. Programming in Haskell, Cambridge, UK ; New York: Cambridge University Press.

Chapter 1 Introduction

Give another possible calculation for the result of double (double 2).

-- Innermost Method:
double (double 2)
= double (2 + 2)
= (2 + 2) + (2 + 2)
= 4 + 4
= 9

-- Outermost Method:
double (double 2)
= (double 2) + (double 2)
= (double 2) + (2 + 2)
= (double 2) + 4
= (2 + 2) + 4
= 4 + 4
= 8

Show that sum [x] = x for any number x.
1
2
3
4
sum [x]
= x + sum []
= x + 0
= x

Define a function product that produces the product of a list of numbers, and show using your definition that product [2,3,4] = 24.

product [] = 1
product (x:xs) = x * product xs
-------------------------------
product [2, 3, 4]
= 2 * product [3, 4]
= 2 * 3 * product [4]
= 2 * 3 * 4 * product []
= 2 * 3 * 4 * 1
= 24

How should the definition of the function qsort be modified so that it produces a reverse sorted version of a list?

1
2
3

qsort' :: Ord(a) => [a] -> [a]
qsort' [] = []
qsort' (x:xs) = qsort' [a | a <- xs, a > x] ++ [x] ++ [b | b <- xs, b <= x]

What would be the effect of replacing <= by < in the original definition of qsort? Hint: consider the example qsort [2,2,3,1,1]

A: Any duplicate elements/items will be lost. e.g. qsort'' [2,2,3,1,1] returns [1, 2, 3] only rather than [1,1,2,2,3].

Chapter 2 First Steps

~~Work through the examples from this chapter using GHCi.~~

Skipped.
Parenthesise the following numeric expressions:

2 ^ 3 * 4 -> (2 ^ 3) * 4

2 * 3 + 4 * 5 -> (2 * 3) + (4 * 5)

2 + 3 * 4 ^ 5 -> 2 + (3 * (4 ^ 5))

The script below contains three syntactic errors. Correct these errors and then check that your script works properly using GHCi.

-- Original Script:
N = a 'div' length xs
      where
          a = 10
         xs = [1,2,3,4,5]
-- Fixed Script:
n = a `div` length xs
    where
      a = 10
      xs = [1,2,3,4,5]
-- Note:
-- 1. Function should start with lowercase letters;
-- 2. Use `(Same key for ~ on keyboard) nontation for a Function-Alias;
-- 3. Align the (1st letter of)variables, not the equations.

The library function last selects the last element of a non-empty list; for example, last [1,2,3,4,5] = 5. Show how the function last could be defined in terms of the other library functions introduced in this chapter. Can you think of another possible definition?
1
2
3
4
-- last :: [a] -> a
last' xs = head (reverse xs)
last'' xs = head (drop (length xs - 1) xs)
last''' xs = xs !! (length xs - 1)
The library function init removes the last element from a non-empty list; for example, init [1,2,3,4,5] = [1,2,3,4]. Show how init could similarly be defined in two different ways.
1
2
3
-- init :: [a] -> [a]
init' xs = take (length xs - 1) xs
init'' xs = reverse (tail (reverse xs))

Chapter 3 Types and Classes

What are the types of the following values?

['a', 'b', 'c'] :: [Char]
('a', 'b', 'c') :: (Char, Char, Char)
[(False,'O'),(True,'1')] ::[(Bool, Char)]
([False,True],['0','1']) :: ([Bool], [Char])
[tail, init, reverse] :: [[Char]]

Write down definitions that have the following types; it does not matter what the definitions actually do as long as they are type correct.

bools :: [Bool]
bools = [True, False, False, True]

nums :: [[Int]]
nums = [[1], [1,2], [1,2,3]]

add' :: Int -> Int -> Int -> Int
add' x y z = x + y + z

copy' :: a -> (a, a)
copy' x = (x, x)

apply' :: (a -> b) -> a -> b
apply' a b = a b

What are the types of the following functions?

second :: [a] -> a
second xs = head (tail xs)

swap :: (a,b) -> (b,a)
swap (x,y) = (y,x)

pair :: a -> b -> (a, b)
pair x y = (x,y)

exDouble :: Num a => a -> a
exDouble x = x*2

palindrome :: String -> Bool
palindrome xs = reverse xs == xs

~~Check your answers to the preceding three questions using GHCi.~~

Skipped.
Why is it not feasible in general for function types to be instances of the Eq class? When is it feasible?

Hint: two functions of the same type are equal if they always return equal results for equal arguments.

A1: Their results may not be instances of the Eq class; It may be impossible to compare every pair of inputs and outputs in scope; A2: Feasible if the functions return same type of instance of the Eq class, and the scope is limited with finite pairs of inputs and outputs.

Chapter 4 Defining Functions(WIP)

Using library functions, define a function halve :: [a] -> ([a],[a]) that splits an even-lengthed list into two halves. For example:
Define a function third :: [a] -> a that returns the third element in a list that contains at least this many elements using:
Consider a function safetail :: [a] -> [a] that behaves in the same way as tail except that it maps the empty list to itself rather than producing an error. Using tail and the function null :: [a] -> Bool that decides if a list is empty or not, define safetail using:
In a similar way to && in section 4.4, show how the disjunction operator || can be defined in four different ways using pattern matching.
Without using any other library functions or operators, show how the meaning of the following pattern matching definition for logical conjunction && can be formalised using conditional expressions:

Hint: use two nested conditional expressions.
Do the same for the following alternative definition, and note the difference in the number of conditional expressions that are required:
Show how the meaning of the following curried function definition can be formalised in terms of lambda expressions:
The Luhn algorithm is used to check bank card numbers for simple errors such as mistyping a digit, and proceeds as follows:

Chapter 5 List Comprehensions(WIP)

Chapter 6 Recursive Functions

How does the recursive version of the factorial function behave if applied to a negative argument, such as (-1)?

Modify the definition to prohibit negative arguments by adding a guard to the recursive case.
1
2
3
4
fact' :: Int -> Int
fact' 0 = 1
fact' n | n > 0 = n * fact' (n - 1)
| otherwise error "Cannot Applied to Negative Arguments"
Define a recursive function sumdown :: Int -> Int that returns the sum of the non-negative integers from a given value down to zero.

For example, sumdown 3 should return the result 3+2+1+0 = 6.
1
2
3
sumdown :: Int -> Int
sumdown :: n | n < 0 = 0
| n > 0 = n + sumdown (n - 1)

Define the exponentiation operator ^ for non-negative integers using the same pattern of recursion as the multiplication operator *, and show how the expression 2 ^ 3 is evaluated using your definition.

(^!) :: Int -> Int -> Int
m ^! n | n <= 0 = 1
       | n > 0  = m * (m *! (n - 1))
-------------------------------------------------
(*!) :: Int -> Int -> Int
m *! n | n <= 0 = 0
       | n > 0  = m + (m *! (n - 1))

Define a recursive function euclid :: Int -> Int -> Int that implements Euclid’s algorithm for calculating the greatest common divisor of two non-negative integers: if the two numbers are equal, this number is the result; otherwise, the smaller number is subtracted from the larger, and the same process is then repeated.

For example: $ > euclid 6 27

$ > 3
1
2
3
4
5
euclid :: Int -> Int -> Int
euclid m n | m <= 0, n <= 0 = 0
| m == m = m
| m < n = euclid m (n - m)
| m > n = euclid (m - n) m

Using the recursive definitions given in this chapter, show how length [1,2,3], drop 3 [1,2,3,4,5], and init [1,2,3] are evaluated.

length [1,2,3]
= 1 + length [2,3]
= 1 + 1 + length [3]
= 1 + 1 + 1 + length []
= 1 + 1 + 1 + 0
= 3
-------------------------------------
drop 3 [1,2,3,4,5]
= drop 2 [2,3,4,5]
= drop 1 [3,4,5]
= drop 0 [4,5]
= [4,5]
-------------------------------------
init [1,2,3]
= [1] ++ init [2,3]
= [1] ++ [2] ++ init [3]
= [1] ++ [2] ++ []
= [1,2]

Without looking at the definitions from the standard prelude, define the following library functions on lists using recursion.

Decide if all logical values in a list are True: and :: [Bool] -> Bool

    and' :: [Bool] -> Bool
    and' [] = True
    and' (x:xs) = x && and' xs 

- Concatenate a list of lists:
    `concat :: [[a]] -> [a]`

    ```haskell
    concat' :: [[a]] -> [a]
    concat' [] = []
    concat' (x:xs) = x ++ concat' xs

- Produce a list with n identical elements:
    `replicate :: Int -> a -> [a]`

    ```haskell
    replicate' :: Int -> a -> [a]
    replicate' 0 _ = [] 
    replicate' n x = x : replicate' (n - 1) x

Select the nth element of a list: (!!) :: [a] -> Int -> a

    (!!!) :: [a] -> Int -> a
    (x:xs) :: 0                              = x
    (x:xs) :: n | n > 0, n < = length (x:xs) = xs !!! (n - 1)
                | otherwise error "Invalid Index"

- Decide if a value is an element of a list:
    `elem :: Eq a => a -> [a] -> Bool`

    ```haskell
    elem' :: Eq a => a -> [a] -> Bool
    elem' _ []               = False
    elem' a x:xs | a == x    = True
                 | otherwise = elem' a xs

Note: most of these functions are defined in the prelude using other library functions rather than using explicit recursion, and are generic functions rather than being specific to the type of lists.

Define a recursive function merge :: Ord a => [a] -> [a] -> [a] that merges two sorted lists to give a single sorted list.

For example: $ > merge [2,5,6] [1,3,4]

$ > [1,2,3,4,5,6]
1
2
3
4
5
6
merge' :: Ord a => [a] -> [a] -> [a]
merge' [] [] = []
merge' xs [] = xs
merge' [] ys = ys
merge' (x:xs) (y:ys) | x < y = x : merge' xs (y:ys)
| otherwise = y : merge' (x:xs) ys
Note: your definition should not use other functions on sorted lists such as insert or isort, but should be defined using explicit recursion.

Using merge, define a function msort :: Ord a => [a] -> [a] that implements merge sort, in which the empty list and singleton lists are already sorted, and any other list is sorted by merging together the two lists that result from sorting the two halves of the list separately.

halve' :: [a] -> ([a], [a])
halve' xs = splitAt ((length xs) `div` 2) xs

msort' :: Ord a => [a] -> [a]
msort' []  = []
msort' [x] = [x]
msort' xs  = merge (sortMerge (fst (halve2 xs))) (sortMerge (snd (halve2 xs))) 
-------------------------------------------------------------------------
msort'' :: Ord a => [a] -> [a]
msort'' [] = []
msort'' [a] = [a]
msort'' xs = merge (msort'' (firstHalf xs)) (msort'' (secondHalf xs))

firstHalf  xs = let { n = length xs } in take (div n 2) xs

secondHalf xs = let { n = length xs } in drop (div n 2) xs

Hint: first define a function halve :: [a] -> ([a],[a]) that splits a list into two halves whose lengths differ by at most one.

Using the five-step process, construct the library functions that:

Calculate the sum of a list of numbers

1
2
3

sum' :: NUM a => [a] -> a
sum' [] = 0
sum' (x:xs) = x + sum' xs

Take a given number of elements from the start of a list;

    takes' :: Int -> [a] -> [a]
    takes' 0 xs = []
    takes' _ [] = []
    takes' n (x:xs) | n < 0  = []
                   | n >= 0 = x: takes' (n - 1) xs

- Select the last element of a non-empty list.

    ```haskell
    last' :: [a] -> a
    last' [x] = x
    last' (x:xs) = last' xs

Chapter 7 Higher-Order Functions

Show how the list comprehension [f x | x <- xs, p x]can be re-expressed using the higher-order functions map and filter.
1
2
filmap :: [a] -> (a -> Bool) -> (a -> b) -> [b]
filmap xs p f = map f (filter p xs)
Without looking at the definitions from the standard prelude, define the following higher-order library functions on lists:

Note: in the prelude the first two of these functions are generic functions rather than being specific to the type of lists.
- Decide if all elements of a list satisfy a predicate: all :: (a -> Bool) -> [Bool] -> Bool
  1
  2
  3
  4
  5
  -- Recursive Method
  all' p [] = True
  all' p (x:xs) = (p x) && (all' p xs)
  -- Advanced Method
  all'' p = map and p
- Decide if any element of a list satisfies a predicate: any :: (a -> Bool) -> [Bool] -> Bool
  1
  2
  3
  4
  5
  -- Recursive Method
  any' p [] = False
  any' p (x:xs) = (p x) || (any' p xs)
  -- Advanced Method
  any'' p = map or p
- Select elements from a list while they satisfy a predicate: takeWhile :: (a -> Bool) -> [a] -> [a]
  1
  2
  3
  4
  -- Recursive Method
  takeWhile' _ [] = []
  takeWhile' p (x:xs) | p x = x : takeWhile' p xs
  | otherwise = []
- Remove elements from a list while they satisfy a predicate: dropWhile :: (a -> Bool) -> [a] -> [a]
  1
  2
  3
  4
  -- Recursive Method
  dropWhile' _ [] = []
  dropWhile' p (x:xs) | p x = dropWhile' p xs
  | otherwise = x : xs

Redefine the functions map f and filter p using foldr.

-- Lamda Calculus Method
maps' :: (a -> b) -> [a] -> [b]
maps' f = foldr (\x xs -> f x : xs) []

filters' :: (a -> Bool) -> [a] -> [b]
filters' :: foldr (\x xs -> if p x then x : xs else xs) []

Using foldl, define a functiondec2int :: [Int] -> Intthat converts a decimal number into an integer.

For example: $ > dec2int [2,3,4,5]

$ > 2345
1
2
dec2int :: [Int] -> Int
dec2int = foldl (\x y -> 10 * x + y) 0
Without looking at the definitions from the standard prelude, define the higher-order library function curry that converts a function on pairs into a curried function, and, conversely, the function uncurry that converts a curried function with two arguments into a function on pairs.

Hint: first write down the types of the two functions.
1
2
3
4
5
curry :: ((a, b) -> t) -> a -> b -> t
curry f = \x y -> f (x, y)

uncurry :: (a -> b -> t) -> (a, b) -> t
uncurry f = \(x, y) -> f x y

A higher-order function unfold that encapsulates a simple pattern of recursion for producing a list can be defined as follows:

1 2	unfold p h t x \| p x = [] \| otherwise = h x : unfold p h t (t x)

That is, the function unfold p h tproduces the empty list if the predicate p is true of the argument value, and otherwise produces a non-empty list by applying the function h to this value to give the head, and the function t to generate another argument that is recursively processed in the same way to produce the tail of the list.

For example, the function int2bin can be rewritten more compactly using unfold as follows: int2bin = unfold (== 0) (‘mod‘ 2) (‘div‘ 2)

Redefine the functions chop8, map f and iterate f using unfold.

chop8 :: [Char] -> [[Char]]
chop8 = unfold (== []) (take 8) (drop 8) 

map' :: Eq b => (b -> a) -> [b] -> [a]:t 
map' f = unfold (== []) (f . head) (tail)

-- Iterate while True
iterateTrue' :: (Bool -> Bool) -> Bool -> [Bool]
iterateTrue' f = unfold (== False) id f

-- Iterate while False
iterateFalse' :: (Bool -> Bool) -> Bool -> [Bool]
iterateFalse' f = unfold (== True) id f

-- Note: id is an identity function of type a -> a.
-- Note: dot (.) is the operator composes functions.
-- e.g. f (g x) == (f . g) x

Modify the binary string transmitter example to detect simple transmission errors using the concept of parity bits. That is, each eight-bit binary number produced during encoding is extended with a parity bit, set to one if the number contains an odd number of ones, and to zero otherwise. In turn, each resulting nine-bit binary number consumed during decoding is checked to ensure that its parity bit is correct, with the parity bit being discarded if this is the case, and a parity error being reported otherwise.

Hint: the library function error :: String -> a displays the given string as an error message and terminates the program; the polymorphic result type ensures that error can be used in any context.

-- Extend with Parity Bit
enparify :: [Int] -> [Int]
enparify [] = []
enparify xs | even (sum xs) = xs ++ [0]
            | otherwise     = xs ++ [1]

-- Decode with Parity Bit
deparify :: [Int] -> [Int]
deparify [] = []
deparify xs | even (sum (init xs)) && (last xs == 0) = init xs
            | odd (sum (init xs)) && (last xs == 1)  = init xs
            | otherwise                 = error "Parity Error"

Test your new string transmitter program from the previous exercise using a faulty communication channel that forgets the first bit, which can be modelled using the tail function on lists of bits.
1
2
3
parityTransmit :: String -> String
parityTransmit [] = []
parityTransmit xs = map snd (filter (\(index, _) -> index `mod` 9 /= 0) $ zip [0..] xs)
Define a function altMap :: (a -> b) -> (a -> b) -> [a] -> [b] that alternately applies its two argument functions to successive elements in a list, in turn about order.

For example:

$ > altMap (+10) (+100) [0,1,2,3,4]

$ > [10,101,12,103,14]
1
2
3
4
5
altMap :: (a -> b) -> (a -> b) -> [a] -> [b]
altMap _ _ [] = []
altMap f _ (x0:[]) = f x0 : []
altMap f g (x0:x1:[]) = f x0 : g x1 : []
altMap f g (x0:x1:xs) = f x0 : g x1 : altMap f g xs

Using altMap, define a function luhn :: [Int] -> Bool that implements the Luhn algorithm from the exercises in chapter 4 for bank card numbers of any length.

Test your new function using your own bank card.

-- Pseudo-Code
function checkLuhn(string purportedCC) 
{
	int sum := integer(purportedCC[length(purportedCC)-1])
	int nDigits := length(purportedCC)
	int parity := nDigits modulus 2
	for i from 0 to nDigits - 2
    {
    	int digit := integer(purportedCC[i])
    	if i modulus 2 = parity
        	digit := digit × 2
		if digit > 9
			digit := digit - 9
        sum := sum + digit
    }
    return (sum modulus 10) = 0
}
--------------------------------------------------------

-- Haskell Solution
luhnCalculus :: Int -> Int
luhnCalculus x | x * 2 < 9 = 9
               | otherwise = (x * 2 - 9)
luhn xs | (sum (map luhnCalculus xs) mod 10) == 0 = True
        | otherwise = False