[Haskell-cafe] 'Associative' order of calling
Kim-Ee Yeoh
ky3 at atamo.com
Sun Oct 25 03:19:26 UTC 2015
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/4ae2977f/attachment.html>
More information about the Haskell-Cafe
mailing list