Lecturer: 穆信成 Shin-Cheng Mu

Bird-Meertens style functional program derivation.

• Slides for the course, and handout version of the slides.
• Exercise 1.
• Exercise 2.
• Supplementary Haskell and OCaml code.

Functional programming.

Day 1. The Expand/Reduce Transformation(2 hours)

• Prelude: Maximum Segment Sum
• Preliminaries
  • Functions
  • Data Structures
• The Expand/Reduce Transformation
  • Example: Sum of Squares
  • Proving Properties by Induction
  • Accumulating parameters
  • Tupling

Day 2. Fold (2 hours)

• Folds
  • The Fold-Fusion Theorem
  • More Useful Functions as Folds
  • Finally, Solving Maximum Segment Sum!
  • Folds on Trees
• Unfolds
  • Unfold on Lists
  • Folds v.s. Unfolds
• Hylomorphism
  • A Museum of Sorting Algorithms
  • Hylomorphism and Recursion
• Wrapping Up

Grading: Class Participation 10%, Homework 40%, Final (2007/07/13) 50%.

Some suggested reading:

• R. S. Bird, Introduction to Functional Programming using Haskell.
• R. S. Bird and O. de Moor, Algebra of Programming. Only the functional part.
• Some papers from H. Zantema on list segment problems.
• A. Kaldewaij, Programming: the derivation of algorithms.
• E. W. Dijkstra, A Discipline of Programming, for more interesting examples and exercises.