Monad instance for Associative Computations Tree

Question

I have data type of Associative Computations Tree

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

Wrote Functor and Applicative for this type

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

How can i make Monad type class instance for this tree?

I try

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

But i cant unwrap f to get type "c". Expected: type [b] -> c

Answer 1

EvalATree b has no Monad instance that’s compatible with this Applicative instance, for the same reason as ZipList: given two inputs with different lengths, combining them by zipping will truncate the longer one. So the Monad instance isn’t associative—depending on how computations are grouped, you can get different results. A zippy Monad instance is valid only if the inputs are always the same shape—such as a fixed-length vector/tuple, or an infinite stream.

However, I think this tree type may not be quite what you want anyway. I assume you wanted Node f ts to represent taking the results of the computations ts, and giving them as inputs to the function f. But there’s no connection between the result type a and the input type b, without further assumptions about b. Your Applicative instance doesn’t offer a way to make an EvalATree b a that actually uses the [b].

So it’s hard to say what you should do without more context, but here are some suggestions for things to try.

• Just skip writing a Monad instance. You can still use do notation with ApplicativeDo.

• Change the Applicative instance to use a Cartesian product, like lists.

• Make Applicative and Monad instances with some constraints, such as Monoid b.

• Get rid of the type parameter b, merging it with a.

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

• Use [a] or Monoid a => a instead of EvalATree b a.

Answer 2

Your applicative seems similar to the classic ZipList applicative which is an example of an applicative that has no monad instance. So, I don't think it is possible to define a monad instance for EvalATree.

And even if you would define the applicative differently like the Tree data type from containers does:

instance Applicative (EvalATree b) where
  pure = Leaf
  Leaf f <*> x = fmap f x
  f <*> Leaf y = fmap ($ x) f
  Node g xs <*> Node f ys = Node (g <*> f) [x <*> y | x <- xs, y <- ys]

Then you'd still essentially be composing the Tree monad with the Reader monad which seems impossible to me.

You could consider changing to tree transformers like TreeT (for some reason not in a standalone package). You'd get a type like this:

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

But I don't know if that matches the behavior you want.