Exploring Languages
with Interpreters
and Functional Programming

Chapter 13
List Programming

H. Conrad Cunningham (after class)

24 September 2018

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.

Lecture Goals

Introduce immutable list data structures
Examine first-order, polymorphic, list processing functions
Reinforce techniques for correct and efficient functional programs
Examine data sharing in lists
Examine library of useful functions

Haskell Data Types

Immutable:: 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, 13-18
User-defined (algebraic) data types — Ch. 21

Lists

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:[]

List Syntactic Sugar

Syntactic sugar:: 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

List Operations

Constructor :
Selector head (h:t) $\Longrightarrow$ h
Selector tail (h:t) $\Longrightarrow$ t
Prelude library functions: length, sum, product, take, drop, ++, reverse

String

String type synonym for [Char]
```
    type String = [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 :: String -> Int
    len s  =  if s == [] then 0 else 1 + len (tail s)

Evaluation (1)

	`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"`

Evaluation (2)

$\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")`

Evaluation (4)

$\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"))`

Evaluation (5)

$\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 "")))`

Evaluation (6)

$\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`

Evaluation (7)

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

Polymorphic Lists

Polymorphism:: property of having “many shapes”

General length function for more types: use type variable
```
    len :: [a] -> Int
```

Polymorphic type — think Java generic

    head :: [a] -> a
    tail :: [a] -> [a]
    (:)  :: a -> [a] -> [a]

Kinds of Polymorphism (1)

From Chapter 5 (section 5.2.5)

Ad hoc polymorphism, same function name denotes different implementations depending on use
1. Overloading, compiler determines which to invoke, early binding
  
  E.g. + in Java, Haskell type classes
2. Subtyping, runtime searches hierarchy of types, late binding
  
  Called just polymorphism in Java, does not exist in Haskell

Kinds of Polymorphism (2)

Parametric polymorphism, same implementation used for different types

Called generics in Java, Haskell just polymorphism

Programming with List Patterns

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

Add List of `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' :: [Int] -> Int  -- sum in Prelude
    sum' []     = 0           -- nil list 
    sum' (x:xs) = x + sum' xs -- non-nil list

sum' [2,4,6,8] yields 2 + (4 + (6 + (8 + 0)))

Add List of `Int` (2)

    sum' :: [Int] -> Int  -- sum in Prelude 
    sum' []     = 0           -- nil list 
    sum' (x:xs) = x + sum' xs -- non-nil list

Termination of sum' xs ? (What if xs infinite?)
Precondition? Postcondition?
Backward recursive? Tail recursive?
Time complexity? Space complexity?

Add List of `Int` (3)

Exercise: Write variant of sum' that uses a tail recursive auxiliary function.

Multiply List of `Integer` (1)

    product' :: [Integer] -> Integer  -- product in Prelude
    product' []     = 1               -- nil list
    product' (0:_)  = 0               -- 0 at head
    product' (x:xs) = x * product' xs -- non-nil, non-zero

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)))

Multiply List of `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 -- non-nil, non-zero

Termination of product' xs ?
Precondition? Postcondition?
Backward recursive? Tail recursive?
Time complexity? Space complexity?

Comparison of `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 of List

    length' :: [a] -> Int  -- length in Prelude
    length' []     = 0              -- nil list
    length' (_:xs) = 1 + length' xs -- non-nil list

Polymorphic list type
Don’t care about actual value — use _
Same correctness and complexity characteristics as sum'

Adjacent Duplicates (1)

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

Adjacent Duplicates (2)

Function examines first two elements

   remdups :: [Int] -> [Int]
   remdups (x:y:xs)  -- note order of equations
     | x == y = remdups (y:xs) 
     | x /= y = x : remdups (y:xs) 
   remdups xs = xs

Termination of remdups xs?
Time complexity? Space complexity?

Adjacent Duplicates (3)

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 /=

    remdups :: Eq a => [a] -> [a]
    remdups (x:y:xs) 
        | x == y = remdups (y:xs) 
        | x /= y = x : remdups (y:xs) 
    remdups xs = xs

Class Ord extends Eq with ordered comparisons <, <=, >, >=

More List Patterns (1)

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"`

More List Patterns (2)

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`

More List Patterns (3)

Pattern	Argument	Succeeds?	Bindings
`[x,y]`	`[1]`	no	none
`(x,y)`	`(1,2)`	yes	`x` $\leftarrow$ `1`, `y` $\leftarrow$ `2`

Data Sharing

    xs = [1,2,3]
    ys = 0:xs 
    zs = tail xs

Data sharing in lists

For immutable xs, neither ys nor zs require copying
Efficient immutable structures via data sharing — persistent
But head xs and remdups xs require copying

Drop Elements from List (1)

Generalize tail to drop' that removes first n elements

    drop' :: Int -> [a] -> [a]  -- drop in Prelude
    drop' n xs | n <= 0 = xs 
    drop' _ []          = []
    drop' n (_:xs)      = drop' (n-1) xs

drop 2 "oxford" $\Longrightarrow \cdots$ "ford"
Different approach than tail — return nil for nil list
Data sharing between argument and result

Drop Elements from List (2)

        drop' :: Int -> [a] -> [a]  -- drop in Prelude
        drop' n xs | n <= 0 = xs 
        drop' _ []          = []
        drop' n (_:xs)      = drop' (n-1) xs

Termination of drop' n xs? (note two base cases)
Tail recursive?
Time complexity? Space complexity?

Take Elements from List (1)

Generalize head to take that returns first n elements

    take' :: Int -> [a] -> [a] -- take in Prelude
    take' n _ | n <= 0 = []
    take' _ []         = []
    take' n (x:xs)     = x : take' (n-1) xs

take 2 "oxford" $\Longrightarrow \cdots$ "ox"
What returned when list nil?

Take Elements from List (2)

~~~{.haskell}
    take' :: Int -> [a] -> [a] -- take in Prelude
    take' n _ | n <= 0 = []
    take' _ []         = []
    take' n (x:xs)     = x : take' (n-1) xs
~~~

Termination of take' n xs?
Data sharing?
Tail recursive?
Time complexity? Space complexity?

Key Ideas

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

Code

The Haskell code for this section is in file ListProg.hs.

Exploring Languages with Interpreters and Functional Programming Chapter 13 List Programming

List Programming