AST > 1-arity 的免费 Monad？

Question

当我说 1-arity | 2-arity | 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... =16=]

此数据类型提升 Free Monad :

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

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

Answer 1

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

例如，二叉树可以定义为一个自由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类型的输入），用于select其中一个children 节点。因此，二叉树可以看作是比特流的解析器。

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.

AST > 1-arity 的免费 Monad？

Free Monad for AST > 1-arity?

compiler-construction

haskell

category-theory