自由组monad
在分类理论中，monad是两个伴随函数的组合。 例如，Maybe monad是由健忘函数组成的免费指向函子。 同样，列表monad是由健忘的函子组成的自由monoid函子。
Monoid是最简单的代数结构之一，所以我想知道编程能否从更复杂的代码中受益。 我没有在标准的Haskell软件包中找到免费的组monad，所以我在这里定义它
data FreeGroup a = Nil | PosCons a (FreeGroup a) | NegCons a (FreeGroup a)
==运算符定义为NegCons x (PosCons xy) == y 。 因此，在length :: FreeGroup a -> Int ，每个PosCons被计数+1，每个NegCons -1（它是唯一的组态射线，每个PosCons上的值+1）。
就像在列表中一样（free monoids）， concat只是乘法， map是函数的函子升级。 所以的单子实例FreeGroup是完全一样的List 。
免费组monad是否有任何编程用途？ 另外，在一个上下文中经常会将monad解释为一个值：对于List ，上下文将是选择或不确定性。 对自由群体monad有这样的解释吗？
自由环和向量空间（总是空闲的）如何？
对于任何代数结构S ，存在一个分类自由函子FS :: Set -> S意味着存在一个函数Haskell调用fold：
foldS :: S s => (a -> s) -> FS a -> s
它将基于a的函数提升为自由对象FS a上的S形。 通常的foldr函数是foldMonoid （在Haskell中称为foldMap ，出于某种原因我不太明白），幺半群是一组函数b -> b ，其组成就是乘法。
为了完整起见，这里是FreeGroup的monad实例：
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
“免费团体monad是否有任何编程用途？”
由于过去四个月缺乏答案，我想答案是'不，不是'。 但这是一个有趣的问题，因为它基于数学基本概念，我认为它也应该。
首先我注意到，提议的免费小组功能也可以很容易地通过一个列表来实现，
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
这是一个很好的定义，因为我们确保我们的自由组只是一个具有一点额外结构的monoid。 它声称自由组只是一个自由幺半群与另一个函子的组合（名字是什么？不是任何一个ab bifunctor而是一个函子F a = L a | R a）。 我们还确保自由组monad实例与自由monoid的monad实例一致。 也就是说，自由群体上的单子运行的条件恰好都是正的，应该像自由monoid上的单子一样，是正确的？
但是，最终，如果我们想要减少逆向我们需要一个Eq a实例。 我们需要在术语级别工作，纯粹的级别信息是不够的。 就我所知，这使得自由幺半群和自由群体之间的类型级别区别变得毫无帮助。 至少不需要依赖打字。
为了讨论实际的编程用途，我会尝试（但失败）提供一个合理的用例。
想象一下，使用“Ctrl”键发送命令序列的文本编辑器。 按住“Ctrl”键时按下的任何按键序列都会在FreeGroup中建模为负片（负片缺陷（： - :)）。 所以自由组的术语'a':+:'b':+:'b':-:'a':-:[]可以用来模拟写入“ab”的emacs行为，将光标移回一个字符，然后到行的开头。 这样的设计很好。 我们可以轻松地将命令和宏嵌入到一个流中，而不需要特殊的保留转义字符。
然而，这个例子失败的正确使用的情况下，因为我们希望'a':+:'b':+:'b':-:'a':-:[]是相同的程序为[]这不是。 此外，它很容易，而不是像上面讨论的那样只是将每个列表项包装在一个Either中。
上一篇: Free group monad