In the end of FLOLAC ’10 I had a chance to show the students, in 25 minutes, what functional program calculation is about. The student have just been exposed to functional programming a week ago in a three-hour course, after which they have written some simple programs handling concrete data but may have problem grasping those more abstract concepts like folds. I have talked to them about maximum segment sum way too many times (in the context of imperative program derivation, though), and it is perhaps too complex to cover in 25 minutes. The steep list problem, on the other hand, can be dealt with in 5 minutes. Thus I need another example.

This is what I eventually came up with: given a list of numbers `a₀, a₁, a₂ ... a`

and a constant _{n}`X`

, compute `a₀ + a₁X, + a₂X² + ... + a`

. In Haskell it can be specified as a one-liner:_{n}X^{n}

```
```

` poly as = sum (zipWith (×) as (iterate (×X) 1))`

```
```

`One problem of this example is that the specification is already good enough: it is a nice linear time algorithm. To save some multiplications, perhaps, we may try to further simplify it.`

It is immediate that `poly [] = 0`

. For the non-empty case, we reason:

```
```

```
poly (a : as)
= { definition of poly }
sum (zipWith (×) (a:as) (iterate (×X) 1))
= { definition of iterate }
sum (zipWith (×) (a:as) (1 : iterate (×X) X))
= { definition of zipWith }
sum (a : zipWith (×) as (iterate (×X) X))
= { definition of sum }
a + sum (zipWith (×) as (iterate (×X) X))
```

```
```

`The expression to the right of `

`a +`

is unfortunately not `poly as`

— the last argument to `iterate`

is `X`

rather than `1`

. One possibility is to generalise `poly`

to take another argument. For this problem, however, we can do slightly better:

```
```

```
a + sum (zipWith (×) as (iterate (×X) X))
= { since iterate f (f b) = map f (iterate f b) }
a + sum (zipWith (×) as (map (×X) (iterate (×X) 1)))
= { zipWith (⊗) as . map (⊗X) = map (⊗X) . zipWith (⊗) as
if ⊗ associative }
a + sum (map (×X) (zipWith (×) as (iterate (×X) 1)))
= { sum . map (×X) = (×X) . sum }
a + (sum (zipWith (×) as (iterate (×X) 1))) × X
= { definition of poly }
a + (poly as) × X
```

```
```

We have thus come up with the program

```
```

```
poly [] = 0
poly (a : as) = a + (poly as) × X
```

```
```

Besides the definitions of `sum`

, `zipWith`

, `iterate`

, etc, the rules used include:

`map f (iterate f x) = iterate f (f x)`

`zipWith (⊗) as . map (⊗X) = map (⊗X) . zipWith (⊗) as`

if`⊗`

associative`sum . map (×X) = (×X) . sum`

, a special case of`foldr ⊕ e . map (⊗X) = (⊗X) . foldr ⊕ e`

if`(a ⊕ b) ⊗ X = (a ⊗ X) ⊕ (b ⊗ X)`

and`e ⊗ X = e`

.

Well, this is not a very convincing example. Ideally I’d like to have a derivation, like the steep list, where we gain some improvement in complexity by calculation.

What is your favourite example for functional program calculation?