[Haskell-cafe] 'Associative' order of calling

[Matteo Acerbi]

Janis Voigtländer writes:

> My messages this morning have decoupled the discussion from Traversable, by
> specialising to one container type for which left-to-right is predefined.
>
> In my mind, that gets to the heart of what Charles was after, namely the
> "calling in an associative manner" thing, which is independent of the
> question "how do we know right from left in the first place". Do the
> considerations then make sense to you as well?

Yes, they do.

The examples related to non-empty lists were most clarifying.

I agree that the interesting part was question 3, concerning which I
think I have now understood your interpretation.

As an exercise, I'll try to express it in my own words.

Let's restrict to non-empty lists.

I'll use these definitions:

data NonEmptyList a = Last a | Cons a (NonEmptyList a)
-- or the one from package semigroups

data Tree a = Leaf a | Node (Tree a) (Tree a)

foldTree :: (a -> a -> a) -> Tree a -> a
foldTree f (Leaf a) = a
foldTree f (Node x y) = f (foldTree f x) (foldTree f y)

(<>) :: NonEmptyList a -> NonEmptyList a -> NonEmptyList a
Last a <> ys = Cons a ys
Cons a xs <> ys = Cons a (xs <> ys)

toNonEmptyList :: Tree a -> NonEmptyList a
toNonEmptyList (Leaf a) = Last a
toNonEmptyList (Node x y) = toNonEmptyList x <> toNonEmptyList y

Given the above, a fold h which calls the first argument "in an
associative manner" is a function of type

    h :: (a -> a -> a) -> NonEmptyList a -> a

which can be equivalently expressed in terms of another function

    h' :: NonEmptyList a -> Tree a

such that

    toNonEmptyList . h' = id

as

    h f = foldTree f . h'

.

h' is allowed to build an application tree whose shape can be a function
of the input list, but its leaves, considered in left-to-right order,
must contain precisely the input sequence.

Is this correct?

Best,
Matteo