如何为Associative Computations Tree实现Monad实例？

定义的数据类型 #

用户定义了关联计算树（Associative Computations Tree）的数据类型EvalATree：

data EvalATree b a = Leaf a | Node ([b] -> a) [EvalATree b a]

已实现的Functor和Applicative实例 #

已经为该类型实现了Functor和Applicative实例：

instance Functor (EvalATree b) where
  fmap :: (a -> c) -> EvalATree b a -> EvalATree b c
  fmap f (Leaf a) = pure (f a)
  fmap f (Node g trees) = Node (f . g) (fmap (fmap f) trees)

instance Applicative (EvalATree b) where
  pure :: a -> EvalATree b a
  (<*>) :: EvalATree b (a -> c) -> EvalATree b a -> EvalATree b c
  (Leaf f) <*> (Leaf x) = fmap f (Leaf x)
  (Leaf f) <*> (Node g trees) = Node (f . g) (fmap (fmap f) trees)
  (Node g trees) <*> (Leaf x) = Node (g <*> pure x) (fmap (<*> pure x) trees)
  (Node g trees) <*> (Node f otherTrees) = Node (g <*> f) (zipWith (<*>) trees otherTrees)
  pure = Leaf

遇到的问题 #

尝试实现Monad类型类实例时，出现类型匹配问题：

instance Monad (EvalATree b) where
  return :: a -> EvalATree b a
  (>>=) :: EvalATree b a -> (a -> EvalATree b c) -> EvalATree b c
  (Leaf a) >>= f = f a
  (Node g trees) >>= f = Node (g >>= f) (fmap (>>= f) trees)
  return = pure

核心问题是无法将f拆解，得到期望的[b] -> c类型。

正确的Monad实例实现 #

要解决类型匹配问题，关键是处理Node构造器中[b] -> a函数与f :: a -> EvalATree b c的绑定逻辑，将其转换为[b] -> c类型的函数。具体实现如下：

instance Monad (EvalATree b) where
  return :: a -> EvalATree b a
  return = pure

  (>>=) :: EvalATree b a -> (a -> EvalATree b c) -> EvalATree b c
  -- Leaf节点直接应用绑定函数f
  Leaf a >>= f = f a
  -- Node节点需分别处理函数和子树
  Node g trees >>= f = 
    let -- 先递归绑定所有子树，得到新的EvalATree列表
        boundTrees = fmap (>>= f) trees
        -- 构造新的[b] -> c函数：输入[b]后，先通过g得到a，再用f生成EvalATree，最后提取对应输入下的c值
        newG :: [b] -> c
        newG bs = case f (g bs) of
                    Leaf c -> c
                    Node h _ -> h bs
    in Node newG boundTrees

实现说明 #

• 对于Node构造器，首先递归绑定所有子树，这部分逻辑和原尝试一致。
• 重点是newG函数的构造：当通过g bs得到a并应用f后，会得到一个EvalATree b c，我们需要从这个树中提取对应bs输入的c值：
  • 如果结果是Leaf c，直接返回c；
  • 如果结果是Node h _，则用当前的bs输入调用h得到c。

这样处理后，newG就满足了[b] -> c的类型要求，解决了类型不匹配的问题。

内容的提问来源于stack exchange，提问作者WmWarescot