Lecture Notes, Week 08

• Polymorphic lists in OCaml
  • Resources
  • Lists
  • The “plural” naming convention
  • Structural induction over lists
  • A sample of lists
  • The list constructor, in actuality
  • Constructing lists: the atoi function
  • Destructuring non-empty lists: list accessors
  • Prototypical skeleton of structurally recursive functions over lists
  • Unparsing polymorphic lists
  • The atoi function, revisited
  • About the nesting in the traces
  • Interlude
  • Unparsing polymorphic lists, refined
  • The atoi function, re2visited
  • Another interlude
  • Compound unparsing
  • Example: computing the length of a list
  • After hours
  • Destructuring lists conditionally: match expressions
  • Exercise 1
  • Prototypical skeleton of structurally recursive functions over lists, revisited
  • Example: unparsing polymorphic lists, revisited
  • Example: computing the length of a list, revisited
  • Example: computing the list of successive suffixes of a list
  • Exercise 2
  • Postlude
  • Resources
  • Version
• Polymorphic lists in OCaml, continued
  • Resources
  • Example: copying a list
  • Example: concatenating two lists
  • Food for thought
  • Exercise 3
  • On the right associativity of list concatenation
  • Example: duplicating the elements of a list
  • Exercise 4
  • Resources
  • Version
• The map function over polymorphic lists
  • Resources
  • Warmup #1: mapping the successor function
  • Warmup #2: mapping the predecessor function
  • Warmup #3: mapping the square function
  • Warmup #4: mapping the list-singleton function
  • Generalization: the map function for lists
  • Exercise 5
  • Exercise 6
  • Hint about Exercise 6
  • Exercise 7
  • Solution for Exercise 7
  • Exercise 8
  • The logical counterpart of the map function for lists
  • The case of the last call in list_andmap and list_ormap
  • Resources
  • Version
• Representing sets as lists
  • Resources
  • A practical consideration
  • Well-formed representation
  • Set membership
  • Set inclusion
  • Set equality
  • Adding an element to a set
  • Creating a random set
  • Set union
  • Exercise 9
  • Solution for Exercise 9
  • First interlude
  • Second interlude
  • Exercise 10
  • Set intersection
  • Exercise 11
  • Solution for Exercise 11
  • Exercise 12
  • Exercise 13
  • Set difference
  • Exercise 14
  • Solution for Exercise 14
  • Exercise 15
  • Exercise 16
  • Exercise 17
  • Normalizing a list into the representation of a set
  • Exercise 18
  • Solution for Exercise 18
  • Exercise 19
  • Solution for Exercise 19
  • Computing the Cartesian product of two sets
  • Computing the Cartesian product of three sets
  • Exercise 20
  • Computing the powerset of a set
  • Exercise 21
  • A reflective interlude
  • Solution for Exercise 21
  • Aftermath
  • Exercise 22
  • A pragmatic approach to solving Exercise 22
  • After hours
  • Resources
  • Version
• Exercises for Week 08
  • Exercise 0
  • Mandatory exercises
  • Exercise 23
  • Exercise 24
  • Version