Higher-Order Functions

Intro

Slides

Quizzes

cse116-map-ind -> D

cse116-quiz-ind -> D

cse116-foldeval-ind -> B

cse116-foldtype-ind -> D

cse116-foldl2-ind ->

In this lecture: code reuse with higher-order functions (HOFs)

e.g.: map, filter, fold

Recursion

Gets pretty old pretty quickly!

Ex. a function that finds all even nums in a list

evens :: [Int] -> [Int]
evens []                      = []
evens (x:xs) | x `mod` 2 == 0 = x:(evens xs)
             | otherwise      = evens xs

or a function that filters 4 letter words

fourChars :: [Int] -> [Int]
fourChars []     = []
fourChars (x:xs) | (length x) == 4 = x:(fourChars xs)
                 | otherwise       = fourChars xs

HOFs

HOFs are a general pattern expressed as a HOF that takes customizable args, applied multiple times

Filter

filter :: (a -> Bool) -> [a] -> [a]  -- polymorphic type!
filter f [] = []
filter f (x:xs)
    | f x       = x:(filter f xs)
    | otherwise = filter f xs

-- now we can:
evens = filter isEven
    where isEven x = x `mod` 2 == 0

fourChars = filter isFour
    where isFour x = length x == 4

Map

Ex: we want to do some op on every elem

-- boring!
shout []     = []
shout (x:xs) = toUpper x : shout xs

square []     = []
square (x:xs) = x * x : square xs

Let’s do this!

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

-- so
shout = map (\x -> toUpper x)
square = map (\x -> x*x)

Fold

Ex: length/sum of a list

How about joining a list of strings?

cat :: [String] -> String
cat []     = ""
cat (x:xs) = x ++ cat xs

Fold-Right

This is fold-right!

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

-- so:
sum = foldr (+) 0
cat = foldr (++) ""
len = foldr (\x n -> 1 + n) 0

It’s called this because it accumulates from the right (expansion is right associative)

Fold-Left

What about tail recursive versions?

-- tail recursive cat!
catTR :: [String] -> String
catTR xs = helper "" xs
    where
        helper acc []     = acc
        helper acc (x:xs) = helper (acc ++ x) xs

so:

foldl :: (a -> b -> b) -> b -> [a] -> b
foldl f b xs = helper b xs
    where
        helper acc []     = acc
        helper acc (x:xs) = helper (f acc x) xs

-- so, syntax is the same as foldr:
sumTR = foldl (+) 0
catTR = foldl (++) ""

Flip

Useful HOF:

-- instead of writing:
foldl (\xs x -> x : xs) [] [1, 2, 3]

-- write:
foldl (flip (:)) [] [1, 2, 3]

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

Compose

map (\x -> f (g x)) ys
-- ==
map (f . g) ys

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