day 4里面粗看了typeclass law以及一些Monoid。今天就到了Monads

A Fistful of Monads

Monads are a natural extension applicative functors, and they provide a solution to the following problem: If we have a value with context, m a, how do we apply it to a function that takes a normal a and returns a value with a context.

Scalaz提供了Monad。(Oh, the M word, Scala)。

1
2
3
trait Monad[F[_]] extends Applicative[F] with Bind[F] { self =>
...
}

它继承了ApplicativeBind。我们先看看Bind

Bind

Bind的代码是这样的。

1
2
3
4
5
6
trait Bind[F[_]] extends Apply[F] { self =>

/** Equivalent to `join(map(fa)(f))`. */
def bind[A, B](fa: F[A])(f: A => F[B]): F[B]
...
}

以及注入的操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
final class BindOps[F[_],A] private[syntax](val self: F[A])
(implicit val F: Bind[F]) extends Ops[F[A]] {
////
import Liskov.<~<, Leibniz.===

def flatMap[B](f: A => F[B]) = F.bind(self)(f)

def >>=[B](f: A => F[B]) = F.bind(self)(f)

def [B](f: A => F[B]) = F.bind(self)(f)

def join[B](implicit ev: A <~< F[B]): F[B] = F.bind(self)(ev(_))

def μ[B](implicit ev: A <~< F[B]): F[B] = F.bind(self)(ev(_))

def >>[B](b: => F[B]): F[B] = F.bind(self)(_ => b)

def >>![B](f: A => F[B]): F[A] = F.bind(self)(a => F.map(f(a))(_ => a))

def ifM[B](ifTrue: => F[B], ifFalse: => F[B])(implicit ev: A === Boolean): F[B] = {
val value: F[Boolean] = ev.subst(self)
F.ifM(value, ifTrue, ifFalse)
}

def mproduct[B](f: A => F[B]) = F.mproduct(self)(f)

////
}

它引入了flatMap以及>>=等操作。可以看出来其实flatMap就是bind操作。

