Control.Lens: isomorphism of transitions to toListOf and more

Question

I watched Simon Payton Jones story about Control.Lens, and he showed that Lens and LensR, as defined here, are isomorphic:

type Lens stab = forall f. Functor f => (a -> fb) -> s -> ft data LensR stab = LensR { viewR :: s -> a, setR :: b -> s -> t } 

I am trying to do the same with Traversal:

 type Traversal stab = forall f. Applicative f => (a -> fb) -> s -> ft data TraversalR stab = TraversalR { toListOfR :: s -> [a], overR :: (a -> b) -> s -> t } newtype CL ab = CL { getCL :: [a] } -- ConstantList instance Functor (CL a) where fmap _ (CL xs) = CL xs instance Applicative (CL a) where pure _ = CL [] (CL xs) <*> (CL ys) = CL (xs ++ ys) travToTravR :: Traversal stab -> TraversalR stab travToTravR tr = TraversalR { toListOfR = getCL . tr (CL . pure), overR = \f -> runIdentity . tr (Identity . f) } 

But I am stuck with travRToTrav. This is the best I can think of:

 travRToTrav :: TraversalR stab -> Traversal stab travRToTrav trR a2fb s = (\bs-> overR trR magic s) <$> f_bs where as = toListOfR trR s f_bs = sequenceA . map a2fb $ as magic = undefined 

Here is magic :: a → b, but I cannot make a general function (a → b). Instead, I can cheat by performing a partial function: I know that a function should return for any value of type a that is in the intersection. So I could create a list of associations from as and bs, and then a partial function from that.

It works? If yes, please tell me the best way!

Or did I choose the wrong shape for TraversableR, and there really is no isomorphism?

Thanks for any advice.

---

EDIT:

So thanks András Kovács Now I think TraversalR should look like this:

 data TraversalR stab = TraversalR { toListOfR :: s -> [a], setListR :: [b] -> s -> t } 

Then travRToTrav is very similar to lensRToLens:

 travRToTrav :: TraversalR stab -> Traversal stab travRToTrav trR a2fb s = (`setL` s) <$> f_bs where as = toListOfR trR s f_bs = sequenceA . map a2fb $ as setL = setListR trR 

But then, how to define setListR in travToTravR? Basically, how do indexed crawls work?

Answer 1

After a discussion with Andras Kovacs, I found a good simple answer: we need a state monad, which is an applied functor. Here is the complete isomorphism:

 type Traversal stab = forall f. Applicative f => (a -> fb) -> (s -> ft) data TraversalR stab = TraversalR { toListOfR :: s -> [a], setListR :: [b] -> s -> t } newtype CL ab = CL { getCL :: [a] } -- ConstantList instance Functor (CL a) where fmap _ (CL xs) = CL xs instance Applicative (CL a) where pure _ = CL [] (CL xs) <*> (CL ys) = CL (xs ++ ys) collectBs :: State [b] b collectBs = state $ \xs -> case xs of [] -> error "Too few bs" (y:ys) -> (y,ys) travToTravR :: Traversal stab -> TraversalR stab travToTravR tr = TraversalR { toListOfR = getCL . tr (CL . pure), setListR = \bs s -> evalState (tr (const collectBs) s) bs } travRToTrav :: TraversalR stab -> Traversal stab travRToTrav trR a2fb s = (`setL` s) <$> f_bs where as = toListOfR trR s f_bs = sequenceA . map a2fb $ as setL = setListR trR