Copyright (C) 2017, 2018, H. Conrad Cunningham

Acknowledgements: I originally created these slides in Fall 2017 to accompany what is now Chapter 15, Higher Order Functions, in the 2018 version of the textbook Exploring Languages with Interpreters and Functional Programming.

Browser Advisory: The HTML version of this document may require use of a browser that supports the display of MathML. A good choice as of October 2018 is a recent version of Firefox from Mozilla.

Lecture Goals

• Demonstrate how to “think like a functional programmer”

• Introduce concepts of first-class and higher-order functions

• Illustrate how to generalize computational patterns

• Develop useful library of higher-order list functions (map, filter, foldr, foldl, concatMap, etc)

• Reinforce correct, efficient, and elegant function designs

Procedural Abstraction

Procedural abstraction: (Ch. 2)

separates logical properties of computation from details of implementation

• To perform same computation on similar data structures

  • encapsulate computation in first-order polymorphic function

  • pass data structure as argument

  • example: length :: [a] -> Int

Generalizing Procedural Abstractions

• To perform similar computations on similar data structures

  • encapsulate computation in higher-order polymorphic function

  • also pass function for subcomputation as argument

  • example: same function can either add or multiply all elements of list

First Class and Higher Order

First-class value:

can be stored in a data structure, passed as argument, returned as result

Higher-order function (HOF):

takes functions as arguments or returns function as result

Haskell functions are first class values, can be higher-order

Advantages of HOFs

Haskell higher-order functions (HOF)

$\Longrightarrow$ construct powerful abstractions and operations

$\Longrightarrow$ express concise, “easy-to-understand” programs

$\Longrightarrow$ “glue together” programs from library functions and new program fragments

$\Longrightarrow$ improve programmer productivity and program reliability

Defining Map (map)

    squareAll :: [Int] -> [Int] 
    squareAll []     = [] 
    squareAll (x:xs) = (x * x) : squareAll xs

    lengthAll :: [[a]] -> [Int] 
    lengthAll []       = [] 
    lengthAll (xs:xss) = (length xs) : lengthAll xss

• Take different kinds of data

• Apply different operations

• But both take list, apply function to each element, generate new list with same order and length

Generalize to HOF map

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

• Generalizes squareAll, lengthAll, and similar functions

• Adds higher-order parameter f for operation applied

• Makes input and output lists polymorphic of different types

Specialize map

    squareAll2 :: [Int] -> [Int]
    squareAll2 xs = map' sq xs 
                    where sq x = x * x 

    lengthAll2 :: [[a]] -> [Int] 
    lengthAll2 xss = map' length xss

• sq and length one-argument functions

• What are map’s types a and b in above?

Analyze map

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

• Under what circumstances does map' f xs terminate normally? (What preconditions?)

• What is time complexity of map f xs?

• What is space complexity of map f xs?

Analyze Specializations

    squareAll2 :: [Int] -> [Int]
     squareAll2 xs = map' sq xs 
                    where sq x = x * x 

    lengthAll2 :: [[a]] -> [Int] 
    lengthAll2 xss = map' length xss

• What is time complexity of squareAll2 xs? space complexity?

• What is time complexity of lengthAll2 xs? space complexity?

Think Like Functional Programmer

map is recursive list function, but can consider it:

1. powerful list operator transforming elements simultaneously

   Parallelism “easy” given referential transparency & immutable data—consider Google’s mapReduce

2. operator node in dataflow network

   Demand-driven network enabled by lazy evaluation  stream $\longrightarrow$ [map node] $\longrightarrow$ transformed-stream

Method for Generalizing (1)

1. Do scope-commonality-variability analysis (SCV) on set of functions

   • scope: what is and is not included

   • commonalities: parts of functions that are same (frozen spots)

   • variabilities: parts of functions that differ (hot spots)

2. Leave commonalities in function body.

3. Move variabilities into type signature & parameter list

Method for Generalizing (2)

3. Move variabilities into type signature & parameter list

   • Make expression moved a function with parameter for each local variable accessed

   • Add type parameter to signature for types that differ among functions in scope

   • Add distinct type or value parameter for each potential role that type/value plays among functions in scope

4. Consider other approaches if many new parameters (e.g., new procedural or data abstractions)

Defining Filter (filter)

Study similar functions

    getEven :: [Int] -> [Int] 
    getEven []      = [] 
    getEven (x:xs)
        | even x    = x : getEven xs 
        | otherwise = getEven xs

    doublePos :: [Int] -> [Int] 
    doublePos []          = [] 
    doublePos (x:xs) 
        | 0 < x     = (2 * x) : doublePos xs 
        | otherwise = doublePos xs

Identify Commonalities

• Take integer list and return integer list

• For empty input, return empty output

• Maintain relative order from input and output

• Select some elements to copy; others not to copy

Identify Variabilities

• What is type of input and output list elements (Int type arbitrary)

• How to select value (getEven uses even, doublePos compares with 0)

• How to transform selected value (doublePos doubles, getEven leaves unchanged)

