Monad instance for Associative Computations Tree

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

Solution

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.