“可撤消”应用函子的示例？

Question

我宣布了一个关于应用函子的小组。从我们通常所说的“行动”来看，似乎这样的团体可以使行动被撤销：

\n

import Control.Applicative\n\nclass Alternative f => Undoable f where\n    undo :: f a -> f a\n

\n

成为一个团体，为所有人x :: Undoable f => f a，应满足以下法律：

\n

x <|> undo x \xe2\x89\xa1 empty\nundo x <|> x \xe2\x89\xa1 empty\n

\n

一些实例：

\n

import Control.Arrow\nimport Data.Functor.Compose\nimport Data.Functor.Product\nimport Data.Proxy\n\ninstance Undoable Proxy where\n    undo _ = Proxy\n\ninstance (Undoable f, Applicative g) => Undoable (Compose f g) where\n    undo (Compose x) = Compose (undo x)\n\ninstance (Undoable f, Undoable g) => Undoable (Product f g) where\n    undo (Pair x y) = Pair (undo x) (undo y)\n\ninstance Undoable m => Undoable (Kleisli m a) where\n    undo (Kleisli f) = Kleisli (undo . f)\n

\n

至少对我来说，这些实例不感兴趣。一些非实例包括：

\n

\n

• Maybe：一旦成功，无论其他选择，它总是成功的。

  \n
\n

• []和ZipList：选项总是增加不确定性，而不是从中减去。

  \n
  \n
  • ReadP和ReadPrec：正如上面所暗示的。
  \n
  \n
\n

• IO：从字面上看，这个实例就是一台时间机器。尽管我们可以取现实与时空的商，但有一个实际的反例：一个新的IORef不能被遗忘。

  \n
\n

\n

有没有什么特别有趣的例子Undoable？

\n

Answer 1

我会考虑这样的事情。不是，Prelude.Functor因为密钥需要可订购（也可以Hashable或仅Eq，您知道其中的权衡）。

\n

它基本上是一个允许负重数的多重集。反物质元素。

\n

import qualified Data.Map as Map\nimport qualified Prelude as Hask\nimport Data.List (sortOn)\nimport Control.Category.Constrained.Prelude\nimport Control.Arrow.Constrained\nimport Control.Applicative.Constrained\n\ndata Dirac n k = Dirac { getOccurences :: Map.Map k n }\n\ninstance Real n => Functor (Dirac n) (Ord\xe2\x8a\xa2(->)) (->) where\n  fmap (ConstrainedMorphism f) (Dirac m)\n    = Dirac . Map.fromAscList\n            . concatMap (\\((k,n\xe2\x82\x80):grp) -> case sum $ n\xe2\x82\x80 : map snd grp of\n                     0 -> []\n                     \xce\xbc -> [(k,\xce\xbc)] )\n            . groupBy (comparing fst)\n            . sortOn fst\n            . map (first f)\n            $ Map.toList m\n

\n

和

\n

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

\n

我认为可以围绕此进行一致性Applicative/Alternative构建，但我不完全确定。

\n

Answer 2

任何幺半群都可以提升为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')

任何组都可以提升为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也有更传统的名称Const，并且在例如和朋友中使用效果良好lens。