Examples of "undoable" applicative functors?

Question

I declared a group on applicative functors. Judging by what we usually call "actions", it seems that such group would enable the action to be undone:

import Control.Applicative

class Alternative f => Undoable f where
    undo :: f a -> f a

Being a group, for all x :: Undoable f => f a, the following laws shall satisfy:

x <|> undo x ≡ empty
undo x <|> x ≡ empty

Some instances:

import Control.Arrow
import Data.Functor.Compose
import Data.Functor.Product
import Data.Proxy

instance Undoable Proxy where
    undo _ = Proxy

instance (Undoable f, Applicative g) => Undoable (Compose f g) where
    undo (Compose x) = Compose (undo x)

instance (Undoable f, Undoable g) => Undoable (Product f g) where
    undo (Pair x y) = Pair (undo x) (undo y)

instance Undoable m => Undoable (Kleisli m a) where
    undo (Kleisli f) = Kleisli (undo . f)

At least for me, these instances are of no interest. Some non-instances include:

• Maybe: Once successful, it will be always a success regardless of other options.

• [] and ZipList: Options always add nondeterminism, not subtract from it.

  • ReadP and ReadPrec: As implied by above.

• IO: Taken literally, this instance would be a time machine. Even though we may take the quotient of the reality over time-space, there is a practical counterexample: A new IORef cannot be forgotten.

Is there any particularly interesting instance of Undoable?

Answer 1

I would consider something like this. Not a Prelude.Functor because the keys need to be orderable (could also be Hashable or only Eq, you know the tradeoffs).

It's basically a multiset that allows negative multiplicities. Antimatter elements as it were.

import qualified Data.Map as Map
import qualified Prelude as Hask
import Data.List (sortOn)
import Control.Category.Constrained.Prelude
import Control.Arrow.Constrained
import Control.Applicative.Constrained

data Dirac n k = Dirac { getOccurences :: Map.Map k n }

instance Real n => Functor (Dirac n) (Ord⊢(->)) (->) where
  fmap (ConstrainedMorphism f) (Dirac m)
    = Dirac . Map.fromAscList
            . concatMap (\((k,n₀):grp) -> case sum $ n₀ : map snd grp of
                     0 -> []
                     μ -> [(k,μ)] )
            . groupBy (comparing fst)
            . sortOn fst
            . map (first f)
            $ Map.toList m

with

instance Num n => Undoable (Dirac n) where
  undo (Dirac m) = Dirac $ Map.map negate m

I think there can be a conforming Applicative / Alternative built around this, but I'm not completely sure.

Answer 2

Any monoid can be lifted to an Alternative:

newtype ViaMonoid m a = ViaMonoid m

instance Monoid m => Applicative (ViaMonoid m) where
    pure _ = ViaMonoid mempty
    ViaMonoid f <*> ViaMonoid x = ViaMonoid (f <> x)

instance Monoid m => Alternative (ViaMonoid m) where
    empty = ViaMonoid mempty
    ViaMonoid m <|> ViaMonoid m' = ViaMonoid (m <> m')

Any group can be lifted to Undo:

class Monoid g => Group g where
    -- law: g <> inverse g = inverse g <> g = mempty
    inverse :: g -> g

instance Group g => Undoable (ViaMonoid g) where
    undo (ViaMonoid m) = ViaMonoid (inverse m)

ViaMonoid is also known by the more traditional name Const, and is used to good effect in e.g. lens and friends.