search

reinerp / indexed

Haskell98 indexed functors, monads, comonads
BSD 3-Clause "New" or "Revised" License
25 stars 3 forks source link

Add indexed Traversable #3

Open treeowl opened 8 years ago

treeowl commented 8 years ago

There are notions of mapping, folding, and traversing available for type-aligned sequences:

class TAMappable t where
  tmap :: (forall x y . c x y -> d x y) -> t c p q -> t d p q

class TAFoldable f where
  tfoldMap :: Category d => (forall x y . c x y -> d x y) -> f c p q -> d p q

Either of the following (I'm not sure which is better):

class (TAMappable t, TAFoldable t) => TATraversable t where
  ttraverse :: IxApplicative m => (forall x y . c x y -> m y x (d x y)) -> t c p q -> m q p (t d p q)

class (TAMappable t, TAFoldable t) => TATraversable t where
  ttraverse :: IxApplicative m => (forall x y . c x y -> m x y (d x y)) -> t c p q -> m p q (t d p q)

The two options correspond to the traversals in each direction. If I'm not mistaken, they're related by IxBackwards (#2).

treeowl commented 8 years ago

Indeed, the following seems to work (modulo the lousy names):

class (TAMappable t, TAFoldable t) => TATraversable t where
  ttraverse :: IxApplicative m => (forall x y . c x y -> m x y (d x y)) -> t c p q -> m p q (t d p q)
  ttraverse f = ixForwards . ttraverseOp (IxBackwards . f)
  ttraverseOp :: IxApplicative m => (forall x y . c x y -> m y x (d x y)) -> t c p q -> m q p (t d p q)
  ttraverseOp f = ixForwards . ttraverse (IxBackwards . f)
  {-# MINIMAL ttraverse | ttraverseOp #-}