haskell - AST > 1-arity 的免费 Monad？

Question

当我说1-arity | 2-元数 | n-arity，我指的是图理论中的树k-ary tree :

a k-ary tree is a rooted tree in which each node has no more than k children

我一直在我的项目中使用 Free Monad 在 haskell 中创建一个小型 eDSL...但我看到的所有示例都只是一元树(线性 AST)，如下所示:

此数据类型在Free Monad 上提升:

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

我想实现一个比线性 eDSL 更复杂的 eDSL...Free Monad 是一个解决方案吗？如果是，你有 Free Monad > 1-Ary 的例子吗？

Answer 1

具有广义数量概念的树的表示和组成实际上是自由单子(monad)的核心特征之一。

例如，二叉树可以定义为自由单子(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的字段数量)来表示其他参数。

有关更实际的示例，the pipes library is build around such a free monad .