=> B)(implicit F: Monoid[B]): B = foldLShape(fa, F.zero)((b, a) => F.append(b, f(a)))._1 7
8 override def foldRight[A, B](fa: F[A], z: => B)(f: (A, => B) => B) =
9 foldMap(fa)((a: A) => (Endo.endo(f(a, _: B)))) apply z 10 ...
这个foldMap就是一个游览可折叠结构的函数。在游览过程中用Monoid append对结构中元素进行操作。值得注意的是这个f: A => B参数:这个函数是用来在append操作之前先对内部元素进行一次转变(transform):
1 List(1,2,3) foldMap {x => x} //> res18: Int = 6
2 List(1,2,3) foldMap {x => (x + 3).toString} //> res19: String = 456 变成String操作
我们试着用一些实际的例子来示范Monoid的用法。上面提到Monoid在可折叠数据结构里的元素连续处理有着很好的应用,我们先试一个例子:确定一个可折叠数据结构F[A]中的元素A是否排序的:
def ordered(xs: List[Int]): Boolean //判断xs是否按序排列
由于我们必须游览List xs,所以用Monoid对元素Int进行判断操作是可行的方法。我们先设计一个对比数据结构:
Option[(min: Int, max: Int. ordered: Boolean)], 它记录了当前元素的状态,包括最小,最大,是否排序的:
1 /判断xs是否是排序的 2 def ordered(xs: List[Int]): Boolean = { 3 val monoid = new Monoid[Option[(Int,Int,Boolean)]] { //对类型Option[(Int,Int,Boolean)]定义一个Monoid实例
4 def zero = None 5 def append(a1: Option[(Int,Int,Boolean)], a2: => Option[(Int,Int,Boolean)]) = //对连续两个元素进行对比操作
6 (a1,a2) match { 7 case (x,None) => x 8 case (None,x) => x //保留不为None的状态
9 case (Some((min1,max1,ord1)),Some((min2,max2,ord2))) => //如果max1 <= min2状态即为true
10 Some((min1 min min2, max1 max max2, ord1 && ord2 && (max1 <= min2))) //更新min,max和ord
11 } 12 } //我们需要把元素转换成Option((Int,Int,Boolean))
13 (xs.foldMap(i => Option((i, i, true)))(monoid)).map(_._3) getOrElse(true) 14 } //> ordered: (xs: List[Int])Boolean
15
16 ordered(List(1,2,12,34)) //> res21: Boolean = true
17 ordered(List(1,2,34,23)) //> res22: Boolean = false
注意这个i => Option((i,i,true)) 转换(transform)。
由于Monoid是种极简单的类型,所以很容易对Monoid进行组合。Monoid组合产生的结果还是Monoid,并且用起来可以更方便:
1 def productMonoid[A,B](ma: Monoid[A], mb: Monoid[B]): Monoid[(A,B)] = new Monoid[(A,B)] { 2 def zero = (ma.zero, mb.zero) 3 def append(x: (A,B), y: => (A,B)): (A,B) = (ma.append(x._1, y._1), mb.append(x._2, y._2)) 4 } //> productMonoid: [A, B](ma: scalaz.Monoid[A], mb: scalaz.Monoid[B])scalaz.Mon 5 //| oid[(A, B)]
6 val pm = productMonoid(Monoid[Int],Monoid[List[Int]]) 7 //> pm : scalaz.Monoid[(Int, List[Int])] = Exercises.monoid$$anonfun$main$1$$a 8 //| non$3@72d1ad2e
以上的pm就是两个Monoid的组合,结果是一个tuple2Monoid。我们可以使用这个tuple2Monoid对可折叠数据结构中元素进行并行操作。比如我们可以在游览一个List[Int]时同时统计长度(list length)及乘积(product):
1 val intMultMonoid = new Monoid[Int] { 2 def zero = 1
3 def append(a1: Int, a2: => Int): Int = a1 * a2 4 } //> intMultMonoid : scalaz.Monoid[Int] = Exercises.monoid$$anonfun$main$1$$ano 5 //| n$1@6c64cb25
6 def productMonoid[A,B](ma: Monoid[A], mb: Monoid[B]): Monoid[(A,B)] = new Monoid[(A,B)] { 7 def zero = (ma.zero, mb.zero) 8 def append(x: (A,B), y: => (A,B)): (A,B) = (ma.append(x._1, y._1), mb.append(x._2, y._2)) 9 } //> productMonoid: [A, B](ma: scalaz.Monoid[A], mb: scalaz.Monoid[B])scalaz.Mon 10 //| oid[(A, B)]
11 val pm = productMonoid(Monoid[Int @@ Tags.Multiplication],Monoid[Int]) 12 //> pm : scalaz.Monoid[(scalaz.@@[Int,scalaz.Tags.Multiplication], Int)] = Exe 13 //| rcises.monoid$$anonfun$main$1$$anon$3@72d1ad2e
14 List(1,2,3,4,6).foldMap(i => (i, 1))(productMonoid(intMultMonoid,Monoid[Int])) 15 //> res23: (Int, Int) = (144,5)
我们再来一个合并多层map的Monoid:
1 def mapMergeMonoid[K,V](V: Monoid[V]): Monoid[Map[K, |