H. Conrad Cunningham (after class)
24 September 2018
Copyright (C) 2017, 2018, H. Conrad Cunningham
Acknowledgements: I originally created these slides in Fall 2017 to accompany what is now Chapter 13, List Programming, 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 September 2018 is a recent version of Firefox from Mozilla.
Introduce immutable list data structures
Examine firstorder, polymorphic, list processing functions
Reinforce techniques for correct and efficient functional programs
Examine data sharing in lists
Examine library of useful functions
not subject to change as program executes
Primitives: Int
, Integer
, Float
, Double
, Char
, Bool
— Ch.
5
Functions — Ch. 4, 5
Tuples — Ch. 5
Lists (and strings) — Ch. 5, 1318
Userdefined (algebraic) data types — Ch. 21
Type [t]
sequence of zero
or more values of type t
—
algebraic data type supported by syntactic
sugar
Hierarchical structure — inductive definition — either empty or pair of head element and tail list
Empty list []
—
pronounced “nil”
“Cons” operator :
constructs
list from head/tail such as 3:[]
notation that simplifies expression, but adds no new functionality
Equivalent expressions
5:(3:(2:[]))
5:3:2:[]
— “cons” binds from the right
[5,3,2]
— comma separated list literal
Constructor :
Selector head (h:t)
$\Longrightarrow$
h
Selector tail (h:t)
$\Longrightarrow$
t
Prelude library functions: length
, sum
, product
, take
, drop
, ++
, reverse
String
type synonym for [Char]
"oxford" == [’o’,’x’,’f’,’o’,’r’,’d’]
"Hello\nworld!\n"
string with two newline characters
"\12\&3" == ['\12','3']
Example function to compute length of string
len "five" 

