How to convert a failed computation to a successful one and vice versa

Question

_{This might very well be a solution seeking a problem ... if so, I beg your indulgence!}

Possible implementation:

class Switch' f where
  switch :: f a -> f ()

instance Switch' [] where
  switch []     = [()]
  switch (_:_)  = []

instance Switch' Maybe where
  switch Nothing   = Just ()
  switch (Just _)  = Nothing

The interpretation would be: given a successful computation, make it a failing one; given a failing computation, make it a successful one. I'm not sure, but this seems like it might be sort of the opposite of MonadPlus ... if you squint really hard. ???

Is there a standard typeclass or some other implementation for this concept? What would the underlying math look like, if any (i.e. is this a semigroup, a loop, etc.)?

`switch` is almost an element of order two - it's almost self inverse, in that `switch.switch.switch` = `switch.switch`. It generates eventually repeating orbits (although eventually is the correct word, it sounds lengthy when referring to a wait of 1 iteration). `switch.switch` is idempotent. That's all the maths I thought of to throw at switch just now. — AndrewC, Oct 30 '12 at 20:41
What makes `[()]` the right thing to return, rather than, say, `[(),()..]`? — Daniel Wagner, Oct 30 '12 at 23:10
@AndrewC Maybe the law could be that `switch` specialized to `m () -> m ()` is an [involution](https://en.wikipedia.org/wiki/Involution_(mathematics)). — Petr, Oct 31 '12 at 14:53
@PetrPudlák Yes, I think that's the perfect way of putting it. Good call. Since `switch :: Switch m => m a -> m ()`, we know `switch x :: m ()`, so then all the ones I said hold automatically. Very neat. Also involution is a nicer term than the ones I used. — AndrewC, Oct 31 '12 at 15:16
@AndrewC I realized that this involution law is infeasible. Let's consider `switch` for `[]`. Then everything of type `[()]` (like `[(),(),()]`) must be mapped to `[]`, so `switch` isn't injective and so it doesn't have an inverse. Stating that `switch . switch . switch = switch` seems much more reasonable. We also need something to say that `switch` flips (to rule out things like `switch = const something`). We could require that `switch (return x) = mzero` and/or `switch mzero = return ()`. Seems to me that these two last conditions could be sufficient. — Petr, Nov 01 '12 at 20:00

singpolyma · Answer 1 · 2012-10-30T20:49:49.093

8

switch :: (Alternative f, Eq (f a)) => f a -> f ()
switch x | x == empty = pure ()
         | otherwise = empty

or

switch :: (MonadPlus m, Eq (m a)) => m a -> m ()
switch x | x == mzero = return ()
         | otherwise = mzero

edited Oct 30 '12 at 20:49

answered Oct 30 '12 at 20:38

singpolyma

10,999
5
47
71

@MattFenwick my mistake, I've fixed them up. – singpolyma Oct 30 '12 at 20:52
3

The `Eq` constraint is unfortunate – singpolyma Oct 30 '12 at 20:53
When my data structures contain functions, or something else not `Eq`-able, what should I do? – Matt Fenwick Oct 31 '12 at 15:05
1

@MattFenwick Not sure. It's almost like we want an `isEmpty` for `Monoid`/`Alternative`. Or some typeclass that let's us do an "outer-Eq" where `outereq :: f a -> f b -> Bool` – singpolyma Oct 31 '12 at 18:56

score 4 · Answer 2 · edited Apr 13 '17 at 12:32

I've got a generic solution but it can only work for MonadPlus instances that obey the left catch law (and that's probably only a necessary condition, not sufficient):

isZero :: (MonadPlus m) => m a -> m Bool
isZero x = (x >> return False) `mplus` return True

switch :: (MonadPlus m) => m a -> m ()
switch x = isZero x >>= \r -> if r then return () else mzero

It works for STM too.

(For lists it always returns [()] though, I'd say this definition won't work for anything that is satisfies left distribution.)

It's not possible to define it in this way for Applicatives, because switch inspects the value of isZero, and applicatives cannot do that. (And, MonadPlus instances that satisfy the left-catch rule rarely satisfy Applicative laws.)

Anyhow it'd be interesting to see if switch . (switch :: m () -> m ()) = id holds for this definition.

score 3 · Answer 3 · answered Jul 26 '13 at 07:53

I found a completely different answer, and that is the LogicT monad transformer. It has lnot defined as:

lnot :: MonadLogic m => m a -> m ()
Inverts a logic computation. If m succeeds with at least one value, lnot m fails. If m fails, then lnot m succeeds the value ().

I believe this is exactly what you wanted.

How to convert a failed computation to a successful one and vice versa

3 Answers3