Lecture Notes, Week 11

• Evaluation order
  • Call by value
  • Call by name
  • Call by need
  • Example: a non-strict function
  • Example: a linear function
  • Example: a non-linear function
  • Left-to-right call by value
  • Right-to-left call by value
  • The case of the Scheme programming language
  • Exercise 1
  • Solution for Exercise 1
  • Exercise 2
  • Version
• Demand-driven computation
  • Demand-driven computation in OCaml
  • A simple example of nested demands
  • The same simple example of nested demands, just different
  • Summa summorum: demand-driven computation
  • Postlude
  • Post-postlude
  • Version
• Lazy lists
  • Version
• Streams
  • How to destructure a stream: stream accessors
  • How to construct a stream: the stream maker
  • Example: the stream of natural numbers
  • Exercise 3
  • Example: the stream of positive integers
  • Exercise 4
  • Example: the stream of even natural numbers
  • Exercise 5
  • Exercise 6
  • Exercise 7
  • Example: the stream of odd natural numbers
  • Exercise 8
  • How to merge streams
  • Exercise 9
  • Solution for Exercise 9
  • Exercise 10
  • Solution for Exercise 10
  • Exercise 11
  • Solution for Exercise 11
  • Exercise 12
  • Exercise 13
  • Exercise 14
  • Exercise 15
  • Exercise 16
  • Exercise 17
  • Exercise 18
  • Exercise 19
  • A beautiful story, to close
  • Exercise 20
  • Exercise 21
  • Resources
  • Version
• Programming with streams
  • Resources
  • Example: duplicating the elements of a stream
  • Mapping functions over streams
  • Filtering out
  • Exercise 22
  • Eratosthenes’s sieve
  • Abstract stream transducers
  • More abstract stream transducers
  • The stream of Fibonacci numbers
  • Food for thought
  • The stream of Fibonacci numbers, incrementally
  • More food for thought
  • Interlude
  • Exercise 23
  • Postlude
  • Resources
  • Acknowledgment
  • Version
• The samefringe problem
  • Resources
  • The samefringe problem: the unit tests
  • Fringe-preserving transformations
  • The samefringe problem: the unit tests, revisited
  • The fringe of a tree as a list
  • The fringe of a tree as a list, revisited
  • The samefringe problem, Take 0: easy does it
  • The samefringe problem, Take 1: minimizing space
  • The samefringe problem, Take 2: trading time for space
  • The samefringe problem, Take 3: constructing only one fringe
  • Exercise 24
  • The samefringe problem, Take 4: accumulating right subtrees
  • The samefringe problem, Take 5: incrementally rotating the given trees to the right
  • Resources
  • Version
• Demand-driven computation, revisited
  • Resources
  • Desugaring a conditional expression into a function call
  • Delaying an evaluation without using the Lazy library
  • Interlude
  • Thunks
  • Thunks by value
  • Exercise 25
  • Thunks by name
  • Thunks by need
  • Exercise 26
  • Demand-driven computation in OCaml, revisited
  • A simple example of nested demands, revisited
  • The same simple example of nested demands, just different, revisited
  • Summa summorum: demand-driven computation
  • Resources
  • Version
• Exercises for Week 11
  • Exercise 0
  • Mandatory exercises
  • Version