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