Lecture Notes, Week 13

• From concrete data types to abstract data types
  • Version
• Environments
  • Exercise 1
  • Environments as association lists
  • Environments as functions
  • Postlude
  • Resources
  • Version
• Queues
  • An abstract data type
  • Last in, first out (LIFO)
  • Exercise 2
  • First in, first out (FIFO)
  • Exercise 3
  • Exercise 4
  • Representing a LIFO queue with a list
  • Representing a FIFO queue with a list
  • Representing a FIFO queue with a list, Version 1: the first (to be dequeued) shall be the first (in the list)
  • Representing a FIFO queue with a list, Version 2: the first (to be dequeued) shall be the last (in the list)
  • Representing a FIFO queue with a list, Version 3: amortizing space and time opportunistically
  • Representing a FIFO queue with a list, Version 4: amortizing space and time structurally
  • Representing a FIFO queue with a list, Version 5: a functional representation
  • Exercise 5
  • Exercise 6
  • Exercise 7
  • Resources
  • Version
• Modules in OCaml
  • Syntax
  • Interlude
  • A first module
  • Exercise 8
  • Solution for Exercise 8
  • A second module
  • A third module
  • A fourth module, with nesting
  • Exercise 9
  • Solution for Exercise 9
  • Declaring the signature of a module
  • The first module, revisited
  • Exercise 10
  • Solution for Exercise 10
  • The second module, revisited
  • Exercise 11
  • Solution for Exercise 11
  • The third module, revisited
  • Exercise 12
  • Solution for Exercise 12
  • Functors
  • Interlude
  • The second module, re2visited
  • Exercise 13
  • Solution for Exercise 13
  • Functors that return other functors
  • Interlude
  • Functors that are applied to other functors
  • Postlude
  • Resources
  • Version
• From concrete data types to abstract data types, revisited
  • Example: lists of integers as an abstract data type
  • A first implementation: native lists
  • A second implementation: a left-to-right representation
  • A third implementation: a right-to-left representation
  • Summary and conclusion
  • Resources
  • Version
• Environments, revisited
  • Environments as association lists, revisited
  • Environments as functions, revisited
  • Resources
  • Version
• Queues, revisited
  • Representing a LIFO queue with a list, revisited
  • Representing a FIFO queue with a list, Version 1, revisited
  • Representing a FIFO queue with a list, Version 2, revisited
  • Representing a FIFO queue with a list, Version 3, revisited
  • Representing a FIFO queue with a list, Version 4, revisited
  • Representing a FIFO queue with a list, Version 5, revisited
  • Exercise 7, revisited
  • Resources
  • Version
• Unit tests using modules
  • Environments
  • Unit-test functions
  • Unit-test functors
  • Making do without the dot notation
  • Exercise 14
  • Solution for Exercise 14
  • Resources
  • Version
• Exercises for Week 13
  • Exercise 0
  • Mandatory exercises
  • Exercise 15
  • Resources
  • Version