Lecture Notes, Week 09

• Reversing lists
  • Resources
  • Reversing a list
  • Reversing a list, Version 1: the first shall be the last
  • Reversing a list, Version 2: the last shall be the first
  • Reversing a list, Version 3: trading space for time
  • Reversing a list, Version 4: using an accumulator
  • Exercise 01
  • Exercise 02
  • Exercise 03
  • ‘lude
  • Exercise 04
  • Resources
  • Version
• Programming using accumulators
  • Resources
  • Adding natural numbers: the unit tests
  • Adding natural numbers: Version 1, lambda-dropped
  • Adding natural numbers: Version 2, lambda-lifted
  • Exercise 05
  • Adding natural numbers: Version 3, using an accumulator
  • Accumulators in a nutshell
  • A converse of atoi: iota
  • Exercise 06
  • Interlude about List.init
  • Computing the length of a list using an accumulator
  • Computing factorial numbers using an accumulator
  • Interlude
  • Sets as lists, revisited
  • Exercise 07
  • Solution for Exercise 07
  • Exercise 08
  • Exercise 09
  • Exercise 10
  • Exercise 11
  • Resources
  • Version
• Generic programming with lists
  • Resources
  • Structural recursion over lists
  • Express interlude
  • Example: computing the length of a list, generically
  • Example: unparsing a polymorphic list in long hand, generically
  • Example: unparsing a polymorphic list in short hand, generically
  • Example: duplicating the elements of a list, generically
  • Example: concatenating two lists, generically
  • Example: list membership, generically
  • Exercise 12
  • Sets as lists, re2visited
  • Exercise 13
  • Solution for Exercise 13
  • Exercise 14
  • Exercise 15
  • Exercise 16
  • Example: the Cartesian product of two sets, generically
  • Example: the Cartesian product of three sets, generically
  • Exercise 17
  • Structural recursion over lists using an accumulator
  • Express interlude
  • Example: computing the length of a list using an accumulator, generically
  • Exercise 18
  • Sets as lists, re3visited
  • Exercise 19
  • Solution for Exercise 19
  • Exercise 20
  • Exercise 21
  • Exercise 22
  • The map function for lists, generically
  • Aftermath
  • Exercise 23
  • Exercise 24
  • Postlude
  • Post-poslude
  • Exercise 25
  • Partial solution for Exercise 25
  • Solution for Exercise 25
  • Exercise 26
  • Exercise 27
  • Resources
  • Version
• The Art of Computer Science
  • Resources
  • Representing finite sets as lists without repetitions, Take 0
  • Representing finite sets as lists without repetitions, Take 1
  • Representing finite sets as binary trees without repetitions, Take 0
  • Representing finite sets as binary trees without repetitions, Take 1
  • The turning point: from linear to logarithmic
  • Natural numbers, revisited: from mathematical induction (in base 1) to structural induction (in base 2)
  • Exercise 28
  • Solution for Exercise 28
  • Exercise 29
  • Solution for Exercise 29
  • Exercise 30
  • Computing the powerset of a set, revisited
  • Exercise 31
  • Resources
  • Version
• The polymorphic option type
  • Exercise 32
  • Implementing total versions of partial function using the option type
  • Exercise 33
  • Exercise 34
  • Analysis of Exercise 34, in the form of an interlude
  • Exercise 35
  • Exercise 36
  • Partial solution for Exercise 36
  • Exercise 37
  • Solution for Exercise 37
  • Executive summary
  • Exercise 38
  • Hint about Exercise 38
  • More hints about Exercise 38, in the form of a Socratic dialogue
  • Exercise 39
  • Solution for Exercise 39
  • Exercise 40
  • Resources
  • Version
• Exercises for Week 09
  • Exercise 00
  • Mandatory exercises
  • Optional exercises
  • Exercise 41
  • Version
• Index of concepts for Week 09
  • Version