<p dir="ltr">Minor correction to avoid confusing anyone. I was wrong about lifting more than lowering for ix. But if you were implementing something that traverses multiple (or even all) elements, that could be significant, I think.</p>
<div class="gmail_quote">On Apr 28, 2016 6:17 PM, "Edward Kmett" <<a href="mailto:ekmett@gmail.com">ekmett@gmail.com</a>> wrote:<br type="attribution"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Good catch. We might see if Coyoneda works better than Yoneda for<br>
`fusing` in lens in practice as well.<br>
<br>
-Edward<br>
<br>
On Thu, Apr 28, 2016 at 2:48 PM, David Feuer <<a href="mailto:david.feuer@gmail.com">david.feuer@gmail.com</a>> wrote:<br>
> AHA! I was wrong! There *is* (some) hope! I should've realized this<br>
> earlier. The trick is to use Coyoneda instead of Yoneda. Coyoneda is<br>
> effectively lazier than Yoneda, so nodes can become available as soon<br>
> as they're passed. I suspect it may also be helpful that while<br>
> liftYoneda is pricier than lowerYoneda for non-trivial functors, the<br>
> opposite holds for Coyoneda. Since adjustA does a lot more lifting<br>
> than lowering, Coyoneda seems like a better fit. A thoroughly<br>
> straightforward Coyoneda-based implementation offers *decent*<br>
> (although not wonderful) viewing performance. But as soon as it's<br>
> passed something that reads *and* modifies, it does a little better<br>
> than the fake version.<br>
><br>
> On Wed, Apr 27, 2016 at 10:15 PM, David Feuer <<a href="mailto:david.feuer@gmail.com">david.feuer@gmail.com</a>> wrote:<br>
>> Using Yoneda greatly improved performance for Identity, and raised the<br>
>> performance for [] a little above that of the "fake" version lens<br>
>> currently uses. But the performance for simply viewing an element is<br>
>> awful (it takes about twice as long as `index`), and I'm beginning to<br>
>> doubt there's any solution that will get the (small) speed-up in some<br>
>> cases without getting a (large) slow-down elsewhere. Oh well.<br>
>><br>
>> On Wed, Apr 27, 2016 at 6:39 PM, Edward Kmett <<a href="mailto:ekmett@gmail.com">ekmett@gmail.com</a>> wrote:<br>
>>> That transformation is effectively what 'fusing' does. It CPSes (er..<br>
>>> Yonedas, actually) the functor `f` as forall r. (a -> r) -> f r, and<br>
>>> accumulates the changes by composing in more functions, so that it can<br>
>>> all be discharged with one fmap. You should be able to achieve the<br>
>>> same result by hand with a manual worker/wrapper transformation.<br>
>>><br>
>>> -Edward<br>
>>><br>
>>> On Thu, Apr 28, 2016 at 8:20 AM, David Feuer <<a href="mailto:david.feuer@gmail.com">david.feuer@gmail.com</a>> wrote:<br>
>>>> I was thinking switching to CPS might help, passing the context down on the<br>
>>>> way to the leaf, so the tree is built "inside" the functor. This is pretty<br>
>>>> easy for nodes and digits, but I'm struggling with the polymorphic recursion<br>
>>>> in the spine right now. I think I'll probably figure it out eventually.<br>
>>>><br>
>>>> On Apr 27, 2016 6:12 PM, "Edward Kmett" <<a href="mailto:ekmett@gmail.com">ekmett@gmail.com</a>> wrote:<br>
>>>>><br>
>>>>> For cases were the Functor winds up particularly complicated or won't<br>
>>>>> be known at compile time so the inlining can't help, it turns out you<br>
>>>>> can usually work around this with the 'fusing' combinator from the<br>
>>>>> lens library. This works around the repeated stacks of `fmap` that get<br>
>>>>> built up otherwise, transforming everything into one gigantic fmap all<br>
>>>>> in one go.<br>
>>>>><br>
>>>>> There is a similar `confusing` combinator for working with traversals.<br>
>>>>> The implementation lives up to the name.<br>
>>>>><br>
>>>>> -Edward<br>
>>>>><br>
>>>>> On Wed, Apr 27, 2016 at 5:19 PM,  <<a href="mailto:rf@rufflewind.com">rf@rufflewind.com</a>> wrote:<br>
>>>>> > On Tue, Apr 26, 2016, at 15:03, David Feuer wrote:<br>
>>>>> >> Way back when, Shachaf Ben-Kiki suggested an efficient implementation<br>
>>>>> >> of `at` for Data.Map in<br>
>>>>> >> <a href="https://mail.haskell.org/pipermail/libraries/2013-May/019761.html" rel="noreferrer" target="_blank">https://mail.haskell.org/pipermail/libraries/2013-May/019761.html</a> but<br>
>>>>> >> that was never approved for inclusion.<br>
>>>>> ><br>
>>>>> > Funny thing, I just tried doing that not to long ago with `at`:<br>
>>>>> ><br>
>>>>> > <a href="https://github.com/haskell/containers/pull/192" rel="noreferrer" target="_blank">https://github.com/haskell/containers/pull/192</a><br>
>>>>> ><br>
>>>>> > In the end, the results were mixed.  It was a small optimization in some<br>
>>>>> > situations, and a moderate pessimization in others (esp. when the<br>
>>>>> > Functor becomes too complex for GHC to optimize).<br>
>>>>> ><br>
>>>>> > --<br>
>>>>> > RF<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" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries</a><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" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries</a><br>
</blockquote></div>