Acknowledgements: I originally created these slides in Fall 2017 to accompany what is now Chapter 16, Haskell Function Concepts, 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.

Code: The Haskell module for this chapter is in FunctionConcepts.hs.

Haskell Function Concepts

Lecture Goals

Explore additional function concepts useful in conjunction with higher-order functions (strictness, currying, partial application, operator sections, combinators, lambda expressions, application operator, eager evaluation)
Demonstrate function composition, point-free style, and function pipelines
Examine additional higher-order function examples
Continue to reinforce how to think like functional programmer

Strictness (1)

Cannot reduce some expressions to simple values: div 1 0 triggers exception
Represent such undefined “values” with symbol $\bot$ (“bottom”)
Cannot represent $\bot$ , but can apply function to it
Call f strict if f $\bot = \bot$
Call f nonstrict otherwise
Must evaluate strict; might not need nonstrict

Strictness (2)

    two :: a -> Int 
    two x = 2  -- argument not evaluated

    reverse' :: [a] -> [a]  -- reverse
    reverse xs = rev xs []  -- must eval xs
                  where rev []     ys = ys 
                        rev (x:xs) ys = rev xs (x:ys)

two (div 1 0) == 2 — two nonstrict in argument
Arithmetic operations (e.g. +) strict in both
reverse' strict in its one argument

Strictness (3)

    (++) :: [a] -> [a] -> [a] 
    [] ++ xs     = xs   -- 2nd arg not evaluated
    (x:xs) ++ ys = x:(xs ++ ys)

    (&&), (||) :: Bool -> Bool -> Bool 
    False && x = False  -- 2nd arg not evaluated 
    True  && x = x 

    False || x = x      -- 2nd arg not evaluated 
    True  || x = True

++ is strict first argument, nonstrict in second
&& and || strict in first argument, nonstrict in second

Currying/Partial Application (1)

    add :: (Int,Int) -> Int 
    add (x,y) = x + y 

    add' :: Int -> (Int -> Int) 
    add' x y  = x + y

add (x,y) = add’ x y, but functions different types
What result of add 3? — compiler error
What result of add’ 3? — single argument function
What result of (add’ 3) 4?
add’ x y = ((add’ x) y) — binds left, tightly

Currying/Partial Application (2)

currying: replace function that takes tuple by function that take arguments one at time
add’ similar to function (+)
((+) 3) — (+) partially applied

    doublePos3 :: [Int] -> [Int]  -- Prelude map, filter
    doublePos3 xs = map ((*) 2) (filter ((<) 0) xs)

Property of Extensionality

Functions f and g extensionally equal if f x = g x for all x

    f, g :: a -> a
    f x = some_expression
    g x = f x  -- one definition

    g = f      -- equivalent definition

Operator Section Motivation

((<) 0) confusing because < normally infix — ((<) 0) returns True for positive integers

((/) 2) divides 2 by its operand — what about function that takes half

flip' :: (a -> b -> c) -> b -> a -> c  -- flip in Prelude 
flip' f x y = f y x

(flip (/) 2) is halving operator

Operator Section Definition

Operator section (syntactic sugar):

For infix operator $\oplus$ and expression e:

(e $\oplus$ ) represents (( $\oplus$ ) e)
( $\oplus$ e) represents (flip ( $\oplus$ ) e)

Operator Section Examples

(1+) is successor function
(0<) is test for positive integer
(/2) is halving function.
(1.0/) is reciprocal function
(:[]) returns singleton list containing argument

    sumCubes :: [Int] -> Int 
    sumCubes xs = sum' (map (^3) xs)

    sum' = foldl' (+) 0  -- sum

Combinator Definition

Combinator:: function without any free variables

No variables or operator symbols on right not bound on left

    flip' :: (a -> b -> c) -> b -> a -> c  -- flip in Prelude 
    flip' f x y = f y x                    -- C combinator

    const' :: a -> b -> a  -- const in Prelude
    const' k x = k         --   constant function constructor
                           --   K combinator

    id' :: a -> a          -- id in Prelude 
    id' x = x              --   identity function
                           --   I combinator

