Clarify laws of NonDet

[michaelpj]

NonDet satisfies the "left-catch" law for MonadPlus but not the "left-distribution" law. This is a little surprising, since that makes it more "maybe-like" than "list-like" (Maybe satisfies "left-catch" but not "left-distribution", and vice versa for lists), which isn't quite what I'd expect for a non-determinism monad.

return x `mplus` m = return x -- left catch
(m `mplus` n) >>= k  =  (m >>= k) `mplus` (n >>= k) -- left distribution

In practice this means that:

do
   v <- a <|> b
   f v

is not the same as

(f a <|> f b)

so you can't guard after you <|>, etc.

I don't think it's possible to satisfy "left-distribution" with NonDet as it's currently implemented, since it's implemented with exceptions. So I just think we should say something in the documentation, to save future people some time!

[arybczak]

Somewhat related: fused-effects/fused-effects#457

Perhaps this effect shouldn't have been named NonDet 😛 but it's too late.

Do you have any suggestion for the documentation improvement?

[michaelpj]

Interesting! I think that's the opposite. I don't know what "algebraic" means in this context, but it sounds like their Choice effect satisfies left-distribution ,which is what I want.

I'll make you a PR :)