关联计算树的 Monad 实例

Question

我有关联计算树的数据类型

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

为此类型编写了 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 来获取类型“c”。 预期：类型 [b] -> c

Answer 1

这看起来与经典的 ZipList Applicative 类似，这是一个没有 Monad 实例的 Applicative 示例。所以，我认为不可能为

EvalATree

定义一个 Monad 实例。

即使你会以不同的方式定义应用程序就像容器中的 Tree 数据类型那样，那么你本质上仍然是用 Reader monad 来组合 Tree monad，这对我来说似乎是不可能的。

您可以考虑更改为树形转换器，例如TreeT（由于某种原因不在独立包中）。但我不知道这是否符合您想要的行为。