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@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@joachim-breitner.dehttp://www.joachim-breitner.de/
  Jabber: nomeata@joachim-breitner.de  • GPG-Key: 0xF0FBF51F
  Debian Developer: nomeata@debian.org

_______________________________________________
Libraries mailing list
Libraries@haskell.org
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries