打印自由单子

Question

可以将自由单子翻译成任何其他单子，但是在给定类型为Free f x的值时，我希望打印整棵树，而不是将生成的AST的每个节点映射到另一个单子中的某些其他节点。

Gabriel Gonzales直接使用该值

showProgram :: (Show a, Show r) => Free (Toy a) r -> String
showProgram (Free (Output a x)) =
    "output " ++ show a ++ "\n" ++ showProgram x
showProgram (Free (Bell x)) =
    "bell\n" ++ showProgram x
showProgram (Free Done) =
    "done\n"
showProgram (Pure r) =
    "return " ++ show r ++ "\n"

可以将其抽象为

showF :: (x -> b) -> ((Free f x -> b) -> f (Free f x) -> b) ->  Free f x -> b
showF backLiftValue backLiftF  = fix (showFU backLiftValue backLiftF)
    where
      showFU :: (x -> b) -> ((Free f x -> b) -> f (Free f x) -> b) -> (Free f x -> b) -> Free f x -> b
      showFU backLiftValue backLiftF next = go . runIdentity . runFreeT where
          go (FreeF c ) = backLiftF next  c
          go (Pure x) =   backLiftValue x 

如果我们有一个类似于多态函数的函数（使用Choice x = Choice x x作为函数子），那么调用起来就很容易。

showChoice :: forall x. (x -> String) ->  Choice x -> String
showChoice show (Choice a b) =  "Choice (" ++ show  a ++  "," ++ show b ++ ")"

但是对于一个简单的操作来说，这似乎相当复杂... 还有哪些方法可以从 f x -> b 转换为 Free f x -> b ？

- nicolas

Answer 1

使用 iter 和 fmap:

{-# LANGUAGE DeriveFunctor #-}

import Control.Monad.Free

data Choice x = Choice x x deriving (Functor)

-- iter :: Functor f => (f a -> a) -> Free f a -> a
-- iter _   (Pure a) = a
-- iter phi (Free m) = phi (iter phi <$> m)

showFreeChoice :: Show a => Free Choice a -> String
showFreeChoice =
      iter (\(Choice l r) -> "(Choice " ++ l ++ " " ++ r ++ ")")
    . fmap (\a -> "(Pure " ++ show a ++ ")")

fmap将Free f a转换为Free f b，而iter则负责其余的工作。您可以将其分解出来，并可能获得更好的性能：

iter' :: Functor f => (f b -> b) -> (a -> b) -> Free f a -> b
iter' f g = go where
  go (Pure a)  = g a
  go (Free fa) = f (go <$> fa)

- András Kovács

---

啊，太好了！谢谢。现在我明白了，显然需要将代数 f 翻译成代数 Free f。 - nicolas

我喜欢你的 iter。最近我试图找到一些类似的通用工具（有信心肯定有这样的工具），但不知何故没有找到合适的类型。 - dfeuer

这个值得与iter' f g = go where ...进行基准测试比较。一些以前的测量结果表明，当至少有两个参数在递归过程中保持不变时，这种方法往往是有效的。 - dfeuer

我还应该提到 Functor f => forall b. (f b -> b) -> (a -> b) -> b 等同于 Free f a，并且是 Church free monad 的定义，而 toF 与 iter' 是相同的。 - András Kovács

@AndrásKovács 很好，感谢您发现并添加了这个。我想阅读关于Cayley表示的内容，它包括密度作为特殊情况，因此这可能是一个有用的链接。 - nicolas

顺便提一下，这个'iter'是由Nicolas Wu提到的，他称其为handle https://skillsmatter.com/skillscasts/6733-transformers-handlers-in-disguise - nicolas