H. Conrad Cunningham
19 October 2018
Copyright (C) 2018, H. Conrad Cunningham
Acknowledgements: I originally created these slides in Fall 2018 to accompany what is now Chapter 18, More List Processing, 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.
Source Code: The Haskell module for this chapter is
in MoreLists.hs
.
Introduce sequences and list comprehensions (sweet syntactic sugar)
Explore list comprehensions as a programming technique
Examine “solve a more general problem” solution strategy
[m..n]
list of
elements from m
up to n
in steps of 1 if m <= n
; nil
otherwise
Sugar for Prelude enumFromTo m n
[1..5]
$\Longrightarrow$
[1,2,3,4,5]
[5..1]
$\Longrightarrow$
[]
[m,m’..n]
list
of elements from m
in steps of
m’m
m’ > m
increasing up to n
m’ < m
decreasing
Sugar for Prelude enumFromThenTo m’ m n
[1,3..9]
$\Longrightarrow$
[1,3,5,7,9]
[9,8..5]
$\Longrightarrow$
[9,8,7,6,5]
[9,8..11]
$\Longrightarrow$
[]
[m..]
and
[m,m’..]
produce potentially infinite lists beginning with m
and having steps 1 and m’m
Sugar for Prelude enumFrom m
and
enumFromThen m m’
geometric :: (Ord a, Num a) => a > a > a > [a]
geometric r m n  m > n = []
 otherwise = m : geometric r (m*r) n
geometric 2 1 10
$\Longrightarrow$
[1,2,4,8]
Syntax: [
expression

qualifiers ]
expression any Haskell expression
expression and qualifiers may contain local variables bound by qualifiers
generates list element by substituting values for variables in expression
Syntax: pat <
exp
exp is listvalued expression
Extracts each element of exp matching pattern pat, in order
[ n*n  n < [1..5]]
yields [1,4,9,16,25]
Syntax: Any Boolean expression
Only values that make expression True
used to
form elements
[ n*n  even n ]
yields (if even n then [n*n] else [])
n
global to comprehension
expression
Syntax: let
pat =
expr
Introduces variable local to comprehension
[ n*n  let n = 2 ]
yields [4]
Generators to right vary more quickly (inner loop)
[ (m,n)  m<[1..3], n<[4,5] ]
yields
[(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)]
Qualifiers to right may use values generated by qualifiers to left
[ n*n  n<[1..10], even n ]
yields
[4,16,36,64,100]
[ (m,n)  m<[1..3], n<[1..m] ]
yields
[(1,1),(2,1),(2,2),(3,1),(3,2),(3,3)]
Generated values may or may not be used
[ 27  n<[1..3]]
yields [27,27,27]
[ x  x<[1..3], y<[1.2]]
yields
[1,1,2,2,3,3]
Translated to regular functions calls — see section 18.3.2
Underlying higherorder function concatMap
—
which can represent both map
and filter
When n < 1
yields empty string
isPrime :: Int > Bool
isPrime n  n > 1 = (factors n == [])
where factors m = [ x  x<[2..(m1)], m `mod` x == 0 ]
isPrime _ = False
n
prime if n > 1
and has no factors other than 1 and n
Lazy evaluation, so factors
never generates more than 1 element
Consider: position
takes list
and value, returns position of first occurrence; 0 if not in list
Generalize to finding all occurrences
Generalize to finding all occurrences
Lazy evaluation only generates head element!
Lazy evaluation allows upper bound to be removed
List comprehensions (generators, filters, local defitions)
Translating list comprehensions to regular functions
Solve a more general problem strategy
The Haskell module for this chapter is in MoreLists.hs
.