1
2
3.some flatMap { x => (x + 1).some} // Some(4)
(none: Option[Int]) >>= { x => (x + 1).some // None

Monad

由于Scalaz里面的Monad是直接继承自Applicative,所以这里不区分return以及pure,可以直接使用point

1
2
9.some >>= { x => Monad[Option].point(x * 10)} // Some(90)
(none: Option[Int]) >>= { x => Monad[Option].point(x * 10)} // None

Walk the line

看一个例子

Let’s say that [Pierre] keeps his balance if the number of birds on the left side of the pole and on the right side of the pole is within three. So if there’s one bird on the right side and four birds on the left side, he’s okay. But if a fifth bird lands on the left side, then he loses his balance and takes a dive.

我们通过Option包裹Pole

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import scalaz._
import Scalaz._

type Birds = Int

case class Pole(left: Birds, right: Birds) {

def landLeft(n: Birds): Option[Pole] =
if (math.abs((left + n) - right) < 4)
copy(left = left + n).some
else none
def landRight(n: Birds): Option[Pole] =
if (math.abs(left - (right + n)) < 4)
copy(right = right + n).some
else none
}

想用它的时候,

1
2
3
4
5
6
7
8
9
10
Monad[Option].point(Pole(0, 0)) >>= 
{ _.landLeft(2) } >>= { _.landLeft(2)
// res0: Option[Pole] = Some(Pole(1,0))

Monad[Option].point(Pole(0, 0)) >>=
{_.landLeft(1)} >>=
{_.landRight(4)} >>=
{_.landLeft(-1)} >>=
{_.landRight(-2)}
// res1: Option[Pole] = None
Banana on wire

We may also devise a function that ignores the current number of birds on the balancing pole and just makes Pierre slip and fall. We can call it banana.

我们可能会需要一个总是通往失败的函数,

1
2
3
4
5
6
7
8
9
10
11
case class Pole(left: Birds, right: Birds) {

def landLeft(n: Birds): Option[Pole] =
if (math.abs((left + n) - right) < 4)
copy(left = left + n).some
else none
def landRight(n: Birds): Option[Pole] =
if (math.abs(left - (right + n)) < 4)
copy(right = right + n).some
else none
}

我们还有函数>>,忽视前一个正常的结果,直接返回下一个(如果你怀疑这个有什么用,想想之前的parser)。

如果我们想直接使用一下的话

1
2
3
4
Monad[Option].point(Pole(0, 0)) >>= 
{_.landLeft(1)} >>
(none: Option[Pole]) >>=
{_.landRight(1)}

就会报错。类型推断并没有正常的发挥作用。这是由于操作符优先级的问题,在Scala中,以=结尾的运算符,除已经用于比较大小的运算符如>=外,优先级等价于赋值号,比其他任何符号的优先级都低,所以这种时候要加括号,或者直接当成函数调用。

1
2
Monad[Option].point(Pole(0, 0)).>>=(
{_.landLeft(1)}).>>(none: Option[Pole]).>>=({_.landRight(1)})
for syntax

Haskell中,Monad有一个明显的好处,就是可以直接使用do这种语法糖。而在Scala中,使用的是for语句。

1
2
3
4
5
6
7
8
9
10
// 当由于有太多的lambda嵌套,显得很乱的时候
3.some >>=
{ x => (none: Option[String]) >>=
{ y => (x.shows + y).some } }

// 改写为for
for {
x <- 3.some
y <- none: Option[String]
} yield x.shows + y

而且,我们避免了显式的在结果中构造Option的过程。

Pierre returns

我们将之前的内容改写成for

1
2
3
4
5
6
for {
start <- Monad[Option].point(Pole(0, 0))
first <- start.landLeft(1)
second <- first.landRight(2)
third <- second.landLeft(1)
} yield third

如果我们丢一个banana,让他总是失败

1
2
3
4
5
6
7
for {
start <- Monad[Option].point(Pole(0, 0))
first <- start.landLeft(1)
_ <- (none: Option[Pole])
second <- first.landRight(2)
third <- second.landLeft(1)
} yield third

一开始可能会感觉困惑,为什么从none取出来的值直接用_,也就是我们不关心它的值,还要把它写出来,其实把这段代码用flatMap展开,就会比较明显。

1
2
3
4
5
6
7
Monad[Option].point(Pole(0, 0)).flatMap(start => {
start.landLeft(1).flatMap(first => {
first.banana.flatMap(second => {
first.landRight(2)
})
})
})

这里使用了banana,其实我们要的是none的作用,可以说Monad包裹了副作用。

Pattern matching and failure

同样,我们在for表达式里面也可以使用Pattern matching,不过,在匹配失败的时候,会直接调用Monadfail函数,从而产生一个failure in the context of the current monad,避免程序的崩溃。

1
2
3
4
5
for {
(x :: xs) <- "".toList.some
} yield x

// res0: Option[Char] = None

List Monad

On the other hand, a value like [3,8,9] contains several results, so we can view it as one value that is actually many values at the same time. Using lists as applicative functors showcases this non-determinism nicely.

List可以看做用来描述non-determinismMonad

比如函数会返回不定个数的结果。

1
2
List(3, 4, 5) >>= {x => List(x, -x)}
// res0: List[Int] = List(3, -3, 4, -4, 5, -5)

所以,可以用List表示可能返回多个解的值。而在scalaz里面使用也很简单。

1
2
3
4
5
6

for {
n <- List(1, 2)
ch <- List('a', 'b')
} yield (n, ch)
// res1: List[(Int, Char)] = List((1,a), (1,b), (2,a), (2,b))

MonadPlus and the guard function

scalafor可以添加filtering

1
2
3
4
for {
x <- (1 |-> 50) if x.shows contains "7"
} yield x
// res0: List[Int] = List(7, 17, 27, 37, 47)

The MonadPlus type class is for monads that can also act as monoids.

Scalaz中的MonadPlus

1
2
3
4
5
6
7
8
9
10
11
trait MonadPlus[F[_]] extends Monad[F] with ApplicativePlus[F] { self =>
////

/** Remove `f`-failing `A`s in `fa`, by which we mean: in the
* expression `filter(filter(fa)(f))(g)`, `g` will never be invoked
* for any `a` where `f(a)` returns false.
*/

def filter[A](fa: F[A])(f: A => Boolean) =
bind(fa)(a => if (f(a)) point(a) else empty[A])
...
}

Plus, PlusEmpty, and ApplicativePlus

转而去看ApplicativePlus,

1
2
3
trait ApplicativePlus[F[_]] extends Applicative[F] with PlusEmpty[F] { self =>
...
}

他继承自PlusEmpty

1
2
3
4
5
trait PlusEmpty[F[_]] extends Plus[F] { self =>
////
def empty[A]: F[A]
...
}

再去看Plus

1
2
3
4
trait Plus[F[_]]  { self =>
////
def plus[A](a: F[A], b: => F[A]): F[A]
}

Semigroup[A]以及Monoid[A]相似,Plus[F[_]]以及PlusEmpty[F[_]]需要去实现plus以及empty,但是是在F[_]这个类型构造器的层次上。

Plus引入了<+>去连接两个containers

1
2
List(1,2,3) <+> List(4, 5, 6)
// res0: List[Int] = List(1, 2, 3, 4, 5, 6)

然后通过MonadPlus引入了filter操作

1
(1 |-> 50) filter { x => x.shows contains '7' }

A knight’s quest

再看个例子,

Here’s a problem that really lends itself to being solved with non-determinism. Say you have a chess board and only one knight piece on it. We want to find out if the knight can reach a certain position in three moves.

先定义个棋子

1
2
3
4
5
6
7
8
9
10
case class KnightPos(c: Int, r: Int) {
def move: List[KnightPos] =
for {
KnightPos(c2, r2) <- List(KnightPos(c + 2, r - 1), KnightPos(c + 2, r + 1),
KnightPos(c - 2, r - 1), KnightPos(c - 2, r + 1),
KnightPos(c + 1, r - 2), KnightPos(c + 1, r + 2),
KnightPos(c - 1, r - 2), KnightPos(c - 1, r + 2))
if ((1 |-> 8) contains c2) && ((1 |-> 8) contains r2)
} yield KnightPos(c2, r2)
}

然后试用一下

1
2
KnightPos(8, 2).move
// res0: List[KnightPos] = List(KnightPos(6,1), KnightPos(6,3), KnightPos(7,4))

然后加入走三步以及判断的功能

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
case class KnightPos(c: Int, r: Int) {
def move: List[KnightPos] =
for {
KnightPos(c2, r2) <- List(KnightPos(c + 2, r - 1), KnightPos(c + 2, r + 1),
KnightPos(c - 2, r - 1), KnightPos(c - 2, r + 1),
KnightPos(c + 1, r - 2), KnightPos(c + 1, r + 2),
KnightPos(c - 1, r - 2), KnightPos(c - 1, r + 2))
if ((1 |-> 8) element c2) && ((1 |-> 8) contains r2)
} yield KnightPos(c2, r2)
def in3: List[KnightPos] =
for {
first <- move
second <- first.move
third <- second.move
} yield third
def canReachIn3(end: KnightPos): Boolean = in3 contains end
}

然后试一下

1
2
3
4
KnightPos(6, 2) canReachIn3 KnightPos(6, 1)
// res0: Boolean = true
KnightPos(6, 2) canReachIn3 KnightPos(7, 6)
// res1: Boolean = false

Monad Laws

Monad也像functor等一样,Monad Laws有着重要的地位。

Left identity

if we take a value, put it in a default context with return and then feed it to a function by using >>=, it’s the same as just taking the value and applying the function to it.

1
2
(Monad[Option].point(3) >>= 
{ x => (x + 100000).some }) assert_=== 3 |> { x => (x + 100000).some }

Right identity

if we have a monadic value and we use >>= to feed it to return, the result is our original monadic value.

1
("move on up".some flatMap {Monad[Option].point(_)}) assert_=== "move on up".some

Associativity

when we have a chain of monadic function applications with >>=, it shouldn’t matter how they’re nested.

1
2
3
4
5
6
7
8
9
10
11
Monad[Option].point(Pole(0, 0)) >>= 
{_.landRight(2)} >>=
{_.landLeft(2)} >>= {_.landRight(2)}
// res0: Option[Pole] = Some(Pole(2,4))

Monad[Option].point(Pole(0, 0)) >>= { x =>
x.landRight(2) >>= { y =>
y.landLeft(2) >>= { z =>
z.landRight(2)
}}}
// res1: Option[Pole] = Some(Pole(2,4))

Scalaz里面,这样描述这些Law

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
trait MonadLaw extends ApplicativeLaw with BindLaw {
/** Lifted `point` is a no-op. */
def rightIdentity[A](a: F[A])(implicit FA: Equal[F[A]]): Boolean =
FA.equal(bind(a)(point(_: A)), a)
/** Lifted `f` applied to pure `a` is just `f(a)`. */
def leftIdentity[A, B](a: A, f: A => F[B])
(implicit FB: Equal[F[B]]): Boolean =
FB.equal(bind(point(a))(f), f(a))
// associative law in Bind
/**
* As with semigroups, monadic effects only change when their
* order is changed, not when the order in which they're
* combined changes.
*/

def associativeBind[A, B, C](fa: F[A], f: A => F[B], g: B => F[C])
(implicit FC: Equal[F[C]]): Boolean =
FC.equal(bind(bind(fa)(f))(g), bind(fa)((a: A) => bind(f(a))(g)))
}



X