我所理解的monad(1):半群(semigroup)与幺半群(monoid)

google到数学里定义的群(group): G为非空集合,如果在G上定义的二元运算 *,满足

(1)封闭性(Closure):对于任意a,b∈G,有a*b∈G
(2)结合律(Associativity):对于任意a,b,c∈G,有(a*b)*c=a*(b*c)
(3)幺元 (Identity):存在幺元e,使得对于任意a∈G,e*a=a*e=a
(4)逆元:对于任意a∈G,存在逆元a^-1,使得a^-1*a=a*a^-1=e

则称(G,*)是群,简称G是群。

如果仅满足封闭性和结合律,则称G是一个半群(Semigroup);如果仅满足封闭性、结合律并且有幺元,则称G是一个含幺半群(Monoid)。

相比公式还是用代码表达更容易理解,下面表示一个半群(semigroup):

trait SemiGroup[T] {
    def append(a: T, b: T): T
}

特质SemiGroup,定义了一个二元操作的方法append,可以对半群内的任意2个元素结合,且返回值仍属于该半群。

我们看具体的实现,一个Int类型的半群实例:

object IntSemiGroup extends SemiGroup[Int] {
    def append(a: Int, b: Int) = a + b
}

// 对2个元素结合
val r = IntSemiGroup.append(1, 2)

现在在半群的基础上,再增加一个幺元(Identity,也翻译为单位元),吐槽一下,幺元这个中文不知道最早谁起的,Identity能表达的意义(同一、恒等)翻译到中文后完全消失了。

trait Monoid[T] extends SemiGroup[T] {
    // 定义单位元
    def zero: T
}

上面定义了一个幺半群,继承自半群,增加了一个单位元方法,为了容易理解,我们用zero表示,半群里的任何元素a与zero结合,结果仍是a本身。

构造一个Int类型的幺半群实例:

object IntMonoid extends Monoid[Int] {
    // 二元操作
    def append(a: Int, b: Int) = a + b
    // 单位元
    def zero = 0
}

构造一个String类型的幺半群实例:

object StringMonoid extends Monoid[String] {
    def append(a: String, b: String) = a + b
    def zero = ""
}

再构造一个复杂点的 List[T] 的幺半群工厂方法:

def listMonoid[T] = {
    new Monoid[List[T]] { 
        def zero = Nil
        def append(a: List[T], b: List[T]) = a ++ b 
    }
}

OK,现在我们已经了解了幺半群是什么样了,但它有什么用?

我所理解的monad(1):半群(semigroup)与幺半群(monoid)》上有13条评论

    1. hongjiang 文章作者

      嗯,有人跟我讨论过,“老幺”在一些地方表示最小的,“幺”也有“一”的意思,是我的无知。

      回复
  1. mi2think

    最近学haskell也掉进monad的坑,不过真的很有趣,还在琢磨中!

    回复
    1. hongjiang 文章作者

      这个世界解决问题的途径很多,函数式语言让我们从另一个维度思考,monad是这种思维方式上的一个奇葩。;-)

      回复
  2. openwares.net

    有一处错误:

    “(1)封闭性(Closure):对于任意a,b,c∈G,有a*b∈G ”
    应为:
    “(1)封闭性(Closure):对于任意a,b∈G,有a*b∈G”

    回复
  3. blackzwei

    我记得离散数学里是叫做零元的似乎…. ….
    加法里是0 乘法里是1

    回复
  4. enjoy飞子翾

    数学定义很简单嘛,为什么搞代码,除了准确,既不直观,又不明了,只是很新鲜。

    回复
  5. 周日明

    这个幺元是一个打麻将的人取的,麻将中有幺鸡。

    回复

发表评论

电子邮件地址不会被公开。 必填项已用*标注