<div dir="ltr">+1 for adding `<span style="font-size:12.8px">traverseWithIndex`, I did look for that one more than once :)</span><div><span style="font-size:12.8px"><br></span></div><div><span style="font-size:12.8px">I don't have strong opinions for the other variations of the functions.</span></div></div><div class="gmail_extra"><br><div class="gmail_quote">On 19 January 2016 at 17:55, 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>
_______________________________________________<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><br><br clear="all"><div><br></div>-- <br><div class="gmail_signature"><div dir="ltr"><div><b>Λ\ois</b></div><div><div><a href="http://twitter.com/aloiscochard" target="_blank">http://twitter.com/aloiscochard</a></div><div><a href="http://github.com/aloiscochard" target="_blank">http://github.com/aloiscochard</a></div></div></div></div>
</div>