RULE traverse = traverse_?

[Edward Kmett]

In general we don't currently go out of our way to export RULES that risk
breakage / semantics changes when the user supplies an instance that merely
doesn't satisfy the laws. The only ones that actually come to mind are the
ones hiding in Control.Arrow that I don't think anybody has looked at since
they were first written. We also have a few around realToFrac that have
questionable semantics that are a source of constant semantic pain as well.

A fairly exotic, but known, use-case for a Traversable is to exploit the
fact that we can extract given the data has a known shape and put the data
back in using the same shape. This sits behind a number of tricks in my
'lens' and 'ad' libraries.

If you are given a Traversable `f` in as input and spit it back out as
output, and you know nothing else about `f`, you can know that the `f` you
took in has the same number of entries as the one you spat out. This gives
a safe way to reason about zipping things that are derived from the same
input, which comes up a lot in the context of 'ad', etc.

This is done in one of two ways.

1.) You can linearize the structure and you recover the shape left to
right. This runs into the same problem as relying on toList to characterize
a Foldable. It ignores infinite cases. (For things like AD where the
infinite cases breaks down, thats fine, for other use cases it isn't.)

2.) Or you make an illegal Applicative that captures the structure as it
walks in a tree.

We can either replay the tree on the same Traversable (2a), or we can build
a heavier GADT during construction (2b).

Uniplate takes the (2a) approach, lens takes (2b) in e.g. A variant on the
construction of
http://hackage.haskell.org/package/lens-4.8/docs/src/Control-Lens-Internal-Magma.html#Molten
for instance can use the ability to 're-walk' a Traversable on the same
data type and get exactly the same arrangement of structures (including
fmaps) to avoid having to store the structure in a GADT.

Your proposed optimization breaks at least the (2a) approach above.

The key is don't get to know that `foldMap f` and `getConst . traverse
(Const . f)` for a given container build the exact same tree. One might
associate differently than the other, and in fact if you supplied a
definition of the Foldable in terms of foldr and the Traversable in terms
of traverse, this is precisely what happens, so it isn't even an academic
exercise. =/

Consequently, the walk to gather all the values in the tree can't be done
with traverse_, but can be done with traverse, despite the fact that we're
ignoring the result inside the monad.

-Edward

On Tue, Mar 31, 2015 at 6:43 AM, Joachim Breitner <mail at joachim-breitner.de>
wrote:

> Hi,
>
> Am Dienstag, den 31.03.2015, 12:33 +0200 schrieb Henning Thielemann:
> > If it works it will still surprise programmers if the magic does not
> > happen for a custom function similar to 'traverse'. E.g. I had a data
> > structure with two type parameters and thus two traverse function
> > parameters. I think it is better to tell programmers about the general
> > problem instead of fixing a selection of instances.
> True.
>
> But that is a problem with every compiler optimization. If you have a
> recursive function taking some Int, the compiler might be able to
> determine that you use it strictly and unbox it, and great things
> happen. It will not always figure this out, and if it does not, you have
> to help it (e.g. using strictness annotations).
>
> Greetings,
> Joachim
>
>
>
> --
> Joachim “nomeata” Breitner
>   mail at joachim-breitner.de • http://www.joachim-breitner.de/
>   Jabber: nomeata at joachim-breitner.de  • GPG-Key: 0xF0FBF51F
>   Debian Developer: nomeata at debian.org
>
> _______________________________________________
> Libraries mailing list
> Libraries at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/libraries/attachments/20150331/5d303a1e/attachment.html>