[Haskell-cafe] traversal with an arrow

[Tom Ellis]

On Sun, Jun 19, 2022 at 01:28:14AM +0200, Olaf Klinke wrote:
> > On Fri, Jun 17, 2022 at 05:01:55PM +0200, Olaf Klinke wrote:
> > > Is there prior art to the following generalisation? 
> > 
> > >     traverseArrow :: Traversable t => a x y -> a (t x) (t y) 
> > 
> > Perhaps you are looking for this:
> > 
> >     https://github.com/tomjaguarpaw/Arrows2/issues/3#issuecomment-561973678
> 
> Thanks Tom, can you explain what's behind this implementation, for
> those unfamiliar with arrow syntax? I guess [*] that the Traversal type
> used is a manifestation of the fact that one can transform any
> traversable structure (t a) into ([a],t ()) and sort the contents of
> the linked list back into their original places? This way, arbitrary
> traversals can be reduced to traversals over linked lists. Then the
> ArrowChoice is needed to pattern match on the list constructors? 

Yes, that's about right, or perhaps more precisely:

"A 'Traversal a r b' is a structure that you can extract 'a's from, at
the same time replacing them with 'r's.  The final result is a 'b'."

So, for example, if 'Traversable t' then 't a' is such a structure
(where b ~ t r).  That's why there's a function

    traversal :: Traversable t => t a -> Traversal a r (t r)

Hope that helps,

Tom