<div dir="ltr"><div><div>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.</div></div><div><br></div>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.<div><br></div><div>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.<br><div><br></div><div>This is done in one of two ways.</div><div><br></div><div>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.)</div><div><br></div><div>2.) Or you make an illegal Applicative that captures the structure as it walks in a tree. </div><div><br></div><div>We can either replay the tree on the same Traversable (2a), or we can build a heavier GADT during construction (2b).</div><div><br></div><div>Uniplate takes the (2a) approach, lens takes (2b) in e.g. A variant on the construction of <a href="http://hackage.haskell.org/package/lens-4.8/docs/src/Control-Lens-Internal-Magma.html#Molten">http://hackage.haskell.org/package/lens-4.8/docs/src/Control-Lens-Internal-Magma.html#Molten</a> 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. </div><div><br></div><div><div>Your proposed optimization breaks at least the (2a) approach above.</div></div><div><br></div><div>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. =/<br></div><div><div></div></div><div><br></div><div>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.</div><div><br></div><div>-Edward</div></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Mar 31, 2015 at 6:43 AM, Joachim Breitner <span dir="ltr"><<a href="mailto:mail@joachim-breitner.de" target="_blank">mail@joachim-breitner.de</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hi,<br>
<span class=""><br>
Am Dienstag, den 31.03.2015, 12:33 +0200 schrieb Henning Thielemann:<br>
> If it works it will still surprise programmers if the magic does not<br>
> happen for a custom function similar to 'traverse'. E.g. I had a data<br>
> structure with two type parameters and thus two traverse function<br>
> parameters. I think it is better to tell programmers about the general<br>
> problem instead of fixing a selection of instances.<br>
</span>True.<br>
<br>
But that is a problem with every compiler optimization. If you have a<br>
recursive function taking some Int, the compiler might be able to<br>
determine that you use it strictly and unbox it, and great things<br>
happen. It will not always figure this out, and if it does not, you have<br>
to help it (e.g. using strictness annotations).<br>
<div class="HOEnZb"><div class="h5"><br>
Greetings,<br>
Joachim<br>
<br>
<br>
<br>
--<br>
Joachim “nomeata” Breitner<br>
<a href="mailto:mail@joachim-breitner.de">mail@joachim-breitner.de</a> • <a href="http://www.joachim-breitner.de/" target="_blank">http://www.joachim-breitner.de/</a><br>
Jabber: <a href="mailto:nomeata@joachim-breitner.de">nomeata@joachim-breitner.de</a> • GPG-Key: 0xF0FBF51F<br>
Debian Developer: <a href="mailto:nomeata@debian.org">nomeata@debian.org</a><br>
</div></div><br>_______________________________________________<br>
Libraries mailing list<br>
<a href="mailto:Libraries@haskell.org">Libraries@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries</a><br>
<br></blockquote></div><br></div>