<div dir="ltr">+1 from me to add something along this line. <div><br></div><div>Right now I hack around it's lack in lens using a rather inefficient codepath.</div><div><br></div><div>-Edward</div></div><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Jan 19, 2016 at 11:55 AM, David Feuer <span dir="ltr"><<a href="mailto:david.feuer@gmail.com" target="_blank">david.feuer@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Indexed traversals seem to be pretty popular these days, and sequences<br>
should be able to support them efficiently. At present, the best<br>
options are<br>
<br>
1. Thread a counter through. This doesn't work well for weird things<br>
like lazy State.<br>
<br>
2. Use zipWith first to add indices, then traverse. This adds a<br>
smaller, but still asymptotic, penalty to the same sorts of unusual<br>
functors, and also adds constant-factor overhead to strict ones that<br>
the counter threading wouldn't.<br>
<br>
I propose the following, modified mechanically from mapWithIndex. It<br>
should be about as efficient as possible in all cases.<br>
<br>
traverseWithIndex :: Applicative f => (Int -> a -> f b) -> Seq a -> f (Seq b)<br>
traverseWithIndex f' (Seq xs') = Seq <$> traverseWithIndexTree (\s<br>
(Elem a) -> Elem <$> f' s a) 0 xs'<br>
 where<br>
  traverseWithIndexTree :: (Applicative f, Sized a) => (Int -> a -> f<br>
b) -> Int -> FingerTree a -> f (FingerTree b)<br>
  traverseWithIndexTree _ s Empty = s `seq` pure Empty<br>
  traverseWithIndexTree f s (Single xs) = Single <$> f s xs<br>
  traverseWithIndexTree f s (Deep n pr m sf) = sPspr `seq` sPsprm `seq`<br>
          Deep n <$><br>
               traverseWithIndexDigit f s pr <*><br>
               traverseWithIndexTree (traverseWithIndexNode f) sPspr m <*><br>
               traverseWithIndexDigit f sPsprm sf<br>
    where<br>
      sPspr = s + size pr<br>
      sPsprm = s + n - size sf<br>
<br>
  traverseWithIndexDigit :: (Applicative f, Sized a) => (Int -> a -> f<br>
b) -> Int -> Digit a -> f (Digit b)<br>
  traverseWithIndexDigit f s (One a) = One <$> f s a<br>
  traverseWithIndexDigit f s (Two a b) = sPsa `seq` Two <$> f s a <*> f sPsa b<br>
    where<br>
      sPsa = s + size a<br>
  traverseWithIndexDigit f s (Three a b c) = sPsa `seq` sPsab `seq`<br>
                                      Three <$> f s a <*> f sPsa b <*> f sPsab c<br>
    where<br>
      sPsa = s + size a<br>
      sPsab = sPsa + size b<br>
  traverseWithIndexDigit f s (Four a b c d) = sPsa `seq` sPsab `seq`<br>
sPsabc `seq`<br>
                          Four <$> f s a <*> f sPsa b <*> f sPsab c<br>
<*> f sPsabc d<br>
    where<br>
      sPsa = s + size a<br>
      sPsab = sPsa + size b<br>
      sPsabc = sPsab + size c<br>
<br>
  traverseWithIndexNode :: (Applicative f, Sized a) => (Int -> a -> f<br>
b) -> Int -> Node a -> f (Node b)<br>
  traverseWithIndexNode f s (Node2 ns a b) = sPsa `seq` Node2 ns <$> f<br>
s a <*> f sPsa b<br>
    where<br>
      sPsa = s + size a<br>
  traverseWithIndexNode f s (Node3 ns a b c) = sPsa `seq` sPsab `seq`<br>
                                     Node3 ns <$> f s a <*> f sPsa b<br>
<*> f sPsab c<br>
    where<br>
      sPsa = s + size a<br>
      sPsab = sPsa + size b<br>
</blockquote></div><br></div>