<div dir="ltr">Yes, nicely put.<br></div><div class="gmail_extra"><br><div class="gmail_quote">2015-10-25 13:03 GMT+01:00 Matteo Acerbi <span dir="ltr"><<a href="mailto:matteo.acerbi@gmail.com" target="_blank">matteo.acerbi@gmail.com</a>></span>:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><br>
Janis Voigtländer writes:<br>
<br>
> My messages this morning have decoupled the discussion from Traversable, by<br>
> specialising to one container type for which left-to-right is predefined.<br>
><br>
> In my mind, that gets to the heart of what Charles was after, namely the<br>
> "calling in an associative manner" thing, which is independent of the<br>
> question "how do we know right from left in the first place". Do the<br>
> considerations then make sense to you as well?<br>
<br>
Yes, they do.<br>
<br>
The examples related to non-empty lists were most clarifying.<br>
<br>
I agree that the interesting part was question 3, concerning which I<br>
think I have now understood your interpretation.<br>
<br>
As an exercise, I'll try to express it in my own words.<br>
<br>
Let's restrict to non-empty lists.<br>
<br>
I'll use these definitions:<br>
<br>
data NonEmptyList a = Last a | Cons a (NonEmptyList a)<br>
-- or the one from package semigroups<br>
<br>
data Tree a = Leaf a | Node (Tree a) (Tree a)<br>
<br>
foldTree :: (a -> a -> a) -> Tree a -> a<br>
foldTree f (Leaf a) = a<br>
foldTree f (Node x y) = f (foldTree f x) (foldTree f y)<br>
<br>
(<>) :: NonEmptyList a -> NonEmptyList a -> NonEmptyList a<br>
Last a <> ys = Cons a ys<br>
Cons a xs <> ys = Cons a (xs <> ys)<br>
<br>
toNonEmptyList :: Tree a -> NonEmptyList a<br>
toNonEmptyList (Leaf a) = Last a<br>
toNonEmptyList (Node x y) = toNonEmptyList x <> toNonEmptyList y<br>
<br>
Given the above, a fold h which calls the first argument "in an<br>
associative manner" is a function of type<br>
<br>
    h :: (a -> a -> a) -> NonEmptyList a -> a<br>
<br>
which can be equivalently expressed in terms of another function<br>
<br>
    h' :: NonEmptyList a -> Tree a<br>
<br>
such that<br>
<br>
    toNonEmptyList . h' = id<br>
<br>
as<br>
<br>
    h f = foldTree f . h'<br>
<br>
.<br>
<br>
h' is allowed to build an application tree whose shape can be a function<br>
of the input list, but its leaves, considered in left-to-right order,<br>
must contain precisely the input sequence.<br>
<br>
Is this correct?<br>
<br>
Best,<br>
Matteo<br>
</blockquote></div><br></div>