[Haskell-cafe] 'Associative' order of calling
matteo.acerbi at gmail.com
Sun Oct 25 12:03:04 UTC 2015
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
toNonEmptyList . h' = id
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?
More information about the Haskell-Cafe