Generalize to HOF filter

    filter' :: (a -> Bool) -> [a] -> [a]  -- filter in Prelude
    filter' _ []    = [] 
    filter' p (x:xs)
        | p x       = x : xs' 
        | otherwise = xs' 
                      where xs' = filter' p xs

• Takes and returns list of type [a]

• Takes predicate function p of type a -> Bool

• Returns list containing elements that satisfy p in same order

• But does not implement transformation operation

Specialize filter

    getEven2 :: [Int] -> [Int] 
    getEven2 xs = filter' even xs 

    doublePos2 :: [Int] -> [Int] 
    doublePos2 xs = map' dbl (filter' pos xs) 
                    where dbl x  = 2 * x
                          pos x = (0 < x)

• Reuse map to transform data in doublePos

• Restate three-leg definition of getEven/doublePos in one leg

  Except simple local definitions in doublePos, which we eliminate later

Analyze filter

    filter' :: (a -> Bool) -> [a] -> [a]  -- filter in Prelude
    filter' _ []    = [] 
    filter' p (x:xs)
        | p x       = x : xs' 
        | otherwise = xs' 
                      where xs' = filter' p xs

• Under what circumstances does filter' p xs terminate normally? (What preconditions?)

• What is time complexity of filter' p xs?

• What is space complexity of filter' p xs?

Analyze Specializations

    getEven2 :: [Int] -> [Int] 
    getEven2 xs = filter' even xs 

    doublePos2 :: [Int] -> [Int] 
    doublePos2 xs = map' dbl (filter' pos xs) 
                    where dbl x  = 2 * x
                          pos x = (0 < x)

• What is the time complexity of getEven2 xs? space complexity?

• What is the time complexity of doublePos2 xs? space complexity?

Defining Fold Right (foldr)

Study similar functions

    sum' :: [Int] -> Int             -- sum in Prelude
    sum' []     = 0
    sum' (x:xs) = x + sum' xs 
        
    product' :: [Integer] -> Integer -- product in Prelude
    product' []     = 1 
    product' (x:xs) = x * product' xs 

    concat' :: [[a]] -> [a]          -- concat in Prelude
    concat' []       =  []
    concat' (xs:xss) =  xs ++ concat' xss

    sum' [1,2,3]          = (1 + (2 + (3 + 0)))
    product' [1,2,3]      = (1 * (2 * (3 * 1)))
    concat' ["1","2","3"] = ("1" ++ ("2" ++ ("3" ++ "")))

Identify Commonalities

• Take list

• Insert binary operator between consecutive list elements (associative for these)

• Reduce list to single return value

• Group operations right to left

• Return some value for nil list (as “rightmost” value of nonempty)

  Here value is (right) identity of operation

Identify Variabilities

• Differ in element type (Int, Integer, [a])

• Differ in operation inserted (addition, multiplication, list append)

• Differ in value returned for nil input list—(right) identity element (0, 1, [])

• Differ in return type (Int, Integer, a)

  Here each same as input element type, but can it differ?

Exploring Generalization

• Is associativity important? identity?

  Do not assume

• Observe operations of type a -> a -> a

• Consider more general operations of type a -> b -> b

  $\Longrightarrow$ return value of type b for empty or nonempty lists

Generalize to HOF foldr (1)

    foldrX :: (a -> b -> b) -> b -> [a] -> b  -- foldr in Prelude
    foldrX f z []     = z
    foldrX f z (x:xs) = f x (foldrX f z xs) 

• Separates input element type a from output value type b

• Takes general binary operation f (of type a -> b -> b) to “fold” list

• Takes “seed” value z (of type b) as return for empty lists

• Does not depend upon operation being associative or having identity

Generalize to HOF foldr (2)

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

foldr f z [1,2,3] expands to

    f 1 (f 2 (f 3 z))       -- prefix form
    1 `f` (2 `f` (3 `f` z)) -- infix form

Specialize foldr

    sum2 :: [Int] -> Int             -- sum
    sum2 xs = foldrX (+) 0 xs

    product2 :: [Int] -> Int         -- product
    product2 xs = foldrX (*) 1 xs

    concat2:: [[a]] -> [a]           -- concat
    concat2 xss = foldrX (++) [] xss

    and', or' :: [Bool] -> Bool      -- and, or
    and' xs = foldrX (&&) True xs 
    or'  xs = foldrX (||) False xs

Analyze foldr

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

• Under what circumstances does foldrX f z xs terminate normally? (What preconditions?)

• What is time complexity of foldrX f z xs? space complexity?

• Backward recursive, so possible stack overflow for complex f or long xs

Analyze Specializations

    product2 :: [Int] -> Int         -- product
    product2 xs = foldrX (*) 1 xs

    concat2:: [[a]] -> [a]           -- concat
    concat2 xss = foldrX (++) [] xss

• What is time complexity of product2 xs? space complexity?

• What is time complexity of concat2 xs? space complexity?

Using foldr for map

    map2 :: (a -> b) -> [a] -> [b] -- map
    map2 f xs = foldr mf [] xs 
        where mf y ys = (f y) : ys

• map inc [1,2] = mf 1 (mf 2 [])
  where inc x = x+1

• Moving right to left folding function mf

  • applies map function f to next element

  • attaches result as head of processed tail

• Uses nil list for seed—mf has no identity but foldr useful!

Using foldr for filter

    filter2 :: (a -> Bool) -> [a] -> [a]  -- filter
    filter2 p xs = foldr ff [] xs
        where ff y ys = if p y then (y:ys) else ys

• filter2 gt2 [1,3] = ff 1 (ff 3 [])
  where gt2 x = x > 2

• Uses nil list for seed for filtered result

• Moving right to left folding function ff

  • applies filter predicate p to next element

  • if holds, attaches element as head of filtered result; else omits

Using foldr for length

    length2 :: [a] -> Int  -- length
    length2 xs  = foldr len  0  xs
        where len _ acc = acc + 1

• length2 [1,2] = len 1 (len 2 0)

• Uses seed value 0 as initial value of counter

• Moving right to left folding function
  len _ acc= acc + 1

  • takes next element as left argument and counter as right

  • returns incremented counter

Using foldr for append

    append2 :: [a] -> [a] -> [a]  -- ++
    append2 xs ys = foldr (:) ys xs

• append2 [1,2] [3,4] = 1 : (2 : [3,4])

• Uses entire second argument of ++ as seed value

• Moving right to left through left argument of ++, folding function (:)

  • attaches next element as head of resulting appended list

Think Like Functional Programmer

• foldr, filter, and map are backward recursive functions

• But think of them as powerful operators on whole lists

Defining Fold Left (foldl)

    foldr :: (a -> b -> b) -> b -> [a] -> b

    foldr f z [1,2,3] ==  f 1 (f 2 (f 3 z))
                      ==  1 `f` (2 `f` (3 `f` z))

What about same functionality except group from left?

    foldl f z [1,2,3]  ==  f (f (f z 1) 2) 3
                       ==  ((z `f` 1) `f` 2) `f` 3`

HOF foldl

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

• Inserts “seed” value as leftmost element

• Uses “seed” value parameter as accumulator—tail recursive

• Has different type signature

First Duality Theorem

If $\oplus$ is an associative binary operation of type t -> t -> t with identity element z then, for any finite xs.

foldr ( $\oplus$) z xs = foldl ( $\oplus$) z xs

• sum, product, and concat all satisfy

• Which of foldr or foldl better to use?

Informal Look at Strictness

• Strict function parameter means argument value always required by function evaluation

• Nonstrict function parameter means argument value sometimes not required

• Addition and multiplication strict in both parameters (operands)

• ++ strict in first parameter and nonstrict in second

Rule of Thumb

1. If operation $\oplus$ nonstrict in either argument, then often better to use foldr—exploits lazy evaluation

2. If operations $\oplus$ strict in both arguments, then more efficient to use foldl' from library Data.List

Choosing foldr or foldl (1)

• Implement concat with foldr because ++ nonstrict in second

• Implement sum and product with foldl' because + an * strict in both

    import Data.List   -- to make foldl' available
    sum3, product3 :: Num a =>  [a] -> a -- sum, product
    sum3 xs     = foldl' (+) 0 xs
    product3 xs = foldl' (*) 1 xs

Choosing foldr or foldl (2)

    length3 :: [a] -> Int  -- length
    length3 xs  = foldl len 0  xs
        where len acc _ = acc + 1

• Uses foldl

• Like length2 except len arguments reversed

• length2 better choice because len nonstrict list argument

Choosing foldr or foldl (3)

    reverse2 :: [a] -> [a]  -- reverse
    reverse2 xs = foldl rev [] xs
        where rev acc x = (x:acc) 

• Similar to the tail recursive reverse

• foldl’s z parameter initially nil

• foldl’s f parameter uses (:) to build list in reverse order

• reverse2 cannot exploit lazy evaluation on (:) ’s right argument because of its initialization

• Better to use tail recursion

Using foldl for foldr

    foldr2 :: (a -> b -> b) -> b -> [a] -> b  -- foldr
    foldr2 f z xs = foldl flipf z (reverse xs)
        where flipf y x = f x y

• Avoids possible stack overflow by reversing list, using tail recursive foldl

Defining Flat Map (concatMap)

    concatMap' :: (a -> [b]) -> [a] -> [b] 
    concatMap' f xs = concat (map f xs)

    concatMap2 :: (a -> [b]) -> [a] -> [b] 
    concatMap2 f xs = foldr fmf [] xs 
        where fmf x ys = f x ++ ys

Using concatMap for filter

    filter3 :: (a -> Bool) -> [a] -> [a]
    filter3 p xs = concatMap' fmf xs
        where fmf x = if p x then [x] else []

Key Ideas

• First-class and higher-order functions

• Generalizing computational patterns as higher-order functions

• Using library of list-transforming functions

• Thinking like a functional programmer

Code

The Haskell code module for this section is in file HigherOrderFunctions.hs