Higher Order Functions¶

7.1 Basic Concepts¶

-- Functions as outputs of other functions
--
add :: Int -> Int -> Int
add x y = x + y

-- equivalent to 
--
-- add :: Int -> (Int -> Int)
-- add = \x -> (\y -> x + y)
--
-- i.e. add is a function that takes x as input and returns a function 
-- as output that takes y as input and returns x + y

-- Functions can also take as input a function value
--
twice :: (a -> a) -> a -> a
twice f x = f (f x)
--
twice (*2) 3
twice reverse [1,2,3]

12

[1,2,3]

Functions that have other functions as inputs or return a function are called Higher Order Functions

7.2 Processing Lists¶

map¶

map1 :: (a -> b) -> [a] -> [b]
map1 f xs = [f x | x <- xs]

map1 (+1) [1,2,3,4]
map1 even [1,2,3,4]
map1 reverse ["abc","def","ghi"]

[2,3,4,5]

[False,True,False,True]

["cba","fed","ihg"]

-- map within a map!
--
map1 (map1 (+1)) [[1,2,3],[4,5]]
-- = [map1 (+1) [1,2,3], map1 (+1) [4,5]]
-- = [[2,3,4],[5,6]]

[[2,3,4],[5,6]]

Definition of map

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

filter¶

filter1 :: (a -> Bool) -> [a] -> [a]
filter1 p xs = [x | x <- xs, p x]

filter1 even [1..10]
filter1 (>5) [1..10]
filter1 (/= ' ') "abc def ghi"

[2,4,6,8,10]

[6,7,8,9,10]

"abcdefghi"

Definition of filter

filter :: (a -> Bool) -> [a] -> [a]
filter p []     = []
filter p (x:xs)
  | p x       = x : filter p xs
  | otherwise = filter p xs

-- Example: sum of squares of even integers in a list
sumsqreven :: [Int] -> Int
sumsqreven ns = sum (map (^2) (filter even ns))

sumsqreven [1,2,3,4,5,6]

56

Other HOFs in the prelude¶

all even [2,4,6,8]

True

any odd [2,4,6,8]

False

takeWhile even [2,4,6,7,8]

[2,4,6]

dropWhile odd [1,3,5,6,7]

[6,7]

7.3 foldr¶

Many functions on lists follow the pattern

f []     = v
f (x:xs) = x # f xs

i.e. f applied to [] is v; f applied to non-empty list equals operator # applied to head of list and result of processing tail of list recursively

sum []     = 0
sum (x:xs) = x + sum xs

product []     = 1
product (x:xs) = x * product xs

or []     = False
or (x:xs) = x || or xs

and []     = True
and (x:xs) = x && and xs

The HOF foldr encapsulates the above pattern

sum :: Num a => [a] -> a
sum = foldr (+) 0
-- sum xs = foldr (+) 0 xs

product :: Num a => [a] -> a
product = foldr (*) 1

or :: [Bool] -> Bool
or = foldr (||) False

and :: [Bool] -> Bool
and = foldr (&&) True

foldr itself could be implemented as follows

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f v []     = v
foldr f v (x:xs) = f x (foldr f v xs)

In practice it is best to think of foldr as an iterative process that processes a list, say

1 : (2 : (3 : []))

by replacing "cons" by f and [] by v. For example

sum = foldr (+) 0

replaces "cons" by + and [] by 0 to get

1 + (2 + (3 + 0))

foldr can be use for much more than the simple pattern seen above. For example

length1 :: [a] -> Int
length1 = foldr (\ _ n -> 1 + n) 0

length1 [1,2,3]

3

snoc :: a -> [a] -> [a]
snoc x xs = xs ++ [x]

reverse1 :: [a] -> [a]
reverse1 = foldr snoc []

reverse [1,2,3]

[3,2,1]

It is interesting to note that foldr uses an operator that "associates" to the right; e.g.

