Монада Invertible State (и парсеры)

Добрый день, дамы и господа!

Я постоянно пишу парсеры и кодеки. Реализация парсеров и принтеров кажется массовым дублированием кода. Интересно, можно ли инвертировать вычисление с сохранением состояния, учитывая, что оно изоморфно по своей природе.

Можно инвертировать чистую композицию функций (Control.Lens.Iso сделал это, определив оператор композиции над изоморфизмами). Как можно заметить,

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

Другими словами, чтобы инвертировать композицию функций, нужно составить инвертированные функции в обратном порядке. Таким образом, если определены все примитивные изоморфные пары, можно составить из них более сложные пары без дублирования кода. Вот пример чисто двунаправленного вычисления (используется Control.Lens, пояснительное видео может помочь чтобы получить общее представление о линзах, складках и пересечениях):

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

Как видите, мне не нужно было указывать инвертированную версию threeTick; получается обратной композицией автоматически!

Теперь давайте рассмотрим простой парсер.

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

Вы можете видеть, что обе версии parseFoo довольно декларативны (благодаря комбинаторам парсеров). Обратите внимание на сходство между parseFoo и printFoo. Могу ли я определить изоморфизмы над примитивными синтаксическими анализаторами (decimal и char), а затем просто автоматически вывести принтер (printFoo :: FOO -> String)? В идеале, комбинаторы парсеров также будут работать.

Я попытался переопределить монадический оператор >>=, чтобы обеспечить инвертированную семантику, но мне это не удалось. Я чувствую, что можно было бы определить инвертированный оператор композиции Клейсли (композицию монадической функции) аналогично инверсии композиции, но можно ли использовать его с обычными монадами?

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)

Почему inverse f имеет тип b -> m a, а не m b -> a? Ответ таков: монадический побочный эффект — это атрибут стрелки, а не тип данных b. Дуализация монады состояний далее обсуждается в великой книге «От эксперта к эксперту» видео.

Если решение действительно существует, не могли бы вы привести рабочий пример вывода printFoo? Кстати, вот интересная статья, которая может нам помочь найти решение.