Use Polymorphism Instead of Product

[BebeSparkelSparkel]

I wonder how useful the product of monads/applicatives really is. In our paper on bidirectional programming we mainly chose it for simplicity of exposition, but in practice I'd much prefer an approach based on polymorphism. Rather than constructing a biparser as a pair of parser and printer, we can write it as a polymorphic function parameterized by biparser primitives and instantiate it separately to parsers and printers (and possibly more).

Originally posted by @Lysxia in https://github.com/Lysxia/generic-data/issues/68#issuecomment-2141508818

[BebeSparkelSparkel]

@Lysxia Could you elaborate a bit more?

Also, could you define what you think newtype Biparser context s m n u v = Biparser' {unBiparser :: FwdBwd m n u v} code link should be changed to?

[Lysxia]

You would not have a Biparser type, but a class.

class (Profunctor p, forall u. Monad (p u)) => Biparser p where
  char :: p Char Char
  -- other biparser primitives

newtype Parser u v = Parser (String -> Maybe (v, String))
newtype Printer u v = Printer (u -> Maybe (v, String))

instance Biparser Parser where ...
instance Biparser Printer where ...

Then a biparser is a polymorphic value

twoChars :: Biparser p => p String String
twoChars = do
  x <- head `lmap` char
  y <- (head . tail) `lmap` char
  pure [x, y]

[BebeSparkelSparkel]

The class is a good idea. I think I'll also create transformers so different monads can be used.

newtype Fwd m u v = Fwd {unFwd :: m v}
instance Biparser (Fwd m) where ...

newtype Bwd m u v = Bwd {unBwd :: u -> m v}
instance Biparser (Fwd m) where ...

[BebeSparkelSparkel]

@Lysxia Instead of having a Biparser class what do you think of having capability constraints? Like:

char ::
  ( IsSequence text
  , UpdateStateWithElement s
  , MonadState s m
  , MonadFail m
  , text ~ TextType s
  , char ~ Element text
  ) => p char char

This allows for scaling the monad's capabilities for which combinators are used.

[Lysxia]

I think if you just want to be able to allow different combinations of primitives, having individual classes for those primitives is both simple and good enough.

Exposing MonadState presumes you can get the parser state and put it back, which isn't possible if your parser state is external (e.g. using IORef or streaming from a file handle).

[BebeSparkelSparkel]

Maybe this is a bad idea, but I was thinking of using lazy IO for those cases.

[BebeSparkelSparkel]

After thinking about it you are definitely right about the primitives

[BebeSparkelSparkel]

@Lysxia In some cases there is divergence between forwards and backwards. Is there a way to allow for divergence without having to define a placeholder monad with the constraint instances?

What I have come up with is this but it seems unwieldy since all the constraint instances will have to be defined for Proxy.

class Divergence m f b | m -> f b where
  -- | First argument is run forward and the second is run backwards
  diverge :: f a -> b a -> m a

instance Divergence (Fwd u) (Fwd u) Proxy where diverge = const
instance Divergence (Bwd u) Proxy (Bwd u) where diverge = flip const