Search code examples
haskellindexingtraversalhaskell-lens

Why have both itraverse and itraversed functions in Haskell's lens library?

The Haskell library lens contains a type class TraversableWithIndex that defines both the functions itraverse and itraversed:

class
    (FunctorWithIndex i t, FoldableWithIndex i t, Traversable t)
    => TraversableWithIndex i t | t -> i where
  itraverse :: Applicative f => (i -> a -> f b) -> t a -> f (t b)
  itraversed :: IndexedTraversal i (t a) (t b) a b

IndexedTraversal expands like this:

type IndexedTraversal i s t a b =
  forall p f. (Indexable i p, Applicative f) => p a (f b) -> s -> f t

itraverse and itraversed seem very similar. Why are both needed?

From playing around with itraverse and itraversed, it appears that itraversed is the only one of the two that can be used with %@~ as an AnIndexedSetter.

Here are the types of %@~, AnIndexedSetter, and Indexed for completeness:

(%@~) :: AnIndexedSetter i s t a b -> (i -> a -> b) -> s -> t 

type AnIndexedSetter i s t a b =
  Indexed i a (Identity b) -> s -> Identity t 

newtype Indexed i a b = Indexed { runIndexed :: i -> a -> b }

Why does %@~ require AnIndexedSetter? Why does Indexed have to be used anyway?

Using Indexed seems like it would make composition more difficult, since it is not a normal function. What am I missing here?

Solution

  • Indexed optics aren't as simple as regular ones. Regular Traversal is simple:

    type Traversal s t a b = forall f. Applicative f => (a -> f b) -> s -> f t

    That is exactly the type of traverse with s = c a and t = c b, where c is a Traversable.

    You could imagine that IndexedTraversal i is something similar with (i -> a -> f b); but it isn't!

    type IndexedTraversal i s t a b =
    forall p f. (Indexable i p, Applicative f) => p a (f b) -> s -> f t

    The Indexable i p constraint is satisfied by (->) and Indexed, so:

    itraverse  :: Applicative f => (i -> a -> f b) -> s -> f t
itraversed :: Applicative f =>      (a -> f b) -> s -> f t  -- (->)
itraversed :: Applicativef  =>   Indexed i a b -> s -> f t

    where

    newtype Indexed i a b = Indexed { runIndexed :: i -> a -> b }

    Why both are needed? itraverse is way more easy to implement. Usually it's already there (e.g. traverseWithKey in containers).

    The operations require concrete instantiations of the optics (e.g. set requires ASetter). Shortly: it's easier for compiler to figure out stuff, as we don't use Rank2Types.

    Indexed i.e. separate newtype is needed so we can talk about a -> b and i -> a -> b as instances of Indexable; that let's us degrade indexed optics into regular ones:

    Prelude Control.Lens> over itraversed (+1) [1,2,3]
[2,3,4]

    and having p a (f b) -> q s (f t) (where p can be (->) or Indexable) let us compose indexed and regular optics:

    Prelude Control.Lens> over (itraversed . traversed)  (+1) [[1,2],[3]]
[[2,3],[4]]

    or

    Prelude Control.Lens> iover (itraversed . traversed) (,) [[1,2],[3]]
[[(0,1),(1,2)],[(0,3)]]