Lecture Notes, Week 10

• Concrete data types
  • Resources
  • Declaring new types in OCaml
  • Aliasing a pre-existing type
  • Aliasing a compound type
  • Aliasing a polymorphic type
  • Power and limitations of aliasing types
  • Datatype constructors
  • Declaring a sum type
  • A side remark
  • A useful sum type with 3 constructors
  • Interlude
  • Declaring a sum type, continued
  • The option type, revisited
  • Recursive data types
  • The list type, revisited
  • Exercise 1
  • Prelude
  • Mutually recursive data types
  • Grammatical correctness as type correctness
  • Resources
  • Version
• The proof is trivial (revisited)
  • Resources
  • The BNF of proofs
  • The data type for proofs
  • The point
  • Resources
  • Version
• Polymorphic binary trees in OCaml
  • Resources
  • Polymorphic binary trees
  • A sample of binary trees
  • Unparsing binary trees
  • Number of leaves
  • Number of nodes
  • Interlude
  • Exercise 2
  • Exercise 3
  • Exercise 4
  • Height
  • Mirror
  • A mirror in a mirror
  • Generating random binary trees of integers
  • The mirror function, revisited
  • Interlude
  • Calder mobiles
  • Exercise 5
  • The map function over polymorphic binary trees
  • The logical counterpart of the map function for binary trees
  • Exercise 6
  • Partial solution for Exercise 6
  • Exercise 7
  • Partial solution for Exercise 7
  • Alternative partial solution for Exercise 7
  • Resources
  • Version
• Generic programming with binary trees
  • Resources
  • The pattern of structural recursion
  • Example: unparsing a binary tree
  • Example: number of leaves
  • Example: number of nodes
  • Exercise 8
  • Exercise 9
  • Exercise 10
  • Exercise 11
  • Exercise 12
  • Exercise 13
  • Resources
  • Version
• Exercises for Week 10
  • Exercise 0
  • Mandatory exercises
  • Version