Functional Approach in Haskell - Ch2

Functional Approach in Haskell - Ch2 - Exercises

by @ardumont on 01 Jun 2013

Now that i know a little more about haskell, I can go and refresh my memory about algorithms but the functional way. So, I came accross functional approach in haskell which does exactly that.

Here are the first exercises (focused on haskell for the moment).

Simple

Using a haskell interpreter, evaluate the following expressions (try to predict the result): (1+2) if (2 > 9) then "hello" else "bye" let x=(sqrt 16) in x+1

(1+2)                               - 3
if (2 > 9) then "hello" else "bye"  - "bye"
let x=(sqrt 16) in x+1              -  5.0

Interpreter:

*Ch1> 1 + 2
3
*Ch1> if (2 > 9) then "hello" else "bye"
"bye"
*Ch1> let x=(sqrt 16) in x+1
5.0

Define and load the following function: fact 1 = 1 fact n = n * fact (n-1)

a) Using the interpreter, evaluate the expression fact 5 b) What happens when you try to evaluate fact 0? Alter the above definition to solve this definition. c) Modify your definition such that the value -1 is returned when an attempt is made to compute the factorial of a negative value.

*Ch1> fact 5
120

the function does not terminate
alter:

fact :: Int -> Int
fact 0 = 1
fact n = n * fact (n-1)

c) Compute factorial of a negative value must render -1:

fact :: Int -> Int
fact n
  | n < 0     = -1
  | n == 0    = 1
  | otherwise = n * fact (n-1)

*Ch1> fact 0
1
*Ch1> fact 1
1
*Ch1> fact 5
120
*Ch1> fact (-10)
-1

wrong

What is wrong with the following expressions? Can you change them to make them valid?

1:2:3 [ [2,3] ++ [], [2,3]:[] ] "hello" : "world"

*Ch1> (1:2:3:[])
[1,2,3]
*Ch1> [[[2,3] ++ []], ([2,3]:[])]
[[[2,3]],[[2,3]]]
*Ch1> "hello" ++ "world"
"helloworld"

reverse

Given the following function:

f l = reverse (f' l [])
      where f' [] r     = r
            f' (x:xs) r = (2*x) : (f' xs r)

What is the value of f [1,2,3,4]) ? Check your answer with the haskell interpreter.

Answer step by step:

