[Haskell-cafe] 'Associative' order of calling
janis.voigtlaender at gmail.com
Sun Oct 25 06:17:17 UTC 2015
Kim-Ee, I think you are overcomplicating things (and on the specific
question of 2. vs. 3.: no, what I described was specifically meant to
capture Charles's 3., not 2. point; note that my "application trees" could
be balanced in any way, rather than being completely left-nested).
In fact, the discussion of "arbitrary data structures" (in this thread in
general) distracts a lot from the properties under consideration, and from
even first finding out whether they are properties of foldLike or of f in
So, let's specialize. Let's consider only the case of non-empty lists.
Then, candidate functions for "foldlike functions" will be functions of
foldLike : (a -> a -> a) -> [a] -> a
Here are some candidates (I give only an equation for four element lists in
each case, but I assume everyone has enough imagination to see how these
could be extended to other lists in an intended way):
foldLike1 f [a,b,c,d] =  -- throws away stuff
foldLike2 f [a,b,c,d] = f a (f b (f c d)) -- we have all ancountered this
foldLike3 f [a,b,c,d] = f (f (f a b) c) d -- also looks familiar
foldLike4 f [a,b,c,d] = f (f a b) (f c d) -- that's a "new" one, but looks
foldLike5 f [a,b,c,d] = f a a -- probably not a very popular one
foldLike6 f [a,b,c,d] = f (f c a) (f b d) -- a reasonable one, for example
there's a Traversable instance that leads to this one; but still, it's not
one that Charles would like, I think
So now we can ask which of these satisfy Charles's 1., 2., 3. points. Can't
> 1. Promises to call f on all data (does not have any guarantees on order)
This is satisfied by foldLike2, foldLike3, foldLike4, and foldLike6, but
not by the others.
> 2. Promises to call f on all data in order (like a left fold)
This is satisfied by foldLike3, but not by the others.
> 3. Promises to call f "associatively" (perhaps can be formalized as an in
order break down of the data into tree structures)
This is satisfied by foldLike2, foldLike3, and foldLike4, but not by the
Since I am able to tell, for a given foldLike candidate, whether or not it
satisfies 3. (for example, I could specifically see that foldLike6 does not
satisfy 3., while it does satisfy 1.), it cannot be maintained that 3. has
Note: Nothing in the above makes any assumptions about f. Whether or not f
is an associative function is irrelevant for what is asked here.
2015-10-25 4:19 GMT+01:00 Kim-Ee Yeoh <ky3 at atamo.com>:
> On Sun, Oct 25, 2015 at 1:12 AM, Janis Voigtländer <
> janis.voigtlaender at gmail.com> 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.
> Isn't this what Charles meant by his 2nd property:
> > 2. Promises to call f on all data in order (like a left fold)
> What about his 3rd?
> 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?
> Before discussing a property of X, isnt it worth asking what X even means?
> The folds whose meanings are crystal clear are the arrows out of initial
> objects in the category of F-algebras.
> They are crystal clear because they couple as one with the data definition
> spelled out in full.
> In the quest for useful generalizations of catamorphisms, that coupling
> with the data definition continues to be assumed.
> Observe, for instance:
> > a) takes all the content elements from a data structure, say x1,...,xn,
> Does a foliar data structure have a canonical flattening out of its
> leaves? Are there symmetric canonicalizations? How is one selected over the
> Is the meaning of "all" referentially transparent? That turns out to be a
> subtle point, as this convo shows:
> With the theory of F-algebras, we started with precise notions of data and
> folds came for free.
> But data can be overspecified. And also, the folds among swathes of data
> suggest useful generalizations.
> So now, a raft of proto-precise and necessarily psychological notions of
> Foldable waded in, and since then it's been fun playing sorting games with
> shape blocks and holes to squeeze them into.
> Fun is good. It's a stage in the journey to knowledge.
> 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".
>> 2015-10-24 19:55 GMT+02:00 Kim-Ee Yeoh <ky3 at atamo.com>:
>>> On Sun, Oct 25, 2015 at 12:42 AM, Matteo Acerbi <matteo.acerbi at gmail.com
>>> > wrote:
>>>> For what concerns question 3, I didn't understand the idea of calling a
>>>> function "associatively".
>>> This. Associativity is a property of binary operators. It's not a
>>> property of the catamorphism 'calling' on a given binary operator.
>>> Also, when Charles writes: "Then it goes on to use f in "thisFold f
>>> [0,1,2]" like "f (1 (f 0 2))""
>>> commutativity appears to raise its head.
>>> -- Kim-Ee
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Haskell-Cafe