[Haskell-cafe] 'Associative' order of calling

[Kim-Ee Yeoh]

On Sun, Oct 25, 2015 at 1:17 PM, Janis Voigtländer <
janis.voigtlaender at gmail.com> wrote:

> Kim-Ee, I think you are overcomplicating things
>

No.

Matteo cited a paper on traversables and you added a rejoinder. So it
wasn't me who introduced data abstraction.

Also, OP explicitly asked about a fold "on a set of data". Only later, when
requested for an example, did he give lists.

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

And look at what we have: A definitive answer to OP's question:

Question: What is a fold of type "(a -> a -> a) -> [a] -> a" that promises
to call its first parameter "associatively"?

Answer: It is a fold equivalent to a fold1 (left or right, it doesn't
matter).

That's nice.

But is that all we can come up with? Does it really do justice to the
original question? Viz.

"Is there a name for a fold that promises to call a function such that only
an associative function will always return the same result. Or in other
words, it has the property that it promises to call a function
"associatively" on a set of data?"

The challenge becomes:

* generalize the result to fearsomely complicated "arbitrary data
structures"
* answer the original question in a holistic spirit





> 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/20151028/56e528eb/attachment.html>