f [1,2,3,4] = reverse (f' [1,2,3,4] [])
            = reverse ((2*1) : (f' [2,3,4] []))
            = reverse (2 : (2*2) : (f' [3,4] []))
            = reverse (2 : 4 : (2*3) : (f' [4] []))
            = reverse (2 : 4 : 6 : (4*2) : (f' [] []))
            = reverse (2 : 4 : 6 : 8 : [])
            = [8,6,4,2]

Interpreter:

*Ch1> f [1..4]
[8,6,4,2]

Predict

Try to predict the value of the following expressions: [1,2,3] ++ [4] 1:(2:(3:[4])) head [1,2,3] tail [1,2,3] drop 4 [1,2,3,4,5] [1,2,3,4] !! 2

[1,2,3] ++ [4]          -- [1,2,3,4]
1:(2:(3:[4]))           -- [1,2,3,4]
head [1,2,3]            -- 1
tail [1,2,3]            -- [2,3]
drop 4 [1,2,3,4,5]      -- [5]
[1,2,3,4] !! 2          -- 3

functions

Write Haskell functions for: a) computing the average value of a list of numbers; b) selecting the middle element in a list (assuming an odd-length list).

avg :: [Int] -> Int
avg xs | null xs   = 0
       | otherwise = (sum xs) `div` (length xs)

*Ch1> avg [1..10]
5
*Ch1> avg []
0

mdl :: [a] -> Maybe a
mdl xs | null xs   = Nothing
       | otherwise = Just (xs !! p)
                     where p = ((subtract 1) . (`div` 2) . length) xs

*Ch1> mdl [1..10]
Just 5
*Ch1> mdl [1..20]
Just 10
*Ch1> mdl []
Nothing

predict

a) Try to predict the value of each of the following expressions: [(x,y) | x <- [1..2], y <- [2..5], (x+y) / 4]= [x | x <- [1..10], x `mod` 2 = 0]=

All the couple (x,y), such that x in [1,2] and y in [2,3,4,5) and that x+y is not 4:

[(x,y) | x <- [1..2], y <- [2..5], (x+y) /= 4] -- [(1,2), (1,4), (1,5),
                                                   (2,3), (2,4), (2,5)]

All even numbers in [1..10]:

[x | x <- [1..10], x `mod` 2 == 0] = [2,4,6,8,10]

Interpreter:

*Ch1> [(x,y) | x <- [1..2], y <- [2..5], (x+y) /= 4]
[(1,2),(1,4),(1,5),(2,3),(2,4),(2,5)]
*Ch1> [x | x <- [1..10], x `mod` 2 == 0]
[2,4,6,8,10]

b) Define each of the following lists using a list comprehension: [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15] [2,-3,4,-5,6,-7,8,-9,10,-11]

Answer:

[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15] = [1..15]
                                      =  [x | x <- [1..15]]

*Ch1> [x | x <- [1..15]]
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]

[2,-3,4,-5,6,-7,8,-9,10,-11] = [ if odd x then -1 * x else x | x <- [2..11]]

*Ch1> [ if odd x then -1 * x else x | x <- [2..11]]
[2,-3,4,-5,6,-7,8,-9,10,-11]

list comprehension

a) Using a list comprehension, define a function neg that counts the number of negative values in a list. For example: neg [1, -9, 5, 4, -6, 0] = 3 b) Using a list comprehension, define the function rep that takes an argument n and returns a list in which 1 occurs one time, 2 occurs 2 two and so one until n occurs n time. For example: =rep 4 => [1,2,2,3,3,3,4,4,4,4]

neg :: [Int] -> Int
neg xs = sum [1 | x <- xs, x < 0 ]

*Ch1> neg [1, -9, -5, 4, -6, 0]
3

rep :: Int -> [Int]
rep n = [ y | x <- [1..n], y <- replicate x x]

*Ch1> rep 0
[]
*Ch1> rep 1
[1]
*Ch1> rep 2
[1,2,2]
*Ch1> rep 3
[1,2,2,3,3,3]
*Ch1> rep 4
[1,2,2,3,3,3,4,4,4,4]

string2int

Define a function string2int that converts a string of digits into the corresponding integer. For example: string2int "3454" = 3454 string2int "76" = 76

string2int :: String -> Int
string2int xs = sum [ ((* u) . digitToInt) x | (u, x) <- zip unit (reverse xs)]
                where unit = iterate (* 10) 1

*Ch1> string2int "123"
123
*Ch1> string2int "3434"
3434
*Ch1> string2int "3454"
3454
*Ch1> string2int "76"
76

Or we could use the standard function read :: Read a => String -> a

Predict

Try to predict the values of the following expressions:

map fst [(1,2), (3,8), (0,6), (3,1)]

(foldr f 0 l, foldl f 0 l)
  where l = [6,9,8,3,10]
        f x y = (x+y) `div` 2

foldr (++) [] [[1,2,3], [4,5,6], [], [7]]

Recall the definition of:

fst :: (a,b) -> a
fst (x,_) = x

map :: (a -> b) -> [a] -> [b]
map _ []     = []
map f (x:xs) = f x : map f xs

-- or using list comprehension:
map f xs = [ f x | x <- xs]

We can then conclude:

map fst [(1,2), (3,8), (0,6), (3,1)] = [1,3,0,3]

b) Again recall the definition of foldr:

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr _ x []     = x
foldr f x (y:ys) = f y $ foldr f x ys

Thus:

foldr f 0 l = foldr f 0 [6,9,8,3,10]
            = f 6 (foldr f 0 [9,8,3,10])
            = f 6 (f 9 (foldr f 0 [8,3,10]))
            = ...
            = f 6 (f 9 (f 8 (f 3 (f 10 0))))
            = f 6 (f 9 (f 8 (f 3 (10+0 `div` 2))))
            = f 6 (f 9 (f 8 (f 3 5)))
            = f 6 (f 9 (f 8 (3 + 4 `div` 2)))
            = f 6 (f 9 (f 8 3))
            = f 6 (f 9 5)
            = f 6 7
            = 6

Now the right operand, using foldl as operations:

foldl :: (a -> b -> a) -> a -> [b] -> a
foldl _ x []     = x
foldl f x (y:ys) = foldl f (f x y) ys

Thus (I do not forget that haskell is lazy, just bear with me)

foldl f 0 l = foldl f 0        [6,9,8,3,10]
            = foldl f (f 0 6)  [9,8,3,10]
            = foldl f (f 1 9)  [8,3,10]
            = foldl f (f 5 8)  [3,10]
            = foldl f (f 6 3)  [10]
            = foldl f (f 5 10) []
            = foldl f 7        []
            = 7

to conclude:

(foldr f 0 l, foldl f 0 l)
  where l = [6,9,8,3,10]
        f x y = (x+y) `div` 2 -- (6,7)

Indeed:

tmp :: (Integer, Integer)
tmp = (foldr f 0 l, foldl f 0 l)
  where l = [6,9,8,3,10]
        f x y = (x+y) `div` 2

*Ch1> tmp
(6,7)

type

What is the type of the following function? compose f g x = f (g x)

As we can see from the definition of compose:

f and g takes one parameter each.
f takes the output type of g as input.

We can sum up the definition of g and f:

g :: a -> b
f :: b -> c

Thus:

compose :: (b -> c) -> (a -> b) -> a -> c

Check:

compose :: (b -> c) -> (a -> b) -> a -> c
compose f g x = f (g x)

Using compose, we could redefine the string2int function from earlier:

string2int' :: String -> Int
string2int' xs = sum [ compose (* u) digitToInt x | (u, x) <- zip unit (reverse xs)]
                 where unit = iterate (* 10) 1

The standard composition function is (.)

*Ch1> :t (.)
(.) :: (b -> c) -> (a -> b) -> a -> c

matrix

Given the matrix:

2 3 4

5 6 7

8 9 10

a) Define a function that transposes a square matrix of size 3. If applied to the previous matrix, the result should be:

