可逆状态monad(和解析器)

Question

女士们,先生们,美好的一天!

我经常编写解析器和编解码器.实现解析器和打印机似乎是大量的代码重复.我想知道是否可以反转有状态计算,因为它本质上是同构的.

可以反转纯函数组合(Control.Lens.也可以通过在同构上定义组合运算符来实现).可以观察到,

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自动派生打印机()吗？理想情况下,解析器组合器也可以工作.

我试图重新定义一个monadic >>=运算符以提供反向语义,但我没有这样做.我觉得可以用组合反演来定义倒置Kleisli合成算子(monadic function composition),但是可以将它与普通monad一起使用吗？

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？答案是:monadic副作用是箭头的属性,而不是数据类型的属性b.在专家专家视频中进一步讨论了状态monad二元化.

如果解决方案确实存在,请您提供一个printFoo推导的工作示例？顺便说一句,这是一篇有趣的论文,可以帮助我们找到解决方案.

Answer 1

您可能有兴趣进一步深入了解该lens包的概念Prism。

APrism可以用作“智能构造函数”来无条件地构建某些内容（例如漂亮的打印字符串），并对其进行匹配（例如 parse）。

不过，您必须忽略这些定律，或者将这些定律视为只保留一个商，因为从漂亮的打印中得到的字符串很可能不完全是您解析的字符串。