[Haskell-cafe] foldt fix proposal (HaskellWiki)

[Bertram Felgenhauer]

Dear Michael,

> I think I've found a mistake in foldt
> implementation on the Fold page[1] of the
> HaskellWiki.
> 
> foldt :: (a -> a -> a) -> a -> [a] -> a
> foldt f z [] = z
> foldt f z [x] = x    -- mistake?
> -- foldt f z [x] = f x z  -- fix proposal
> foldt f z xs = foldt f z (pairs f xs)
> 
> pairs :: (a -> a -> a) -> [a] -> [a]
> pairs f (x:y:t) = f x y : pairs f t
> pairs f t = t

In the context of the text on the fold page, I believe you're right,
since it describes z as an "initial value".

Nevertheless I like the definition on the wiki. Let me explain by
starting with what is, to my mind, the fundamental tree folding
function, which works with an associative function left and non-empty
lists:

  foldt f [x] = x
  foldt f xs = foldt f (pair f xs)

It has the nice property P that

  f (foldt f xs) (foldt f ys) = foldt f (xs ++ ys)

if f is associative and xs, ys are non-empty.

Now there are two fairly natural ways of making this function total.

One way is to work with a monoidal structure (so f comes with a unit z).
This results in the definition currently given on the wiki, and it
preserves property P, and even extends it to empty lists. But the wiki
page makes no mention of the fact that z should be a unit.

The second way is to add an extra element that corresponds to the
final (alternatively it could be the first...) element of the list
being processed. This corresponds to the idea of having an "initial
value", but property P is lost. This is what happens with your fix
proposal.

To summarize, I believe your fix proposal is ok, but there may be a
bigger story to be told about tree-like folds.

Cheers,

Bertram