Ideas regarding Alternative instance for 'profunctor-monad'

[chshersh]

Hello! I'm using this approach to write bidirectional parser and pretty-printer for TOML:

• https://github.com/kowainik/tomland

Now I want to be able to encode and decode sum types. And Alternative type class looks like a good pattern for such things. But, unfortunately, I can't figure out clean way to do it.

• Support sum types in bidirectional conversion kowainik/tomland#54

Maybe you could give some ideas and tips regarding how to deal with sum types in this approach? I can introduce dirty hacks and workarounds without problems, but it would be great to have some idiomatic and clean solution!

In examples for codec library I see only record types, no sum types, so I'm a little bit confused by this problem 🤔

[Lysxia]

Indeed, sum types are tricky. I don't have very satisfactory answers, but here are my attempts so far.

Keeping close to Alternative

We can build something around the signature (<|>) :: p x a -> p x a -> p x a, which we know how to implement for parsers. But for printers we need the ability to fail depending on the input x. One way here is to generalize Profunctor to lift partial functions:

dimap' :: (x -> Maybe y) -> (a -> Maybe b) -> p y a -> p x b

So a parser such as

onOff = (string "ON" $> On) <|> (string "OFF" $> Off)

would now look like:

onOff = lmap' isOn (string "ON" $> On) <|> lmap' isOff (string "OFF" $> Off)

string :: String -> BiParser () ()
isOn, isOff  :: OnOff -> Maybe ()

Of course, on top of the repetition isOn/On and isOff/Off, the big drawback is the fact that there is little protection against mistakes like swapping or forgetting them.

A different combinator

Somehow, it may seem that it should be up to the choice operator (<|>) to pick the right branch depending on the input, suggesting a different operator:

(<||>) :: p x a -> p y b -> p (Either x y) (Either a b)

However, when defining maps to and from Either (necessary to use (<||>)), we encounter again the unavoidable problem of encoding bijections correctly, one way or another.

As a small digression, we can define (<||>) in terms of (<|>) and thus reuse Alternative, at the cost of having the printer type allow failures (both because of empty and because failure is a fundamental part of the meaning of (<|>)).

a <||> b = dimap' fromLeft' Left a <|> dimap' fromRight' Right b
-- where fromLeft' and fromRight' are the Maybe versions of fromLeft and fromRight

Leveraging generics

I'm now thinking that the above solutions may be trying to be too general. In practice, the structure of the types are reflected in the parsers. We can certainly exploit that with generics, to derive a specialized version of (<||>) for each ADT, taking care of pattern-matching/constructing, and letting us just write each branch individually.

In the above onOff example, one side returns On, one side returns Off, that should be enough to derive the right choice to make for the printer. Some mangling of the original parser will be unavoidable, but I think we can remain very close to it visually.

[chshersh]

@Lysxia Probably prisms could help here. It would be great to have first-class patterns in Haskell, but we are not there yet, though there's some library:

• https://hackage.haskell.org/package/first-class-patterns

What I think is that instead of specifying constructor and deconstructor manually you can just specify prism, something like that (not sure it will work eventually, didn't write prototype code):

a <||> b = pmap _Left a <|> pmap _Right b

Prism can be both constructor and deconstructor. I just see some usage examples here:

• https://hackage.haskell.org/package/lens-4.16.1/docs/Control-Lens-Fold.html#v:-94--63-
• https://hackage.haskell.org/package/lens-4.16.1/docs/Control-Lens-Review.html#v:review

If BiParser is something like that:

data Bi r w c a = Bi
    { biRead :: r a
    , biWrite :: c -> w a
    }

type BiParser c a = Bi SomeEnvMonad SomeWriteMonad c a

and if SomeEnvMonad is something like ExceptT MyCustomError (Reader SomeEnv a) (because it's usually convenient to report errors), you can write Alternative instance for BiParser by handling ExceptT exception. And empty is just some TrivialError as it usually happens with parser combinators libraries. And with this we probably don't even need <||> operator, <|> should be okay.

And if you have BiParser (Maybe a) (Maybe a) you probably can just do nothing on Nothing. Thus such instance should be okay:

type Bi' a = BiParser a a  -- some newtype here probably

instance Alternative Bi where
    empty = Bi (throwError TrivialError) pure
    bi1 <|> bi2 = Bi (biRead bi1 `catchError` \_ -> biRead bi2) (biWrite bi1 >> biWrite bi2)

[Lysxia]

Indeed, some form of first class pattern supported by the compiler would help here! Thanks for the links, I didn't know about the first-class-patterns library, it's so nice!

I'm not sure about implementing empty for the biWrite component as pure, since we lose the law empty >> m = empty.

[chshersh]

@Lysxia Looks like empty >> m = empty law is only for MonadPlus. Alternative doesn't need to satisfy this law (according to this wiki book):

• https://en.wikibooks.org/wiki/Haskell/Alternative_and_MonadPlus#Alternative_and_MonadPlus_laws

[Lysxia]

I think every lawful Monad that is also Alternative satisfies the left-zero law for free by parametricity.

It would be less clear if we only have an Applicative, but in the context of bidirectional programming it seems desirable for both the biRead and biWrite to follow the same laws to help guarantee round-tripping.

[chshersh]

@Lysxia I have the following definition. I wonder, how much sense does it make and what can be improved?

data Bi r w c a = Bi
    { biRead :: r a
    , biWrite :: c -> w a
    }

instance (MonadError e r, Monoid e, Alternative w) => Alternative (Bi r w c) where
    empty :: Bi r w c a
    empty = Bi
        { biRead  = throwError mempty
        , biWrite = \_ -> empty
        }

    (<|>) :: Bi r w c a -> Bi r w c a -> Bi r w c a
    bi1 <|> bi2 = Bi
        { biRead  = biRead bi1 `catchError` \_ -> biRead bi2
        , biWrite = \c -> biWrite bi1 c <|> biWrite bi2 c
        }

Main reason for MonadError constraint is because I really want ExcepT for decoding to give human-readable error messages. I wonder how much sense in the concept of monoidal errors. I have error type like this:

data DecodeException
    = TrivialError
    | KeyNotFound Key
    | TableNotFound Key
    | TypeMismatch Key Text TValue
    | ParseError ParseException
    deriving (Eq, Show)

instance Semigroup DecodeException where
    TrivialError <> e = e
    e <> TrivialError = e
    e <> _ = e

instance Monoid DecodeException where
    mempty = TrivialError
    mappend = (<>)

[Lysxia]

The MonadError constraint on r can be replaced with Alternative. This is more general because r can still implement Alternative using MonadError.

[chshersh]

Turned out there already exist such Alternative instance for ExceptT that I want:

• https://hackage.haskell.org/package/transformers-0.5.5.0/docs/Control-Monad-Trans-Except.html#t:ExceptT

[chshersh]

@Lysxia Btw, I've finished tomland recently. You can read the blog post about the implementation here:

• https://kowainik.github.io/posts/2019-01-14-tomland

Regarding support for sum types: this is how I did it currently

• Alternative instance
• Usage example

Current approach is not powerful and flexible enough, but I'm still working on making it better!