Solved problems : Higher Order Functions

Problem 1

Implement a function eql :: [Int] -> [Int] -> Bool that tells whether two lists of integers are equal.

eql [1, 2, 3] [1, 2, 3]     -- True
eql [1, 2, 3] [3, 2, 1]     -- False
eql [1, 2, 3] [1, 2, 3, 4]  -- False

eql :: [Int] -> [Int] -> Bool

eql x y
    | length x /= length y = False
    | otherwise = and $ zipWith (==) x y

-- With the dollar sign, we can make sure that the list is first built by zipWith, before the function 'and' is applied.

Problem 2

Implement a function prod :: [Int] -> Int that returns the product of a list of integers. (custom implementation of product)

prod [2, 10, 5]     -- 100
prod [3, 1, 2, 4]   -- 24

We will use an important function from Haskell : foldl. L stands for left because we start folding with n from the left.

Type: (a -> b -> a) -> a -> [b] -> a Input: foldl (/) 64 [4, 2, 4] Output: 2.0

prod :: [Int] -> Int

prod x = foldl (*) 1 x

prod = foldl (*) 1 -- This is implicit notation

Problem 3

Implement a function prodEvens :: [Int] -> Int that returns the product of all even numbers of a list of integers.

prodEvens [2, 10, 5]    -- 20
prodEvens [3, 1, 2, 4]  -- 8

prod :: [Int] -> Int
prod = foldl (*) 1

prodEvens :: [Int] -> Int
prodEvens = prod . filter even      -- with implicit notation

prodEvens l = prod (filter even l)  -- explicit notation

Problem 4

Implement a function powersOf2 :: [Int] that generates that list of all the powers of 2.

take 5 powersOf2        -- [1, 2, 4, 8, 16]
take 3 powersOf2        -- [1, 2, 4]

There is a standard function called iterate which returns an infinite list.

powersOf2 :: [Int]
powersOf2 = iterate (*2) 1

Problem 5

Implement a function scalarProduct :: [Float] -> [Float] -> Float that returns the dot product of two lists of float numbers with the same size.

scalarProduct [2.0, 1.0, 5.0] [3.0, 2.0, 2.0] -- 18.0
scalarProduct [3.0, 4.0] [5.0, 3.0]           -- 27.0

We want to do:

l1 = [x, y, z]
l2 = [a, b, c]

dot product = x * a + y * b + z * c

-> l3 = [x * a, y * b, z * c]
sum l3

scalarProduct :: [Float] -> [Float] -> Float
scalarProduct x y = sum $ zipWith (*) x y

Problem 6

Implement a function flatten :: [[Int]] -> [Int] that flattens a list of lists of integers in a list of integers.

flatten [[1, 2, 3], [4, 5], [6], [], [3, 3]] -- [1, 2, 3, 4, 5, 6, 3, 3]
flatten [[2, 7], [8, 9], []]                 -- [2, 7, 8, 9]

flatten :: [[Int]] -> [Int]
flatten = foldr (++) []         -- implicit input

flatten x = foldr (++) [] x     -- explicit input

Problem 7

Implement a function myLength :: String -> Int that returns the length of a string.

myLength "Tomas"                -- 5
myLength "Sunset"               -- 6

myLength :: String -> Int
myLength = foldr (+) 0 . map (const 1)

Debugging Grimoire