+1 for adding `traverseWithIndex`, I did look for that one more than once :) I don't have strong opinions for the other variations of the functions. On 19 January 2016 at 17:55, David Feuer wrote:

Indexed traversals seem to be pretty popular these days, and sequences should be able to support them efficiently. At present, the best options are

1. Thread a counter through. This doesn't work well for weird things like lazy State.

2. Use zipWith first to add indices, then traverse. This adds a smaller, but still asymptotic, penalty to the same sorts of unusual functors, and also adds constant-factor overhead to strict ones that the counter threading wouldn't.

I propose the following, modified mechanically from mapWithIndex. It should be about as efficient as possible in all cases.

traverseWithIndex :: Applicative f => (Int -> a -> f b) -> Seq a -> f (Seq b) traverseWithIndex f' (Seq xs') = Seq <$> traverseWithIndexTree (\s (Elem a) -> Elem <$> f' s a) 0 xs' where traverseWithIndexTree :: (Applicative f, Sized a) => (Int -> a -> f b) -> Int -> FingerTree a -> f (FingerTree b) traverseWithIndexTree _ s Empty = s `seq` pure Empty traverseWithIndexTree f s (Single xs) = Single <$> f s xs traverseWithIndexTree f s (Deep n pr m sf) = sPspr `seq` sPsprm `seq` Deep n <$> traverseWithIndexDigit f s pr <*> traverseWithIndexTree (traverseWithIndexNode f) sPspr m <*> traverseWithIndexDigit f sPsprm sf where sPspr = s + size pr sPsprm = s + n - size sf

traverseWithIndexDigit :: (Applicative f, Sized a) => (Int -> a -> f b) -> Int -> Digit a -> f (Digit b) traverseWithIndexDigit f s (One a) = One <$> f s a traverseWithIndexDigit f s (Two a b) = sPsa `seq` Two <$> f s a <*> f sPsa b where sPsa = s + size a traverseWithIndexDigit f s (Three a b c) = sPsa `seq` sPsab `seq` Three <$> f s a <*> f sPsa b <*> f sPsab c where sPsa = s + size a sPsab = sPsa + size b traverseWithIndexDigit f s (Four a b c d) = sPsa `seq` sPsab `seq` sPsabc `seq` Four <$> f s a <*> f sPsa b <*> f sPsab c <*> f sPsabc d where sPsa = s + size a sPsab = sPsa + size b sPsabc = sPsab + size c

traverseWithIndexNode :: (Applicative f, Sized a) => (Int -> a -> f b) -> Int -> Node a -> f (Node b) traverseWithIndexNode f s (Node2 ns a b) = sPsa `seq` Node2 ns <$> f s a <*> f sPsa b where sPsa = s + size a traverseWithIndexNode f s (Node3 ns a b c) = sPsa `seq` sPsab `seq` Node3 ns <$> f s a <*> f sPsa b <*> f sPsab c where sPsa = s + size a sPsab = sPsa + size b _______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

-- *Λ\ois* http://twitter.com/aloiscochard http://github.com/aloiscochard

+1 from me to add something along this line. Right now I hack around it's lack in lens using a rather inefficient codepath. -Edward On Tue, Jan 19, 2016 at 11:55 AM, David Feuer wrote:

Indexed traversals seem to be pretty popular these days, and sequences should be able to support them efficiently. At present, the best options are

1. Thread a counter through. This doesn't work well for weird things like lazy State.

2. Use zipWith first to add indices, then traverse. This adds a smaller, but still asymptotic, penalty to the same sorts of unusual functors, and also adds constant-factor overhead to strict ones that the counter threading wouldn't.

I propose the following, modified mechanically from mapWithIndex. It should be about as efficient as possible in all cases.

traverseWithIndex :: Applicative f => (Int -> a -> f b) -> Seq a -> f (Seq b) traverseWithIndex f' (Seq xs') = Seq <$> traverseWithIndexTree (\s (Elem a) -> Elem <$> f' s a) 0 xs' where traverseWithIndexTree :: (Applicative f, Sized a) => (Int -> a -> f b) -> Int -> FingerTree a -> f (FingerTree b) traverseWithIndexTree _ s Empty = s `seq` pure Empty traverseWithIndexTree f s (Single xs) = Single <$> f s xs traverseWithIndexTree f s (Deep n pr m sf) = sPspr `seq` sPsprm `seq` Deep n <$> traverseWithIndexDigit f s pr <*> traverseWithIndexTree (traverseWithIndexNode f) sPspr m <*> traverseWithIndexDigit f sPsprm sf where sPspr = s + size pr sPsprm = s + n - size sf

traverseWithIndexDigit :: (Applicative f, Sized a) => (Int -> a -> f b) -> Int -> Digit a -> f (Digit b) traverseWithIndexDigit f s (One a) = One <$> f s a traverseWithIndexDigit f s (Two a b) = sPsa `seq` Two <$> f s a <*> f sPsa b where sPsa = s + size a traverseWithIndexDigit f s (Three a b c) = sPsa `seq` sPsab `seq` Three <$> f s a <*> f sPsa b <*> f sPsab c where sPsa = s + size a sPsab = sPsa + size b traverseWithIndexDigit f s (Four a b c d) = sPsa `seq` sPsab `seq` sPsabc `seq` Four <$> f s a <*> f sPsa b <*> f sPsab c <*> f sPsabc d where sPsa = s + size a sPsab = sPsa + size b sPsabc = sPsab + size c

traverseWithIndexNode :: (Applicative f, Sized a) => (Int -> a -> f b) -> Int -> Node a -> f (Node b) traverseWithIndexNode f s (Node2 ns a b) = sPsa `seq` Node2 ns <$> f s a <*> f sPsa b where sPsa = s + size a traverseWithIndexNode f s (Node3 ns a b c) = sPsa `seq` sPsab `seq` Node3 ns <$> f s a <*> f sPsa b <*> f sPsab c where sPsa = s + size a sPsab = sPsa + size b