[Haskell-cafe] 'Associative' order of calling

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
foldLike f.

So, let's specialize. Let's consider only the case of non-empty lists.
Then, candidate functions for "foldlike functions" will be functions of
this type:

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
one
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
good
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
we?

There was:

> 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
others.

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
no meaning.

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
> others?
>
> Is the meaning of "all" referentially transparent? That turns out to be a
> subtle point, as this convo shows:
>
>
> http://haskell.1045720.n5.nabble.com/A-Proposed-Law-for-Foldable-tp5765339.html
>
> 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...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20151025/ba7ea0ff/attachment-0001.html>