I don't think I see what you are getting at, Tom. Let's consider the special case of non-empty lists. One fold-like function that has the property I think Charles meant by 3., would be one that works as follows: foldBalanced :: (a -> a -> a) -> [a] -> a foldBalanced f [x] = x foldBalanced f [x,y] = f x y foldBalanced f [x,y,z] = f x (f y z) foldBalanced f [x,y,z,u] = f (f x y) (f z u) ... -- I hope you can see the pattern (building f-application trees that are as balanced as possible) I don't see how this function can be written as g . foldl f z for some g and z. 2015-10-25 0:55 GMT+02:00 Tom Ellis < tom-lists-haskell-cafe-2013@jaguarpaw.co.uk>:
On Sat, Oct 24, 2015 at 08:12:11PM +0200, Janis Voigtländer wrote:
It has already been established in this thread what Charles meant by 3.
He meant that a fold-function that has the property he is after would guarantee that it:
a) takes all the content elements from a data structure, say x1,...,xn,
b) builds an application tree with the to-be-folded, binary operation f in the internal nodes of a binary tree, whose leafs, read from left to right, form exactly the sequence x1,...,xn,
c) evaluates that application tree.
Do you agree that what I describe above is a property of a given fold-like function, not of the f handed to that fold-like function?
And do you agree that what I describe above is a property that is weaker than (and so, in particular different from) for example the property "this fold-like function is foldl or foldr".
I do agree. I would be interested whether you think such a property could differ from my earlier proposed property:
"the function factors through `foldl f`", i.e. is `g . foldl f` for some `g`.
(Actually when I wrote that I suppose I meant `g . foldl f z` for some `g` and `z`)
Tom _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe