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