haskell - 将此 FreeT(显式递归数据类型)函数转换为适用于 FT(教堂编码)

Question

我正在使用FreeT从free库中输入来编写这个“运行”底层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 编写。有没有一种很好的方法来编写此代码，而不涉及通过 FreeT 进行往返(也就是说，以一种需要在 Pure 和 Free 上显式匹配的方式) )？ (我尝试过手动内联，但我不知道如何在 runStateFree 定义中使用不同的 s 来处理递归)。或者这可能是显式递归数据类型必然比 Church (mu) 编码性能更高的情况之一？

Answer 1

这是定义。实现本身没有任何技巧。不要思考并进行类型检查。是的，至少其中之一 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 的使用明显可疑在handleS ，但只要 run 就有效从不查看 handleS 产生的状态。它几乎立即被evalStateT之一扔掉了。 .

理论上，存在 FT f (StateT s m) a 类型的项这打破了这个不变量。实际上，这几乎肯定不会发生；你真的必须不遗余力地对这些延续做出一些道德上错误的事情。

在下面的完整要点中，我还展示了如何使用 QuickCheck 测试它确实相当于使用 FreeT 的初始版本。 ，有具体证据表明上述不变量成立:

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