By the way, I'm also interested in knowing if extensible-effects have some relation to MonadPlus or Applicative in any way.
The Eff monad is a genuine monad, and all monads are Applicatives. So, extensible-effects directly relates to Applicative. As Oliver Charles noted, the extensible-effects package provides the Choose effect, with the operation choose :: Member Choose r => [a] -> Eff r a to non-deterministically select an element from a list. It is easy to see that Choose is as alias of MonadPlus: given choose one can implement mplus and mzero (the latter is choose []). Conversely, MonadPlus lets us implement Choose. The signature of choose says the resulting computation will have the Choose effect -- and, since the effect label |r| is left polymorphic, the computation may have an unspecified number of other effects (including IO).
handler. So, we get another implementation of LogicT, this time in terms of extensible effects.
This sounds very interesting - is this work available for us to look at anywhere?
Actually yes, from the very slightly updated http://okmij.org/ftp/Haskell/extensible/Eff.hs Please search for 'Soft-cut'. The implementation is so trivial that it didn't seem worth mentioning before. The most interesting part is reflect :: VE a r -> Eff r a which is the inverse of admin (aka, reify). It is gratifying that monadic reification-reflection can be implemented with extensible-effects _generically_, once and for all.