Invertible State monad (and parsers)

Question

Good day, ladies and gentlemen!

I'm constantly writing parsers and codecs. Implementing both parsers and printers seems to be massive code duplication. I wonder whether it is possible to invert a stateful computation, given it is isomorphic by nature.

It is possible to invert pure function composition (Control.Lens.Iso did that by defining a composition operator over isomorphisms). As it can be observed,

Iso bc cb . Iso ab ba = Iso (bc . ab) (ba . cb) -- from Lenses talk
invert (f . g) = (invert g) . (invert f)        -- pseudo-code

In other words, to invert a function composition one should compose inverted functions in the opposite order. So, given all primitive isomorphic pairs are defined, one can compose them to get more complicated pairs with no code duplication. Here is an example of pure bidirectional computation (Control.Lens is used, the explanatory video can help you to get the general idea of Lenses, Folds and Traversals):

import Control.Lens

tick :: Num a => Iso' a a
tick = iso (+1) (subtract 1)   -- define an isomorphic pair

double :: Num a => Iso' a a
double = iso (+2) (subtract 2) -- and another one

threeTick :: Num a => Iso' a a
-- These are composed via simple function composition!
threeTick = double . tick

main :: IO ()
main = do
        print $ (4 :: Int)^.tick           -- => 5
        print $ (4 :: Int)^.from tick      -- => 3

        print $ (4 :: Int)^.threeTick      -- => 7, Composable
        print $ (4 :: Int)^.from threeTick -- => 1, YEAH

As you can see, I didn't need to supply the inverted version of threeTick; it is obtained by backward composition automatically!

Now, let's consider a simple parser.

data FOO = FOO Int Int deriving Show

parseFoo :: Parser FOO
parseFoo = FOO <$> decimal <* char ' '
               <*> decimal

parseFoo' :: Parser FOO
parseFoo' = do
    first <- decimal
    void $ char ' '
    second <- decimal
    return $ FOO first second


printFoo :: FOO -> BS.ByteString
printFoo (FOO a b) = BS.pack(show a) <>
                     BS.pack(" ")    <>
                     BS.pack(show b)


main :: IO ()
main = do
        print $ parseOnly parseFoo "10 11"  -- => Right (FOO 10 11)
        print $ parseOnly parseFoo' "10 11" -- => Right (FOO 10 11)

        print . printFoo $ FOO 10 11        -- => "10 11"
        print . parseOnly parseFoo . printFoo $ FOO 10 11 -- id

You can see that both versions of parseFoo are fairly declarative (thanks to parser combinators). Note the similarity between parseFoo and printFoo. Can I define isomorphisms over primitive parsers (decimal and char) and then just derive the printer (printFoo :: FOO -> String) automatically? Ideally, parser combinators will work as well.

I tried to redefine a monadic >>= operator in order to provide inverted semantics, but I've failed to do so. I feel that one could define inverted Kleisli composition operator (monadic function composition) similarly to composition inversion, but can one use it with ordinary monads?

f :: a -> m b,     inverse f :: b -> m a
g :: b -> m c,     inverse g :: c -> m b
inverse (f >=> g) = (inverse f) <=< (inverse g)

Why inverse f is of type b -> m a and not m b -> a? The answer is: monadic side effect is an attribute of an arrow, not that of a data type b. The state monad dualization is further discussed in the great Expert to Expert video.

If the solution does exist, could you please supply a working example of printFoo derivation? By the way, here is an interesting paper that could help us find the solution.

Answer 1

You may be interested in digging in further into the lens package for the concept of a Prism.

A Prism can be used as a 'smart constructor' to build something (e.g. a pretty printed string) unconditionally, and match on it (e.g. parse).

You'd have to ignore the laws or treat the laws as holding only up to a quotient though, as the string you get out of pretty printing is very likely not exactly the string you parsed.