代码之家 › 专栏 › 技术社区 › Justin L.

将这个FreeT(显式递归数据类型)函数转换为FT(教会编码)

church-encoding free-monad haskell

0

Justin L. · 技术社区 · 6 年前

我用的是 FreeT 从 自由的 StateT

runStateFree
    :: (Functor f, Monad m)
    => s
    -> FreeT f (StateT s m) a
    -> FreeT f m (a, s)
runStateFree s0 (FreeT x) = FreeT $ do
    flip fmap (runStateT x s0) $ \(r, s1) -> case r of
      Pure y -> Pure (y, s1)
      Free z -> Free (runStateFree s1 <$> z)

但是,我正在尝试将其转换为 FT ,改为教会编码的版本:

runStateF
    :: (Functor f, Monad m)
    => s
    -> FT f (StateT s m) a
    -> FT f m (a, s)
runStateF s0 (FT x) = FT $ \ka kf -> ...

runStateF s0 (FT x) = FT $ \ka kf ->
    ka =<< runStateT (x pure (\n -> _ . kf (_ . n)) s0

但第一个洞的类型是 m r -> StateT s m r 第二个洞的类型是什么 StateT s m r -> m r …这意味着我们必须在这个过程中失去状态。

FreeT 函数可以用 FT . 有没有一个很好的方式来写这篇文章,不涉及来回通过 弗里特 (也就是说,以一种需要在 Pure 和 Free )? (我尝试过手动内联,但不知道如何使用不同的方法处理递归 s 它的定义是 runStateFree ). 或者这是显式递归数据类型必然比church(mu)编码性能更好的情况之一?

0 回复 | 直到 6 年前

1

Li-yao Xia 6 年前

定义如下。实现本身没有技巧。别想了,好好检查一下。是的,至少有一个 fmap

runStateF
    :: (Functor f, Monad m)
    => s
    -> FT f (StateT s m) a
    -> FT f m (a, s)
runStateF s0 (FT run) = FT $ \return0 handle0 ->
  let returnS a = StateT (\s -> fmap (\r -> (r, s)) (return0 (a, s)))
      handleS k e = StateT (\s -> fmap (\r -> (r, s)) (handle0 (\x -> evalStateT (k x) s) e))
  in evalStateT (run returnS handleS) s0

我们有两个无状态函数(即 m )

return0 :: a -> m r
handle0 :: forall x. (x -> m r) -> f x -> m r

我们必须把它们分成两部分( StateT s m )具有以下签名的变体。下面的评论给出了一些关于 handleS .

returnS :: a -> StateT s m r
handleS :: forall x. (x -> StateT s m r) -> f x -> StateT s m r

-- 1.                                               --    ^   grab the current state 's' here
-- 2.                                               --      ^ call handle0 to produce that 'm'
-- 3.                             ^ here we will have to provide some state 's': pass the current state we just grabbed.
--                                  The idea is that 'handle0' is stateless in handling 'f x',
--                                  so it is fine for this continuation (x -> StateT s m r) to get the state from before the call to 'handle0'

这个词的用法显然可疑 fmap公司 在里面 ,但只要 run 从不看 手柄 . 它几乎立刻被一个 evalStateT .

在理论上,存在类型术语 FT f (StateT s m) a 这打破了不变量。实际上,这种情况几乎肯定不会发生;你真的必须千方百计去做一些道德上错误的事情。

在下面的完整要点中,我还展示了如何使用QuickCheck测试它是否确实等同于您的初始版本 FreeT

https://gist.github.com/Lysxia/a0afa3ca2ea9e39b400cde25b5012d18

2

1

phadej 6 年前

我会说不,即使是像 cutoff FreeT :

cutoff :: (Functor f, Monad m) => Integer -> FT f m a -> FT f m (Maybe a)
cutoff n = toFT . FreeT.cutoff n . fromFT

一般来说,您可能会看到:

improve :: Functor f => (forall m. MonadFree f m => m a) -> Free f a

通过在后台使用F来提高构建只包含绑定和返回的自由单子的代码的渐近性能。

一、 e.你将构建 Free 效率很高,但你需要做什么就做什么 免费的 (也许再次,通过 improve ing)。