[Haskell-cafe] 'Associative' order of calling

[Janis Voigtländer]

Yes, nicely put.

2015-10-25 13:03 GMT+01:00 Matteo Acerbi <matteo.acerbi at gmail.com>:

>
> 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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20151025/3b765f1e/attachment.html>