List Basics and Concatenation

• Natural numbers are examples of building bigger objects from smaller ones
• Lists are analogous to natural numbers

List Basics

• Lists are familiar, like "to do" items or alphabetized names
• Base ten numerals (e.g., 30295) are lists of digits
• Words, sentences, and paragraphs can also be considered lists
• When thinking carefully about lists, a more formal approach is helpful
• Square brackets are used, common in programming languages, e.g., [1, 3, 2, 1]
• Order matters, so [1, 2, 3, 1] is different from [1, 3, 2, 1]
• Brackets and commas are not always needed, like writing 201 instead of [1, 0, 2]
• When dropping brackets/commas, it should be clear what the list represents

Concatenation

• Concatenation joins two lists, for example, [2, 5, 1] + [3, 0, 9] = [2, 5, 1, 3, 0, 9]
• Haskell uses ++, Python uses +, mathematicians use ⊗ or sometimes ·
• This text adopts Haskell's notation (+) for concatenation

Properties of Concatenation

• Associativity: L + (M + N) = (L + M) + N
• Identity: [] + L = L = L + [] - An empty list exists and serves as an identity
• Cancellative: If L + M = L + N, then M = N. Likewise, if L + N = M + N then L = M
• If [x] = [y], then x = y
• Lists are finite

Building Lists

• Lists can be built one item at a time, similar to incrementing natural numbers
• Prepending items is a common approach in computer science
• To get [a, b, e], start with [], then prepend e to get [e], then b to get [b, e], then a to get [a, b, e]
• Haskell notation: x : L indicates prepending
• "Cons" is the historical pronunciation, short for "construct"

Terminology

• Empty list: []
• Head: The first element of the list
• Tail: The rest of the list
• x : L represents a list with x as the head and L as the tail
• Square brackets can be used as abbreviations
• colon (:) associates from right to left
• a : b makes sense only when b is already a list

Homogeneous and Heterogeneous Lists

• List may consist of similar items (natural numbers/alphabetical chars)
• Lists can be heterogeneous (a mixed list); [4, a] is permitted by the vocabulary

Postulates for Lists

• Empty list has no head or tail: [] ≠ x : L
• Lists that are not empty can only be built one way
• Uniqueness of head and tail: if x : L = y : M, then x = y and L = M

Axiom of List Induction

• Anything not required by the vocabulary does not exist
• No lists can be eliminated without violating the basic vocabulary
• Every nonempty list has a head and a tail

Proof by Contraposition

• if L does not have a head or tail, then L is not a list

List Vocabulary

• The vocabulary for lists declares that anything can be an item on a list, including mathematical things
• The collection of mathematical "things" is open-ended

List Induction

• Achieves proofs about lists using a scheme almost identical to simple arithmetic induction

List Induction Steps

• Basis: Prove the property is true for []
• Inductive hypothesis: Assume property is true for list K
• Inductive step: Prove that for any thing x, the property is true for the list x : K
• Conclusion: Property is true for all lists

Recursion

• Useful for defining concepts associated with lists
• Every list has a length, which is a natural number

List Length

• Denoted by len(L)
• len([]) = 0
• len(x : K) = len(K) + 1

List Concatenation

• Defined as follows for list L and M:
• [] + M = M
• (x : K) + M = x : (K + M) for any thing x and any list K

Recursion for Lists

• Requires specifying how the operation affects the empty list and how it affects a list with a head and tail, lists of the form x : M

Proposition:

• [] is the identity for +
• [] + L = L and L + [] = L
• By definition, [] + L = L is always true
• The second equality is proven by list induction on L

List Concatenation Associativity

• For All lists L, M and N, L + (M + N) = (L + M) + N

Concatenation is Cancellative

• For lists L, M and N:
• If L + M = L + N, then M = N
• If L + N = M + N, then L = M

Length and Concatenation

• Length is a homomorphism with respect to concatenation and addition with the following properties:
• len([]) = 0
• For any lists L and M, len(L + M) = len(L) + len(M)

List Operation

• Appending an item to the end of a list. That is, define an algorithm for L ^ x, so that the result is L with x appended to the end
• For example, [3, 2, 7] ^ 5 should result it [3, 2, 7, 5].

List Reversal

• An operation rev on lists so that, for example, rev([2, 3, 4]) is [4, 3, 2]

List Structure

• In a list L, items appear in order
• Items are referred to via their position in list
• Can start counting either from 1 or from 0
• Starting from 0 makes calculations simpler
• Formula for indexed items in a List is as follows. Suppose L is a list and i is a natural number so that i < len(L)
• Note that len([]) = 0, so there is no i < len([])
• Li is defined as follows:
• []i is never defined because i < len([])
• (x : L)0 = x
• (x : L)k+1 = Lk provided that Lk is defined

List Slicing

• Extract the sublist of L consisting of items indexed i, i + 1, ... j – 1, writing L[i : j] for the list [ai, ai+1,... aj−1].

List Slicing Algorithm:

• For a list L and natural numbers i ≤ j ≤ len(L), L[i : j] is a list defined by the following:
• L[0:0] = []
• (x: L) [0: j] = x : (L[0: j])
• (x: L)[i: j] = L[i : j]

Prefix Order

• For Lists L and M, say that L is a Prefix of M, writing L ⊆ M, if L + D = M for some list D

List Monoids

• If X is a set, then (List[X], +, []) is the monoid consisting of lists with items drawn from X
• The set List[X] is defined by
• [] ∈ List[X]
• If x ∈ X and L ∈ List[X], then x : L∈ List[X]
• Nothing else is in List[X]

Homogeneous Lists

• We will commonly need to consider homogeneous lists — lists in which all items are drawn from the same collection
• When that collection is a clearly defined set, these lists also comprise a clearly defined set
• And since we already know that concatenation is an associative operation with identity [], this set actually forms a monoid

List Homomorphisms

• Homomorphism is a function h: X → Y satisfying
• h(e) = 1
• h(x+y) = h(x) * h(y)

List as Functor

• Definition: List extended to operations
• Suppose X and Y are sets, and f: X → Y is an operation that transforms elements of X into elements of Y
• Then define an operation from List[X] to List[Y] that applies f to each item on a list by recursion
• List[f]([]) = []
• List [f] (x: K) = f(x) : List[f] (K)

Folding

• Can be used to define list homomorphisms
• fold([]) = e
• fold(x: K) = x *fold(K)