[Haskell-cafe] 'Associative' order of calling

Tom Ellis tom-lists-haskell-cafe-2013 at jaguarpaw.co.uk
Fri Oct 23 16:46:11 UTC 2015


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


More information about the Haskell-Cafe mailing list