hangscer

Advanced-Scala之cats学习笔记(二)

2017/06/06

Monoids and Semigroups(幺半群与半群)

至于什么是幺半群与半群,可以参考半群-wikipedia幺半群-wikipedia。它们允许互相结合,针对IntStringListOption以及其它很多很多类型都有具体实例。
Integer addition
整数的加法操作是二元操作,两个整数相加仍然得到一个整数:

1
2
scala> 1+2
res0: Int = 3

当然对于加法操作,存在一个幺元0,有着这样的有趣的现象:a+0==0+a==a:

1
2
3
4
5
scala> 2+0
res1: Int = 2
scala> 0+2
res2: Int = 2

加法还存在结合性,无论从左结合还是从右结合,其结果一样:

1
2
3
4
5
scala> ((1+2)+3)
res3: Int = 6
scala> (1+(2+3))
res4: Int = 6

Definition of a Monoid

a monoid for a type A is:

  • (A,A)=>A结合操作
  • 一个幺元empty

幺半群描述一类数据操作现象。
monoid在Cats中的定义为:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
trait Monoid[@sp(Int, Long, Float, Double) A] extends Any with Semigroup[A] {
def empty: A
def isEmpty(a: A)(implicit ev: Eq[A]): Boolean =
ev.eqv(a, empty)
override def combineN(a: A, n: Int): A =
if (n < 0) throw new IllegalArgumentException("Repeated combining for monoids must have n >= 0")
else if (n == 0) empty
else repeatedCombineN(a, n)
def combineAll(as: TraversableOnce[A]): A =
as.foldLeft(empty)(combine)
override def combineAllOption(as: TraversableOnce[A]): Option[A] =
if (as.isEmpty) None else Some(combineAll(as))
}

monoid法则包括associative以及identity element两个法则。
我们可以定义函数来验证数据是否满足monoid法则:

1
2
def associativeLaw[A](x: A, y: A, z: A)(implicit m:Monoid[A]): Boolean =
m.combine(x, m.combine(y, z)) == m.combine(m.combine(x, y), z)
1
2
def identityLaw[A](x: A)(implicit m: Monoid[A]): Boolean =
(m.combine(x, m.empty) == x) &&(m.combine(m.empty, x) == x)

很显然,减法并不满足monoid法则。

Definition of a Semigroup

半群与幺半群仅仅从名字上你就可以明白它们的联系与区别。半群没有幺元,就酱。
从Cats中对半群与幺半群的实现,进一步看出它们的区别:

1
2
3
trait Semigroup[A] extends Serializable {
def combine(x: A, y: A): A
}
1
2
3
trait Monoid[A] extends Semigroup[A] {
def empty: A
}

Exercise:The Truth About Monoids

对于Boolean类型,你可以定义多少monoid呢?

1
2
3
4
5
6
7
8
val orBoolean:Monoid[Boolean]=new Monoid[Boolean] {
override def empty = false
override def combine(x: Boolean, y: Boolean) = x || y
}
val andBoolean:Monoid[Boolean]=new Monoid[Boolean] {
override def empty = true
override def combine(x: Boolean, y: Boolean) = x && y
}

Exercise:All Set for Monoids

Set定义Monoid,涉及到类型构造器以及高阶类型:

1
2
3
4
def setMonoid[A]:Monoid[Set[A]]=new Monoid[Set[A]] {
override def empty =Set.empty[A]
override def combine(x: Set[A], y: Set[A]) = x union y
}

Monoids in Cats

Obtaining Instances

1
2
3
4
5
import cats.Monoid
import cats.instances.string._
val r=Monoid[String].combine("hah","asd")
Monoid.apply[String].combine("ha","asd")
println(r)

让我们来看看它的object Monoid

1
2
3
object Monoid extends MonoidFunctions[Monoid] {
@inline final def apply[A](implicit ev: Monoid[A]): Monoid[A] = ev
}

它需要隐式实例:

1
2
3
4
5
6
7
8
package cats
package object instances {
object all extends AllInstances
object list extends ListInstances
object option extends OptionInstances
object string extends StringInstances
.......
}

可以string是父类为StringInstances的对象。让我们再看看StringInstances的具体实现:

1
2
3
4
5
6
package cats
package instances
trait StringInstances extends cats.kernel.instances.StringInstances {
implicit val catsStdShowForString: Show[String] =
Show.fromToString[String]
}

Default Instances

Monoid类型类的具体类型实例在cats.instances包中。比如我们现在想要针对Int类型的类型类的实例:

1
2
3
4
import cats.Monoid
import cats.instances.int._
val r=Monoid[Int].combine(11,22)
println(r)//33

相似的,针对Option[Int]类型的Monoid实例分别需要引入cats.instances.intcats.instances.option包。

1
2
3
4
import cats.instances.int._
import cats.instances.option._
val r=Monoid[Option[Int]].combine(Some(1),None)
println(r)

Monoid Syntax

Cats provides syntax for the combine method in the form of the |+|operator.Because combine technically come from Seigroup,we access the syntax by importing from cats.syntax.semigroup.

Cats提供了操作符|+|来结合操作数。结合操作来自于半群,我们需要从cats.syntax.semigroup引入它。

1
2
3
4
5
6
import cats.syntax.semigroup._
import cats.instances.all._
val stringResult = "Hi " |+| "there" |+| Monoid[String].empty
val r= 1 |+| 2 |+| Monoid[Int].empty
val r1=(Some(1):Option[Int]) |+| Monoid[Option[Int]].empty
//想想为什么要这么写呢?

Monoid不支持协变。这就是原因。

自定义类型类实例

1
2
3
4
5
6
7
import cats.syntax.semigroup._
implicit val intMonoid:Monoid[Int]=new Monoid[Int]{
override def empty = 1
override def combine(x: Int, y: Int) = x+y
}
val r= 1 |+| 2 |+| Monoid[Int].empty
println(r) //4