$\Longrightarrow$  if "five" == [] then 0 else 1 + len (tail "five") 
$\Longrightarrow$  if False then 0 else 1 + len (tail "five") 
$\Longrightarrow$  1 + len (tail "five") 
$\Longrightarrow$  1 + len "ive" 
$\Longrightarrow$  1 + (if "ive" == [] then 0 else 1 + len (tail "ive")) 
$\Longrightarrow$  1 + (if False then 0 else 1 + len (tail "ive")) 
$\Longrightarrow$  1 + (1 + len (tail "ive")) 
$\Longrightarrow$  1 + (1 + len "ve") 
$\Longrightarrow$  1 + (1 + (if "ve" == [] then 0 else 1 + len (tail "ve"))) 
$\Longrightarrow$  1 + (1 + (if False then 0 else 1 + len (tail "ve"))) 
$\Longrightarrow$  1 + (1 + (1 + len (tail "ve"))) 
$\Longrightarrow$  1 + (1 + (1 + len "e")) 
$\Longrightarrow$  1 + (1 + (1 + (if "e" == [] then 0 else 1 + len (tail "e")))) 
$\Longrightarrow$  1 + (1 + (1 + (if False then 0 else 1 + len (tail "e")))) 
$\Longrightarrow$  1 + (1 + (1 + (1 + len (tail "e")))) 
$\Longrightarrow$  1 + (1 + (1 + (1 + len ""))) 
$\Longrightarrow$  1 + (1 + (1 + (1 + (if "" == [] then 0 else 1 + len (tail ""))))) 
$\Longrightarrow$  1 + (1 + (1 + (1 + (if True then 0 else 1 + len (tail ""))))) 
$\Longrightarrow$  1 + (1 + (1 + (1 + 0))) 
$\Longrightarrow$  1 + (1 + (1 + 1)) 
$\Longrightarrow$  1 + (1 + 2) 
$\Longrightarrow$  1 + 3 
$\Longrightarrow$  4 
See Chapter 8 for explanation of evaluation model
Number of reduction steps proportional to length of s
— 5*(length s) + 3
steps — O(length s
) time
complexity
Maximum size of expression proportional to length of s
— 2*(length s) + 9
arguments — O(length s
) space complexity
property of having “many shapes”
General length function for more types: use type variable
Polymorphic type — think Java generic
From Chapter 5 (section 5.2.5)
Ad hoc polymorphism, same function name denotes different implementations depending on use
Overloading, compiler determines which to invoke, early binding
E.g. +
in Java,
Haskell type classes
Subtyping, runtime searches hierarchy of types, late binding
Called just polymorphism in Java, does not exist in Haskell
Parametric polymorphism, same implementation used for different types
Called generics in Java, Haskell just polymorphism
Use pattern matching on lists
Follow the types to implementations
Let form of the data guide form of the algorithm
Consider two basic cases: empty and nonempty lists
Int
(1)Type signature: sum' :: [Int] > Int
Sum of an empty list? sum' [] = 0
identity element $0 + x = x = x + 0$
Sum of nonempty list? sum' (x:xs) = x + sum' xs
sum' [2,4,6,8]
yields 2 + (4 + (6 + (8 + 0)))
Int
(2) sum' :: [Int] > Int  sum in Prelude
sum' [] = 0  nil list
sum' (x:xs) = x + sum' xs  nonnil list
Termination of sum' xs
? (What if xs
infinite?)
Precondition? Postcondition?
Backward recursive? Tail recursive?
Time complexity? Space complexity?
Int
(3)Exercise: Write variant of sum'
that uses a tail
recursive auxiliary function.
Integer
(1) product' :: [Integer] > Integer  product in Prelude
product' [] = 1  nil list
product' (0:_) = 0  0 at head
product' (x:xs) = x * product' xs  nonnil, nonzero
Identity element $1 + x = x = x + 0$
Zero element $0 * x = x * 0 = 0$
product' [2,4,6,8]
yields 2 * (4 * (6 * (8 * 1)))
Integer
(2) product' :: [Integer] > Integer  product in Prelude
product' [] = 1  nil list
product' (0:_) = 0  0 head, don't care
product' (x:xs) = x * product' xs  nonnil, nonzero
Termination of product' xs
?
Precondition? Postcondition?
Backward recursive? Tail recursive?
Time complexity? Space complexity?
sum'
and product'
sum'
and product'
similar computational patterns — note! (Ch. 15)
different base types, but both numbers
both return identity element for nil
zero handled differently by product'
length' :: [a] > Int  length in Prelude
length' [] = 0  nil list
length' (_:xs) = 1 + length' xs  nonnil list
Polymorphic list type
Don’t care about actual value — use _
Same correctness and complexity characteristics as sum'
Problem: Replace group of adjacent duplicate integers by one occurrence
What does adjacency mean?
fewer then two elements? $\Longrightarrow$ keep everything
first two elements duplicates? $\Longrightarrow$ remove one
first two elements not duplicates? $\Longrightarrow$ keep both
more than two adjacent duplicates? $\Longrightarrow$ step one element at time
Function examines first two elements
Termination of remdups xs
?
Time complexity? Space complexity?
How can we make work for polymorphic list?
[a] > [a]
?
Cannot compare everything for equality (e.g. functions)
Constrain to class Eq
, which
support ==
and /=
Class Ord
extends
Eq
with
ordered comparisons <
, <=
, >
, >=
Pattern  Argument  Succeeds?  Bindings 
1 
1 
yes  none 
x 
1 
yes  x
$\leftarrow$
1 
(x:y) 
[1,2] 
yes  x
$\leftarrow$
1 , y
$\leftarrow$
[2] 
(x:y) 
[[1,2]] 
yes  x
$\leftarrow$
[1,2] , y
$\leftarrow$
[] 
(x:y) 
["olemiss"] 
yes  x
$\leftarrow$
"olemiss" , y
$\leftarrow$
[] 
(x:y) 
"olemiss" 
yes  x
$\leftarrow$
’o’ , y
$\leftarrow$
"lemiss" 
Pattern  Argument  Succeeds?  Bindings 
(1:x) 
[1,2] 
yes  x
$\leftarrow$
[2] 
(1:x) 
[2,2] 
no  none 
(x:_:_:y) 
[1,2,3,4,5,6] 
yes  x
$\leftarrow$
1 , y
$\leftarrow$
[4,5,6] 
[] 
[] 
yes  none 
[x] 
["Cy"] 
yes  x
$\leftarrow$
"Cy" 
[1,x] 
[1,2] 
yes  x
$\leftarrow$
2 
Pattern  Argument  Succeeds?  Bindings 
[x,y] 
[1] 
no  none 
(x,y) 
(1,2) 
yes  x
$\leftarrow$
1 , y
$\leftarrow$
2 
For immutable xs
, neither
ys
nor zs
require copying
Efficient immutable structures via data sharing — persistent
But head xs
and
remdups xs
require
copying
Generalize tail
to drop'
that removes first n
elements
drop 2 "oxford"
$\Longrightarrow \cdots$
"ford"
Different approach than tail
— return
nil for nil list
Data sharing between argument and result
drop' :: Int > [a] > [a]  drop in Prelude
drop' n xs  n <= 0 = xs
drop' _ [] = []
drop' n (_:xs) = drop' (n1) xs
Termination of drop' n xs
? (note two base
cases)
Tail recursive?
Time complexity? Space complexity?
Generalize head
to take
that
returns first n
elements
take 2 "oxford"
$\Longrightarrow \cdots$
"ox"
What returned when list nil?
~~~{.haskell}
take' :: Int > [a] > [a]  take in Prelude
take' n _  n <= 0 = []
take' _ [] = []
take' n (x:xs) = x : take' (n1) xs
~~~
Termination of take' n xs
?
Data sharing?
Tail recursive?
Time complexity? Space complexity?
Polymorphism — powerful generalization mechanism
Immutable lists and data sharing
Follow the types to implementations
Let form of the data guide form of the algorithm
Library of useful functions
The Haskell code for this section is in file ListProg.hs
.