2 5 8

3 6 9

4 7 10

b) Extends this definition for a matrix of any size

transpose3 :: [[a]] -> [[a]]
transpose3 xs = map (\ n -> map (!! n) xs) [0..2]

*Ch1> transpose3 [[1,2,3], [4,5,6], [7,8,9]]
[[1,4,7],[2,5,8],[3,6,9]]

transpose :: [[a]] -> [[a]]
transpose xs = map (\ n -> map (!! n) xs) [0..l]
               where l = length xs - 1

*Ch1> transpose [[1,2,3], [4,5,6], [7,8,9]]
[[1,4,7],[2,5,8],[3,6,9]]
*Ch1> transpose [[1,2,3,4], [5,6,7,8], [9,10,11,12], [13,14,15,16]]
[[1,5,9,13],[2,6,10,14],[3,7,11,15],[4,8,12,16]]

type

Determine the type definitions (with the context) of the following functions:

cube x = x * x * x

maxi x y | x >= y = x
         | otherwise = y

sumAtoB a b = sum [a..b]

We must be able to compute the multiplication on x, so this must be of type Num.

cube :: Num a => a -> a
cube x = x * x * x

We must be able to compare the number, so type Ord.

maxi :: (Ord a) => a -> a -> a
maxi x y | x >= y = x
         | otherwise = y

We must be able to compute the sum, so Num type and use a list comprehension, so Enum type.

sumAtoB :: (Num a, Enum a) => a -> a -> a
sumAtoB a b = sum [a..b]