[Haskell-cafe] 'Associative' order of calling

Wed Oct 28 12:50:10 UTC 2015

Kim-Ee, I think you are overcomplicating things

No.

Your message contained lots of category-theory-speak that wasn’t called for.

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

No, it seems you haven’t understood the answer. At least, that was not the
answer.

2015-10-28 13:41 GMT+01:00 Kim-Ee Yeoh <ky3 at atamo.com>:

> 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/d49d87d4/attachment.html>