Lecture Notes, Week 08

• Polymorphic lists in OCaml
  • Resources
  • Lists
  • Exercise 01
  • The “plural” naming convention
  • Structural induction over lists
  • A sample of lists
  • Interlude
  • The list constructor, in actuality
  • Constructing lists: the atoi function
  • Destructuring nonempty 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 02
  • 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 the successive suffixes of a list
  • Exercise 03
  • Postlude
  • Resources
  • Version
• Polymorphic lists in OCaml, continued
  • Resources
  • Example: copying a list
  • Example: concatenating two lists
  • Food for thought
  • Exercise 04
  • On the right associativity of list concatenation
  • Example: duplicating the elements of a list
  • Exercise 05
  • 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 06
  • Exercise 07
  • Exercise 08
  • Exercise 09
  • Hint about Exercise 09
  • Exercise 10
  • Solution for Exercise 10
  • Historical note
  • Exercise 11
  • The logical counterpart of the map function for lists
  • The case of the last call in list_andmap and list_ormap
  • Postlude
  • 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 12
  • Solution for Exercise 12
  • First interlude
  • Second interlude
  • Exercise 13
  • Set intersection
  • Exercise 14
  • Solution for Exercise 14
  • Exercise 15
  • Exercise 16
  • Set difference
  • Exercise 17
  • Solution for Exercise 17
  • Exercise 18
  • Exercise 19
  • Exercise 20
  • Normalizing a list into the representation of a set
  • Exercise 21
  • Solution for Exercise 21
  • Exercise 22
  • Solution for Exercise 22
  • Computing the Cartesian product of two sets
  • Computing the Cartesian product of three sets
  • Exercise 23
  • Computing the powerset of a set
  • Exercise 24
  • A reflective interlude
  • Solution for Exercise 24
  • Aftermath
  • Exercise 25
  • A pragmatic approach to solving Exercise 25
  • After hours
  • Resources
  • Version
• Programming with lists
  • On enumerating the elements of a list
  • Exercise 26
  • Exercise 27
  • Exercise 28
  • Resources
  • Version
• Exercises for Week 08
  • Exercise 00
  • Mandatory exercises
  • Optional exercise
  • Version
• Index of concepts for Week 08
  • Version