自由群单子

Question

在范畴理论中，一个单子是两个伴随函子的组合。例如，也许单子是由遗忘函子组成的自由点集函子。同样地，列表单子是由遗忘函子组成的自由么半函子。

半群是最简单的代数结构之一，所以我想知道编程是否可以从更复杂的结构中受益。我在标准的Haskell包中没有找到免费的组单子，所以我将在这里定义它

data FreeGroup a = Nil | PosCons a (FreeGroup a) | NegCons a (FreeGroup a)

自由环和向量空间（它们总是自由的）呢？

对于任何代数结构s，一个范畴自由函子fs::set->s的存在意味着Haskell调用fold的函数的存在：

foldS :: S s => (a -> s) -> FS a -> s

它将基于a的函数提升为自由对象FS a上的S-morphism。通常的foldr函数是foldmonoid的专门化（在Haskell中称为foldmap，出于某种原因，我不太明白），monoid是函数的集合b->b，组合为乘法。

mult :: FreeGroup a -> FreeGroup a -> FreeGroup a
mult Nil x = x
mult x Nil = x
mult (PosCons x y) z = PosCons x (mult y z)
mult (NegCons x y) z = NegCons x (mult y z)

inverse :: FreeGroup a -> FreeGroup a
inverse Nil = Nil
inverse (PosCons x y) = mult (inverse y) (NegCons x Nil)
inverse (NegCons x y) = mult (inverse y) (PosCons x Nil)

groupConcat :: FreeGroup (FreeGroup a) -> FreeGroup a
groupConcat Nil = Nil
groupConcat (PosCons x l) = mult x (groupConcat l)
groupConcat (NegCons x l) = mult (inverse x) (groupConcat l)

instance Functor FreeGroup where
  fmap f Nil = Nil
  fmap f (PosCons x y) = PosCons (f x) (fmap f y)
  fmap f (NegCons x y) = NegCons (f x) (fmap f y)

instance Applicative FreeGroup where
  pure x = PosCons x Nil
  fs <*> xs = do { f <- fs; x <- xs; return $ f x; }

instance Monad FreeGroup where
  l >>= f = groupConcat $ fmap f l

Answer 1

“免费团体monad有任何编程用途吗？”

由于在过去的四个月里缺乏答案，我想答案是‘不，不是真的’。但这是一个有趣的问题，因为它是基于基本的数学概念，所以在我看来（也）它应该是。

首先，我注意到提议的自由组功能也可以很容易地用一个a列表来实现，

type FreeGroupT a = [Either a a]

fgTofgT :: FreeGroup a -> FreeGroupT a
fgTofgT Nil = []
fgTofgT (a :+: as) = Right a : fgToList as
fgTofgT (a :-: as) = Left a : fgToList as

fgTTofg :: FreeGroupT a -> FreeGroup a
fgTTofg [] = Nil
fgTTofg (Right a : as) = a :+: fgTTofg as
fgTTofg (Left a : as) = a :-: fgTTofg as

--using (:-:) instead of NegCons
--and   (:+:) instead of PosCons

但是，作为一个正确的用例，这个示例失败了，因为我们希望'a':+:'b':+:'b':-:'a':-:[]与[]是相同的程序，但实际上并非如此。此外，将每个列表术语包装在上面讨论过的Off中也很容易。