How does Lens.Internal.Indexed connect to keyed containers?

Question

A traversable may be labelled. To take this idea one step further, one may apply a function to any element of a traversable by its index.

import Control.Monad.State

updateAt :: forall a. Int -> (a -> a) -> [a] -> [a]
updateAt i f = flip evalState [0..] . traverse g
  where
    g :: a -> State [Int] a
    g x = do
        js <- get
        case js of
            [ ]      -> error ""
            (j: js') -> do
                put js'
                if j == i
                   then return (f x)
                   else return x

In Haskell, there is an attempt to generalize or otherwise sort out operations like this. First it was keys, then it grew up into lens. It is now a huge package. I am trying to make sense of it.

To this end, I am trying to do simple things first. One simple thing is what I started with — to label a traversable. Can it be done? Further, can it be done on a "low level"?

element seems to be doing the same as my example above, so I checked its definition. It led me to Indexable, then to this:

class ( Choice p, Corepresentable p, Comonad (Corep p)
      , Traversable (Corep p), Strong p, Representable p, Monad (Rep p)
      , MonadFix (Rep p), Distributive (Rep p), Costrong p, ArrowLoop p
      , ArrowApply p, ArrowChoice p, Closed p
      ) => Conjoined p

I admit this is a bit over my head. I like how "indexable" sounds — it must be useful. But it also seems to be the hardest piece of Haskell ever written. I understand that Conjoined is an advanced kind of a profunctor, so basically... a function? I am not sure what it might be, and how this all connects to keyed containers.

Is it applicable to my problem? What is it for? How can I make sense of it?

Answer 1

Indexable i p really just means "p is either (->) or Indexed i (Indexed i a b = i -> a -> b)". The lens package is built on a tower of very abstract classes that makes everything very general. Specifically, instead of working with functions, it tries to work with general profunctors, but trying to deal with indices basically causes the whole thing to collapse down (very noisily, as you've seen) to just "the profunctor is either (->) or Indexed i".

In any case, you don't care about Indexable. The "index" you're talking about is the argument to element. The "index" in IndexedTraversable is a "result", each element returned by an IndexedTraversable also has its index associated with it. Here, it just returns the argument you passed in again, in case something else wants to get it. You don't. To recover updateAt, simply pass element's return value to over, specializing p to (->) and throwing away the duplicated index:

updateAt :: Traversable t => Int -> (a -> a) -> t a -> t a
updateAt = over . element
-- updateAt i f = over (element i) f
-- "over element i do f"

I'd say over is pretty "low-level"

-- basically
over :: ((a -> Identity b) -> (s -> Identity t)) -> (a -> b) -> (s -> t)
over setter f = runIdentity . setter (Identity . f)
-- I think even over = coerce would be valid
-- meaning it's actually just an identity function
-- and that updateAt = element (but with the type changed)

In general, I suppose the "portal" to "operations on Traversable with indices" is traversed, which basically "is" traverse (when you specialize its p to (->)). elements = elementsOf traverse = elementsOf traversed and element = elementOf traverse = elementsOf traversed just filter for specific indices.