Table of Contents

Lecturer: 穆信成 Shin-Cheng Mu

Bird-Meertens style functional program derivation.

- Supplementary Haskell code.

Functional programming.

- Prelude: Maximum Segment Sum
- Preliminaries
- Functions
- Data Structures

- The Expand/Reduce Transformation
- Example: Sum of Squares
- Proving Properties by Induction
- Accumulating parameters
- Tupling

- 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

- The Guarded Command Language
- Assignments and Selection
- Repetition

- Procedural Program Derivation
- Taking Conjuncts as Invariants
- Replacing Constants by Variables
- Strengthening the Invariant
- Tail Invariants

- Maximum Segment Sum, Procedually
- Wrapping Up

Grading: Class Participation 10%, Homework 40%, Final (2008/07/11) 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.