H. Conrad Cunningham
15 October 2018
Copyright (C) 2017, 2018, H. Conrad Cunningham
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
.
Explore additional function concepts useful in conjunction with higherorder functions (strictness, currying, partial application, operator sections, combinators, lambda expressions, application operator, eager evaluation)
Demonstrate function composition, pointfree style, and function pipelines
Examine additional higherorder function examples
Continue to reinforce how to think like functional programmer
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
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
(++) :: [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
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: replace function that takes tuple by function that take arguments one at time
add’
similar to function (+)
((+) 3)
— (+)
partially applied
f
and g
extensionally equal if f x = g x
for all x
((<) 0)
confusing because <
normally infix — ((<) 0)
returns True
for positive integers
((/) 2)
divides 2 by its operand — what about function that takes half
(flip (/) 2)
is halving operator
For infix operator $\oplus$ and expression e
:
(e
$\oplus$)
represents ((
$\oplus$) e)
(
$\oplus$ e)
represents (flip (
$\oplus$) e)
(1+)
is successor function
(0<)
is test for positive integer
(/2)
is halving function.
(1.0/)
is reciprocal function
(:[])
returns singleton list containing argument
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
sum (map (const 1) xs)
do? 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 3tuples (No, use Data.Tuple.Select
now.)flip (:)
takes list on left and element on right
Starts with []
from left
Attaches each element as head of list
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 componentwise to pair of values to create pair of results
Combines several “smaller” functions into “larger” functions
Binds from right, highest precedence except function application
Pointful style — gives parameters explicitly
Pointfree style — leaves parameters implicit
count :: Int > [[a]] > Int
count n  pointfree 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
Pointfree expressions define function pipelines
Partial applications, operator sections, and combinators are plumbing for pipelines
Key concepts in thinking like functional programmers
Above reexpressed in pointfree style below
“Quick and dirty” function pipeline more efficient if implemented directly
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 
Above from earlier can be reexpressed in pointfree style
(\x > x * x)
is lambda expression (anonymous function)
Syntax: \
atomicPatterns >
expression
(\x y > (x+y)/2)
averages two numbers
(\n _ > n+1)
takes integer “counter” and value, returns incremented “counter”
$
(1)Function application associates to left with highest binding power
Sometimes want it to associate to right with lowest binding power
$
(2)For oneargument functions f
, g
, and h
For twoargument functions f'
, g'
, and h'
$
(3)Prelude function enumFromTo m n
generates inclusive sequence of integers from m
to n
[m..n]
syntactic sugar for enumFromTo m n
(Chapter 18)
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
seq
(1)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
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
$!
(1)f $! x
eagerly evaluates argument x
before applying function f
$!
(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
Be careful!
seq
and $!
change semantics of lazily evaluated language where argument nonstrict
May cause program to terminate abnormally or evaluate unneeded expressions
Function concepts useful in conjunction with higherorder functions (strictness, currying, partial application, operator sections, combinators, lambda expressions, application operator, eager evaluation, etc.)
Function composition, pointfree style, and function pipelines
Thinking like a functional programmer
The Haskell module for this chapter is in FunctionConcepts.hs
.