foldr (+) 0 [1,2,3] = 1 + (2 + (3 + 0))

or in general

foldr (#) v [x0,x1,...,xn] = x0 # (x1 # (... (xn # v)...))

7.4 foldl¶

-- left associative!
sum2 :: Num a => [a] -> a
sum2 = sum' 0
       where sum' v [] = v
             sum' v (x:xs) = sum' (v+x) xs

sum2 [1,2,3]

6

  sum2 [1,2,3]
= sum' 0 [1,2,3]
= sum' (0+1) [2,3]
= sum' ((0+1)+2) [3]
= sum' (((0+1)+2)+3) []
= sum' ((0+1)+2)+3
= 6

Generalizing the pattern, we get

f v []     = v
f v (x:xs) = f (v # x) xs

This pattern is captured by the foldl operator in Haskell. e.g.

sum :: Num a -> [a] -> a
sum = foldl (+) 0

Similarly

product :: Num a -> [a] -> a
product = foldl (*) 1

or :: [Bool] -> Bool
or = foldl (||) False

and :: [Bool] -> Bool
and = foldl (&&) True

length :: [a] -> Int
length = foldl (\n _ -> n+1) 0

reverse :: [a] -> [a]
reverse = foldl (\xs x -> x:xs) []

Using the above foldl definitions,

length [1,2,3] = ((0 + 1) + 1) + 1 = 3
reverse [1,2,3] = 3 : (2 : (1 : [])) = [3,2,1]

foldl itself is defined using recursion as

foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f v []     = v
foldl f v (x:xs) = foldl f (f v x) xs

In practice, however, it is bestto view foldl non-recursively as `` foldl (#) v [x1,x1,...,xn] = (... ((v # x0) # x1) ... ) # xn ```

7.5 The composition operator¶

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

Composition can be used to simplify nested function applications. e.g.

odd n = not (even n)
twice f x = f (f x)
sumsqreven ns = sum (map (^2) (filter even ns))

can be rewritten as

odd = not . even
twice f = f . f
sumsqreven = sum . map (^2) . filter even

Composition is associative

f . (g . h) = (f . g) . h

Composition has an identity:

id :: a -> a
id = \x -> x

Now composition of a list of functions can be defined as

compose :: [a -> a] -> (a -> a)
compose = foldr (.) id

7.6 Binary string transmitter¶

Convert binary to integer¶

take 10 (iterate (*2) 1)

[1,2,4,8,16,32,64,128,256,512]

import Data.Char
type Bit = Int
bin2int :: [Bit] -> Int
bin2int bits = sum [w*b | (w,b) <- zip weights bits]
               where weights = iterate (*2) 1

-- bits are in reverse order for this example
bin2Int [1,0,1,1]

13

Another way to implement bin2Int

[a,b,c,d]
  1*a + 2*b + 4*c + 8*d
= a + 2*b + 4*c + 8*d
= a + 2*(b + 2*c + 4*d)
= a + 2*(b + 2*(c + 2*d))
= a + 2*(b + 2*(c + 2*(d + 2*0)))

This can be implemented using foldr as follows

bin2int :: [Bit] -> Int
bin2int = foldr (\x y -> x + 2*y) 0

bin2int :: [Bit] -> Int
bin2int = foldr (\x y -> x + 2*y) 0

bin2Int [1,0,1,1]

13

Convert integer to binary¶

int2bin :: Int -> [Bit]
int2bin 0 = []
int2bin n = n `mod` 2 : int2bin (n `div` 2)

int2bin 13

[1,0,1,1]

making all binary numbers same length (8 bits)¶

make8 :: [Bit] -> [Bit]
make8 bits = take 8 (bits ++ repeat 0)

make8 [1,0,1,1]

[1,0,1,1,0,0,0,0]

Here, repeat is a function within the prelude that produces an infinite list of the same value.

repeat :: a -> [a]

Message transmission¶

encode :: String -> [Bit]
encode = concat . map (make8 . int2bin . ord)

encode "abc"

[1,0,0,0,0,1,1,0,0,1,0,0,0,1,1,0,1,1,0,0,0,1,1,0]

-- to decode message back to string, first we chop into 8 bits
chop8 :: [Bit] -> [[Bit]]
chop8 []   = []
chop8 bits = take 8 bits : chop8 (drop 8 bits)

chop8 [1,0,0,0,0,1,1,0,0,1,0,0,0,1,1,0,1,1,0,0,0,1,1,0]

[[1,0,0,0,0,1,1,0],[0,1,0,0,0,1,1,0],[1,1,0,0,0,1,1,0]]

decode :: [Bit] -> String
decode = map (chr . bin2int) . chop8

decode [1,0,0,0,0,1,1,0,0,1,0,0,0,1,1,0,1,1,0,0,0,1,1,0]

"abc"

-- Finally transmit message
transmit :: String -> String
transmit = decode . channel . encode
channel :: [Bit] -> [Bit]
channel = id

transmit "higher-order functions are easy"

"higher-order functions are easy"

7.7 Voting algorithms¶

First past the post method¶

votes :: [String]
votes = ["Red","Blue","Green","Blue","Blue","Red"]

count :: Eq a => a -> [a] -> Int
count x = length . filter (== x)

count "Red" votes
count "Blue" votes
count "Green" votes

2

3

1

rmdups :: Eq a => [a] -> [a]
rmdups [] = []
rmdups (x:xs) = x : filter (/= x) (rmdups xs)

rmdups votes

["Red","Blue","Green"]

import Data.List

result :: Ord a => [a] -> [(Int,a)]
result vs = sort [(count v vs,v) | v <- rmdups vs]

result votes

[(1,"Green"),(2,"Red"),(3,"Blue")]

winner :: Ord a => [a] -> a
winner = snd . last . result

winner votes

"Blue"

Alternative vote¶

ballots :: [[String]]
ballots = [["Red","Green"],
           ["Blue"],
           ["Green","Red","Blue"],
           ["Blue","Green","Red"],
           ["Green"]]

Each ballot list 1st preference, 2nd preference, etc.

Method to determine winner: repeatedly eliminate smallest number of 1st choice votes. e.g.

Since "Red" has smallest number of 1st choices, eliminate it from all ballots:

ballots = [["Green"],
           ["Blue"],
           ["Green","Blue"],
           ["Blue","Green"],
           ["Green"]]

Now, "Blue" has smallest number of 1st choices; eliminate it from all ballots:

ballots = [["Green"],
           [],
           ["Green"],
           ["Green"],
           ["Green"]]

Removing [] and observing that we have only one remaining candidate we can now declare the winner

rmempty :: Eq a => [[a]] -> [[a]]
rmempty = filter (/= [])

elim :: Eq a => a -> [[a]] -> [[a]]
elim x = map (filter (/= x))

ballots2 = [["Green"],
            [],
            ["Green"],
            ["Green"],
            ["Green"]]
rmempty ballots2

[["Green"],["Green"],["Green"],["Green"]]

elim "Red" ballots

[["Green"],["Blue"],["Green","Blue"],["Blue","Green"],["Green"]]

elim "Blue" (elim "Red" ballots)

[["Green"],[],["Green"],["Green"],["Green"]]

rank :: Ord a => [[a]] -> [a]
rank = map snd . result . map head

rank ballots

["Red","Blue","Green"]

winner' :: Ord a => [[a]] -> a
winner' bs = case rank (rmempty bs) of
               [c]    -> c
               (c:cs) -> winner' (elim c bs)

winner' ballots

"Green"

Exercises¶

-- #4 dec2int
dec2int :: [Int] -> Int
dec2int = foldl (\x y -> 10*x + y) 0

dec2int [2,3,4,5]

2345