Re: [Haskell-cafe] traversal with an arrow
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? E. Kmett's profunctor implementation wanderA, linked to from the end of the discussion, seems to be missing from the current Data.Profunctor.Traversing module. Olaf [*] Structurally, Traversal a r b ~ Free (Const a :*: ((->) r)) b and also their Applicative instances seem to match on first glance. In particular, Traversal a () b ~ ([a],b) whence traversal :: Traversable t => t a -> Traversal a b (t b) can be specialized to traversal :: Traversable t => t a -> ([a],t ())
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
participants (2)
-
Olaf Klinke -
Tom Ellis