Table of Contents

Lecturer: 穆信成 Shin-Cheng Mu

Bird-Meertens style functional program derivation.

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.