What does sum (map (const 1) xs) do?

Tuple Selector Combinators

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

    snd' :: (a,b) -> b     -- snd in Prelude 
    snd' (_,y) = y

fst3, snd3, thd3 from extract 1st, 2nd, 3rd components of 3-tuples (No, use Data.Tuple.Select now.)

Reverse Using Combinator

    reverse' :: [a] -> [a]           -- reverse in Prelude
    reverse' = foldlX (flip (:)) [] -- foldl, flip

flip (:) takes list on left and element on right
Starts with [] from left
Attaches each element as head of list

Curry and Uncurry Combinators

    curry' :: ((a, b) -> c) -> a -> b -> c -- curry in Prelude 
    curry' f x y =  f (x, y) 

    uncurry' :: (a -> b -> c) -> ((a, b) -> c) -- uncurry in Prelude 
    uncurry' f p =  f (fst p) (snd p)

Fork and Cross Combinators

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

    cross :: (a -> b, c -> d) -> (a,c) -> (b,d)
    cross (f,g) (x,y) = (f x, g y)

Not in Prelude
fork applies each pair of functions separately to value to create pair of results
cross applies pair of functions component-wise to pair of values to create pair of results

Functional Composition

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

Combines several “smaller” functions into “larger” functions
Binds from right, highest precedence except function application

     f . (g . h) = (f . g) . h  -- associative
     id . f  = f . id           -- "id" is identity

Pointful and Point-Free Styles

Pointful style — gives parameters explicitly

    doit x = f1 (f2 (f3 (f4 x)))

Point-free style — leaves parameters implicit

    doit = f1 . f2 . f3 . f4

Function Pipelines (1)

    count :: Int -> [[a]] -> Int 
    count n           -- point-free expression below defines pipeline
        | n >= 0    = length . filter (== n) . map length
        | otherwise = const 0   -- discard 2nd arg, return 0

Pipeline takes polymorphic list of lists as input
map length replaces each inner list by its length
filter (== n) keeps only elements equal to n
length determines how many elements remaining
Pipeline outputs number of lists within input with length n

Function Pipelines (2)

Point-free expressions define function pipelines
Partial applications, operator sections, and combinators are plumbing for pipelines
Key concepts in thinking like functional programmers

    doublePos3 xs = map ((*) 2) (filter ((<) 0) xs)

Above re-expressed in point-free style below

    doublePos4 :: [Int] -> [Int] 
    doublePos4 = map (2*) . filter (0<)

Function Pipelines (3)

    last' = head . reverse            -- last in Prelude
    init' = reverse . tail . reverse  -- init in Prelude

“Quick and dirty” function pipeline more efficient if implemented directly

    last2 :: [a] -> a    -- last in Prelude
    last2 [x]    = x 
    last2 (_:xs) = last2 xs 

    init2 :: [a] -> [a]  -- init in Prelude
    init2 [x]    = [] 
    init2 (x:xs) = x : init2 xs

Function Pipelines (4)

    any', all' :: (a -> Bool) -> [a] -> Bool 
    any' p = or . map p   -- any in Prelude
    all' p = and . map p  -- all in Prelude

    elem', notElem' :: Eq a => a -> [a] -> Bool 
    elem'    = any . (==)  -- elem in Prelude
    notElem' = all . (/=)  -- notElem in Prelude

	`elem’ x xs`
$\Longrightarrow$	{ expand `elem’` }
	`(any . (==)) x xs`
$\Longrightarrow$	{ expand composition }
	`any ((==) x) xs`

Lambda Expression Motivation

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

Above from earlier can be re-expressed in point-free style

    squareAll3 :: [Int] -> [Int] 
    squareAll3 = map (\x -> x * x)

