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.[]
andZipList
: Options always add nondeterminism, not subtract from it.ReadP
andReadPrec
: 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 newIORef
cannot be forgotten.
Is there any particularly interesting instance of Undoable
?
CodePudding user response:
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.
CodePudding user response:
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.