AST> 1-arity的免费Monad吗？

Question

当我说的时候1-arity | 2-arity | n-arity，我指的是grap theory k-ary树中的树：

k叉树是一个有根树，其中每个节点最多有k个子节点

我在我的项目中一直使用Free Monad在haskell中创建一个小型eDSL ...但是我所看到的所有示例都只有这样的一元树（线性AST）：

此数据类型对FreeMonad的提升：

data Toy b next =
    Output b next
  | Bell next
  | Done

我想实现比线性eDSL更复杂的eDSL ... Free Monad是否可以解决该问题？如果是，您是否有Free Monad> 1-Ary的示例？

Answer 1

具有广义的“ arity”概念的树木的表示和组成实际上是自由monads的核心特征之一。

例如，可以将二叉树定义为自由monad，如下所示：

data BinF a = Node a a
type Bin = Free BinF

node :: Bin a -> Bin a -> Bin a
node l r = Free (Node l r)

example :: Bin Int
example = node (node (pure 0)
                     (pure 1))
               (pure 2)
{-
  +---+---0
   \   \--1
    \-2
 -}

同构表示为

data BinF a = Node (Bool -> a)
{- The product type (a, a) is isomorphic to (Bool -> a). -}

其背后的想法是，树节点可以看作是对输入的需求（在这种情况下，是类型的输入Bool），用于选择节点的子节点之一。因此，二叉树可以看作是比特流的解析器。

type Bin = Free BinF

nextBit :: Bin Bool
nextBit = Free (Node (\b -> Pure b))

example :: Bin Int
example = do
  b1 <- nextBit
  if b1 then do
    b2 <- nextBit
    if b2 then
      pure 0
    else
      pure 1
  else
    pure 2

当然，您可以通过更改Bool类型（或Node原始配方中的字段数）来表示其他区域。

对于更实际的示例，管道库是围绕这样一个免费的monad构建的。