Open chshersh opened 6 years ago
Indeed, sum types are tricky. I don't have very satisfactory answers, but here are my attempts so far.
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.
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
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.
@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:
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:
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)
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
.
@Lysxia Looks like empty >> m = empty
law is only for MonadPlus
. Alternative
doesn't need to satisfy this law (according to this wiki book):
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.
@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 = (<>)
The MonadError
constraint on r
can be replaced with Alternative
. This is more general because r
can still implement Alternative
using MonadError
.
Turned out there already exist such Alternative
instance for ExceptT
that I want:
@Lysxia Btw, I've finished tomland
recently. You can read the blog post about the implementation here:
Regarding support for sum types: this is how I did it currently
Current approach is not powerful and flexible enough, but I'm still working on making it better!
Hello! I'm using this approach to write bidirectional parser and pretty-printer for TOML:
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.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 🤔