Lecture - Functional Programming, MT22, VIII

When all the conditions hold, what does fold fusion say about $\text{f} \cdot \text{fold g a}$?

\[\text{f} \cdot \text{fold g a} = \text{fold h b}\]

The fold fusion law is

\[\text{f} \cdot \text{fold g a} = \text{fold h b}\]

How many conditions are there for this to hold?

3

The fold fusion law is

\[\text{f} \cdot \text{fold g a} = \text{fold h b}\]

What, broadly, are the three conditions for this to hold?

The fold fusion law is

\[\text{f} \cdot \text{fold g a} = \text{fold h b}\]

What is the condition about stritcness?:: $f$ is strict, i.e. $f \bot = \bot$.

The fold fusion law is

\[\text{f} \cdot \text{fold g a} = \text{fold h b}\]

What is the condition about the zero value $b$?

\[\text{f a = b}\]

The fold fusion law is

\[\text{f} \cdot \text{fold g a} = \text{fold h b}\]

What is the tricky condition about “moving $f$ through”?

\[\text{f (g x y)} = \text{h x (f y)}\]

What is the identity $\text{id}$ function as a fold?

\[\text{fold (:) []}\]

How do you determine if a function $f$ can be written as a fold?

Use fold fusion with the identity fold,

\[\text{f}\cdot \text{fold (:) []}\]

When determining if a function $f$ is a fold on lists by composing it with the identity fold, i.e.

\[\text{f}\cdot \text{fold (:) []}\]

What does the tricky condition about “moving $f$ through” become?

\[\text{f (x : xs)} = \text{h x (f xs)}\]