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
  • Exercise 01
  • Interlude
  • Declaring a sum type, continued
  • The option type, revisited
  • Recursive data types
  • The list type, revisited
  • Interlude
  • 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 02
  • Exercise 03
  • Exercise 04
  • Partial solution for Exercise 04
  • Height
  • Mirror
  • A mirror in a mirror
  • Generating random binary trees of integers
  • Exercise 05
  • Generating random binary trees
  • Exercise 06
  • The mirror function, revisited
  • Interlude
  • The map function over polymorphic binary trees
  • Exercise 07
  • The logical counterpart of the map function for binary trees
  • Exercise 08
  • Calder mobiles
  • Exercise 09
  • Exercise 10
  • Partial solution for Exercise 10
  • Exercise 11
  • Partial solution for Exercise 11
  • Alternative partial solution for Exercise 11
  • Resources
  • Version
• The slash type error
  • The issue in a nutshell
  • The onion, yet again
  • Executive summary
  • Resources
  • Exercise 21
  • A tragically confusing story
  • 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 12
  • Exercise 13
  • Exercise 14
  • Exercise 15
  • Solution for Exercise 15
  • Exercise 16
  • Exercise 17
  • Exercise 18
  • Exercise 19
  • Exercise 20
  • Resources
  • Version
• Exercises for Week 10
  • Exercise 00
  • Mandatory exercises
  • Optional exercises
  • Practical exercise in preparation for Introduction to Data Structures and Algorithms
  • Version
• Index of concepts for Week 10
  • Version