On Fri, Oct 23, 2015 at 06:38:22PM +0200, Francesco Ariis wrote:
On Fri, Oct 23, 2015 at 05:12:06PM +0100, Tom Ellis wrote:
On Fri, Oct 23, 2015 at 12:07:57PM -0400, Charles Durham wrote:
I can think of a few properties that folds can honor:
1. Promises to call f on all data (does not have any guarantees on order) 2. Promises to call f on all data in order (like a left fold) 3. Promises to call f "associatively" (perhaps can be formalized as an in order break down of the data into tree structures)
I'm assuming at least #1 has a well known name (something completeness?)
2. doesn't have any meaning in a pure language, I think. What would it mean to call f on data out of order?
He gave an example in his previous email:
On Fri, Oct 23, 2015 at 11:45:13AM -0400, Charles Durham wrote:
Let's say you have a function "thisFold :: (a -> a -> a) -> [a] -> a"
and it says that the function 'f' passed in must be associative.
Then it goes on to use f in "thisFold f [0,1,2]" like "f (1 (f 0 2))". Obviously f is still associative, but 'thisFold' did not call f 'associatively' on the data.
Oh, I think I see. Not temporal order, but an order "determined" by `f`. In this case I would just say that property is that "the function factors through `foldl f`", i.e. is `g . foldl f` for some `g`. Tom