可表示函子同构于 (Bool -> a)

Question

我想我会尝试有趣的 Representable-functors 包为给定的函子定义 Monad 和 Comonad 实例data Pair a = Pair a a，用Bool表示；正如我之前关于向量 monad 的问题的回答中提到的。

我注意到的第一件事是，为了使我的类型成为可表示的实例，我不仅应该定义制表符和索引，还应该确保我的类型是 Indexable、Distributive、Keyed、Apply、Applicative 的实例，和函子类型类。好了，好了，index就完成了Indexable的定义，Apply的<.>函数就可以了使用Applicative中的<*>；需要一个 Functor 实例也就不足为奇了。尽管如此，我对 Keyed 和 Distributive 的实例表示怀疑。

data Pair a = Pair a a
  deriving (Show,Eq)

instance Functor Pair where
  fmap f (Pair x y) = Pair (f x) (f y)

type instance Key Pair = Bool

instance Keyed Pair where
  mapWithKey f (Pair x y) = Pair (f False x) (f False y)

instance Indexable Pair where
  index (Pair x _) False = x
  index (Pair _ y) True  = y

instance Applicative Pair where
  pure a = Pair a a
  Pair f g <*> Pair x y = Pair (f x) (g y)

instance Apply Pair where
  (<.>) = (<*>)

instance Distributive Pair where
  collect f x = Pair (getL . f <$> x) (getR . f <$> x)
    where getL (Pair x _) = x
          getR (Pair _ y) = y

instance Representable Pair where
  tabulate f = Pair (f False) (f True)

我的 mapWithKey 定义借用了 Keyed 的 [] 实例的定义：尽管我不明白为什么 0每次迭代都使用它。我对 Pair 的每个术语都使用了类似的 False。

当我通过定义 Monad 和 Comonad 实例得出结论时，我发现 Bool 需要 Semigroup 定义 >Extend，以及 Comonad 的 Monoid 定义。我遵循 Either 的 Semigroup 实例，它与 (||) 同构，并为 False 选择mempty：

instance Monad Pair where
  return = pureRep
  (>>=)  = bindRep

instance Monoid Bool where
  mempty = False
  mappend = (||)

instance Semigroup Bool where
  (<>) = mappend

instance Extend Pair where
  extend = extendRep -- needs Bool Semigroup

instance Comonad Pair where
  extract = extractRep -- needs Bool Monoid

那么，我是否正确、惯用地满足了 Representable 类的要求？

Answer 1

是的，你有。尽管您的 Keyed 实例已关闭。

instance Keyed Pair where
    mapWithKey f (Pair x y) = Pair (f False x) (f True y)

或者甚至更简单

instance Keyed Pair where
    mapWithKey = mapWithKeyRep

，类似

instance Distributive Pair where
    distribute = distributeRep

给定 index 和 tabulate，您可以使用 Representable 模块中的各种 fooRep 方法来提供所有其他超类的定义。

Extend 和 Comonad 定义实际上并不是可表示 要求的一部分。不过它们也被包含在内，因为可表示意味着您与函数同构，这使您能够重复使用“指数”Comonad（又名 cowriter，或 追踪 comonad) 也成为一个 Comonad ，只要你的表示有一些幺半群。但这不是必需的，主要是因为我无法将其限制为所涉及的类型。

您可能想删除 Bool 的 Semigroup 和 Monoid，而只需手动实现 extend 和 extract 。这很容易。

instance Extend Pair where
    extend f p@(Pair a b) = Pair (f p) (f (Pair b a))

instance Comonad Pair where
    extract (Pair a b) = a

另外，此类型是 由 rel="noreferrer">representable-tries 包，其中包含许多其他实例。

并且，

import Control.Applicative
bool = [True, False]
f tt _tf _ft _ff True  True  = tt
f _tt tf _ft _ff True  False = tf
f _tt _tf ft _ff False True  = ft
f _tt _tf _ft ff False False = ff
associative f = and (assoc <
gt; bool <*> bool <*> bool) where 
    assoc a b c = f (f a b) c == f a (f b c)
semigroups = filter associative 
    [ f tt tf ft ff | tt <- bool, tf <- bool, ft <- bool, ff <- bool ]
unital (u, f) = all unit bool where 
    unit a = f u a == a && f a u == a
monoids = filter unital 
    [ (u, f) | u <- bool, f <- semigroups ]

表明正如您猜测的那样，有 4 个可能的幺半群，如果您只想要一个扩展实例，则有 8 个半群可用。