Performance of List representation of MonadPlus versus Tree representation
A bit late, but perhaps it'll still help someone.

From the benchmark it's not clear if the time difference is caused by producing a tree or consuming it. I'm not very familiar with operational to make a guess.

It seems that what you're looking for is a free MonadPlus. The closest to this is probably FreeT f [] using FreeT, see also this question. I tried to benchmark it with your code with

exploreFreeTree :: FreeT Identity [] (Sum Int) -&gt; Sum Int
exploreFreeTree = mconcat . iterT runIdentity


that flattens a tree into a list and then concatenates it, and it was almost as fast as plain [].

But there is another potential problem. For free monads the bind operation &gt;&gt;= needs to traverse the whole sequence of operations in the left argument, which can cause performance issues. It's similar to appending two lists. I don't know if operational has a similar problem or not. For free monads the solution is to use the Codensity monad, in particular it's enough to just wrap your computation with improve. For this it might be better to use Free [] instead of FreeT [] Identity (although I haven't checked the details), as Codensity works only on Free, not FreeT.

It might be relevant to read 
Is there a Codensity MonadPlus that asymptotically optimizes a sequence of MonadPlus operations?, although it's somewhat complicated stuff.

An good alternative could be to use logict. You could express your computations using MonadLogic and then run your computation in LogicT to do whatever processing you need to do. The advantage of this is that LogicT is internally build with continuations, which alleviates the problem with &gt;&gt;= performance of Free, and is built exactly to deal with branching computations. If you'd be interested, I could try to work out an example.