(\x -> x * x) is lambda expression (anonymous function)
Syntax: \ atomicPatterns -> expression

Lambda Expression Examples

(\x y -> (x+y)/2) averages two numbers
(\n _ -> n+1) takes integer “counter” and value, returns incremented “counter”

    import Data.List ( foldl' )
    length4 :: [a] -> Int   -- length in Prelude
    length4  = foldl' (\n _ -> n+1) 0

Application Operator `$` (1)

Function application associates to left with highest binding power

    w + f x y * z 

    w + (((f x) y) * z) -- same as above

Sometimes want it to associate to right with lowest binding power

    infixr 0 $

    ($) :: (a -> b) -> a -> b 
    f $ x = f x

Application Operator `$` (2)

For one-argument functions f, g, and h

    f $ g $ h $ z + 7

    (f (g (h (z+7))))  -- same as above

    (f . g . h) (z+7)  -- same as above

For two-argument functions f', g', and h'

    f' w $ g' x $ h' y $ z + 7

    ((f' w) ((g' x) ((h' y) (z+7)))) -- same as above

    (f' w . g' x . h' y) (z+7)

Application Operator `$` (3)

    foldr (+) 0 $ map (2*) $ filter odd $ enumFromTo 1 20

Prelude function enumFromTo m n generates inclusive sequence of integers from m to n
[m..n] syntactic sugar for enumFromTo m n (Chapter 18)

Eager Evaluation

Haskell lazily evaluated — if argument nonstrict, may never be evaluated
Compiler’s strictness analysis can safely force eager evaluation as optimization, preserving semantics
GHC’s -O option enables code optimization, including strictness analysis
Programmer can force eager evaluation explicitly

Eager Evaluation Using `seq` (1)

    seq :: a -> b -> b
    x `seq` y = y

Returns second argument y
But as side effect evaluates x (to head normal form)

Evaluated until outer layer of structure such as (h:t) revealed, but h and t may not be fully evaluated

Eager Evaluation Using `seq` (2)

    foldlP :: (a -> b -> a) -> a -> [b] -> a  -- foldl' in Data.List 
    foldlP f z []     = z                     -- optimized
    foldlP f z (x:xs) = y `seq` foldl' f y xs 
                        where y = f z x

Evaluates z argument of tail recursive foldlP eagerly
Uses where to do graph reduction of y

Eager Evaluation Using `$!` (1)

    infixr 0 $! 
    ($!) :: (a -> b) -> a -> b 
    f $! x = x `seq` f x

f $! x eagerly evaluates argument x before applying function f

    foldlQ :: (a -> b -> a) -> a -> [b] -> a  -- foldl' in Data.List 
    foldlQ f z []     = z                     -- optimized
    foldlQ f z (x:xs) = (foldlQ f $! f z x) xs

Eager Evaluation Using `$!` (2)

    sum4 :: [Integer] -> Integer  -- sum in Prelude
    sum4 xs = sumIter xs 0        -- tail recursive
        where sumIter []     acc = acc
              sumIter (x:xs) acc = sumIter xs (acc+x)

    sum5 :: [Integer] -> Integer -- sum in Prelude
    sum5 xs = sumIter xs 0 
        where sumIter []     acc = acc
              sumIter (x:xs) acc = sumIter xs $! acc + x

Eagerly evaluate accumulator argument

Eager Evaluation Caution

Be careful!
seq and $! change semantics of lazily evaluated language where argument nonstrict
May cause program to terminate abnormally or evaluate unneeded expressions

Key Ideas

Function concepts useful in conjunction with higher-order functions (strictness, currying, partial application, operator sections, combinators, lambda expressions, application operator, eager evaluation, etc.)
Function composition, point-free style, and function pipelines
Thinking like a functional programmer

Source Code

The Haskell module for this chapter is in FunctionConcepts.hs.

Exploring Languages with Interpreters and Functional Programming Chapter 16 Haskell Function Concepts