@MiloXia 2015-07-03T16:28:46.000000Z 字数 19710 阅读 2797

Scala FP 扫盲

scala 函数式编程

fold

List(a, b, c, d)
foldRight: 尾元素d 先于 z 施用op; op(a,op(b,op(c,op(d,z)))); 非尾递归
foldLeft: 头元素a 先于 z 施用op; op(op(op(op(z,a),b),c),d); 尾递归

def foldRight[A, B](l :List[A], z: B)(op: (A, B) => B): B = l match {
    case Nil => z
    case h :: t => op(h, foldRight(t, z)(op))
  }
  def foldLeft[A, B](l :List[A], z: B)(op: (A, B) => B): B = l match {
    case Nil => z
    case h :: t => foldLeft(t, op(h, z))(op)
  }
  println(foldRight(List(1,2,3,4,5), 0)((a, b) => {println(a, b); b + a}))
  println(foldLeft(List(1,2,3,4,5), 0)((a, b) => {println(a, b); b + a}))

(5,0)
(4,5)
(3,9)
(2,12)
(1,14)
15
(1,0)
(2,1)
(3,3)
(4,6)
(5,10)
15

Either

trait Either[+E, +A]

E代表异常类型，A代表计算类型
Left代表无法完成计算, Right 代表计算正常完成

case class Employee(name: String, age: Int, salary: Double)
  def getAge(msg: String, v: Int): Either[String, Int] = if(v <= 18) Left(msg) else Right(v)
  def getName(msg: String, v: String): Either[String, String] = if(v.isEmpty) Left(msg) else Right(v)
  def getSalary(msg: String, v: Double): Either[String, Double] = if(v < 0.0) Left(msg) else Right(v)
  var e1 = for {
    age <- getAge("invalid age", 26).right
    name <- getName("invalid name", "").right
    salary <- getSalary("invalid salary", 10000.0).right
  } yield Employee(name, age, salary)
  println(e1)
  //用map2_s合并错误 monad貌似不行
  def map2_s[A,B,C](a: Either[String, A],b: Either[String, B])(f: (A, B) => C): Either[String, C] = (a, b) match {
    case (Left(e), Left(ee)) => Left(e + "," + ee)
    case (_, Left(e)) => Left(e)
    case (Left(e), _) => Left(e)
    case (Right(a), Right(b)) => Right(f(a, b))
  }
// 编译不过
//  def map3_s[A,B,C,D](a: Either[String, A],b: Either[String, B],c: Either[String, C])(f: (A, B, C) => D): Either[String, D] =
//    map2_s(a, b)((a, b) => map2_s(c, Right(a,b))((ax, bx) => f(bx._1, bx._2, ax)))
 def map3_s[A,B,C,D](a: Either[String, A],b: Either[String, B],c: Either[String, C])(f: (A, B, C) => D): Either[String, D] =
    map2_s(a, map2_s(b, c){(bx, cx) =>
      (bx, cx)
    }){(ax, bcx) => f(ax, bcx._1, bcx._2)}
  val e2 = map2_s(getAge("invalid age", 17), getName("invalid name", ""))((a, b) => map2_s(getSalary("invalid salary", 10000.0), Right(a,b))((ax, bx) => Employee(bx._2, bx._1, ax)))
  val e3 = map3_s(getName("invalid name", ""), getAge("invalid age", 17), getSalary("invalid salary", 10000.0))((a, b, c) => Employee(a, b, c))
  println(e2)
  println(e3)

Left(invalid name)
Left(invalid age,invalid name)
Left(invalid name,invalid age)

lazy evaluation

def pair(x: => Int):(Int, Int) = (x, x)
  println(pair({println("hello");1}))

hello
hello
(1,1)

参数x的类型是 => Int, 代表x参数是non-strict的。(call-by-name)
non-strict参数每次使用时都会重新计算一次。
从内部实现机制来解释:这是因为编译器(compiler)遇到non-strict参数时会把一个指针放到调用堆栈里,而不是惯常的把参数的值放入。
所以每次使用non-strict参数时都会重新计算一下

lazy声明可以解决non- strict参数多次运算问题

def pair2(x: => Int):(Int, Int) = {
    lazy val lx = x
    (lx, lx)
  }
println(pair2({println("hello");1}))

hello
(1,1)

  def inc(i :Int) = i + 1
  def lazyInc(x: => Int) = 1
  def pair3(x: => Int) = inc(x) //x被计算
  def pair4(x: => Int) = lazyInc(inc(x)) //inc(x)不被计算
  println(pair3({println("hello3");1}))
  println(pair4({println("hello4");1}))

hello3
2
1

call-by-name
求职：在使用的地方就会被求职
class构造函数参数不可以是non-strict,所以要lazy必须传函数() => ???

case class Pair(x : => Int, y : => Int) //编译不过
case class Pair(x : () => Int, y : () => Int) {
    def pairF = (x, y)
    def pair = (x(), y())
  }
println(Pair(() => 1, () => 2))
println(Pair(() => 1, () => 2).pairF)
println(Pair(() => 1, () => 2).pair)

Pair(<function0>,<function0>)
(<function0>,<function0>)
(1,2)

Stream

trait Stream[+A]
case object Empty extends Stream[Nothing]
case class Cons[+A](head: () => A, tail: () => Stream[A]) extends Stream[A]

由于Cons不是普通函数而是一个类,不容许延后计算类参数,所以传入的是一个函数 () => ???

trait Stream[+A] {
    def uncons: Option[(A, Stream[A])]
    def isEmpty: Boolean = uncons.isEmpty
    //other
    def toList: List[A] = {
      @annotation.tailrec
      def go(s: Stream[A], acc: List[A]): List[A] = {
        s.uncons match {
          case None => acc
          case Some((h,t)) => go(t,h :: acc)
        }
      }
      go(this, Nil).reverse
    }
    import Stream._
    def take(n: Int): Stream[A] = {
      if ( n == 0 ) empty
      else
        uncons match {
          case None => empty
          case Some((h,t)) => cons({println("take"+h);h},t.take(n-1)) //lazy的 并没真的take 执行uncons时才计算
        }
    }
    def drop(n: Int): Stream[A] = {
      if (n == 0) this
      else {
        uncons match {
          case Some((h,t)) => t.drop(n-1)
          case _ => this
        }
      }
    }
    // lazy的foldRight
    def foldRight[B](z: B)(op: (A, => B) => B): B = { //op第二个参数是=> B，所以t.foldRight(z)(op)就是延迟计算的
       uncons match {
           case None => z
           case Some((h,t)) => op({println("fold"+h);h},t.foldRight(z)(op)) //只要不在op里使用b fold就会结束
       }
    }
    // lazy的exists 满足条件p(a) = true 就结束foldRight
    def exists(p: A => Boolean): Boolean = {
      foldRight(false){(a,b) => p(a) || b } //op = (a,b) => p(a) || b ，当p(a) = true时 b不再传给foldRight
    }
    def forAll(p: A => Boolean): Boolean = {
      foldRight(true){(a,b) => p(a) && b}
    }
    def filter(p: A => Boolean): Stream[A] = {
      foldRight(empty[A]){(h,t) => {println("filter"+h);if(p(h)) cons(h,t) else t}} //该表达式，foldRight会执行到底
    }
    def map[B](p: A => B): Stream[B] = {
      foldRight(empty[B]){(h,t) => cons({println("map"+h);p(h)}, t)}
    }
    def flatMap_1[B](f: A => Stream[B]): Stream[B] = {
      foldRight(empty[B]){(h,t) => f(h) #++ t}
    }
    def append[B >: A](b: Stream[B]): Stream[B] = {
      uncons match {
        case None => b
        case Some((h,t)) => cons(h, t.append(b))
      }
    }
    //append简写
    def #++[B >: A](b: Stream[B]): Stream[B] = append(b)
//    override def toString = s"Stream(${toList.mkString(",")})" //会导致全部计算一遍，这可不好
    override def toString = "Stream(lazy...)"
  }
  object Stream {
    def empty[A]: Stream[A] = new Stream[A] { def uncons = None }
    //采用call-by-name比较好，Cons case class的构造参数会比较难看
    def cons[A](h: => A, t: => Stream[A]): Stream[A] = new Stream[A] {
      def uncons = Some((h, t)) /*!!!!!!此时计算*/
    }
    def apply[A](as: A*): Stream[A] = {
      if (as.isEmpty) empty
      else cons(as.head, apply(as.tail: _*))
    }
  }
  def get1 = {println("hello1");1}
  def get2 = {println("hello2");2}
  def get3 = {println("hello3");3}
  println(Stream(1,2,3) take 2)
  println(Stream(get1,get2,get3) take 2) //打印hello是因为apply 所以Stream只能作为产生器
  println((Stream(1,2,3) take 2).toList)
  println("------")
  println(Stream(1,2,3).foldRight(0)(_+_))
  println(Stream(1,2,3).foldRight(0)((a, b) => a )) //foldRight 是否lazy和op有关 只要不使用b fold就会结束 在第一层a=1时 op(1, b不计算)=>1
  println("------")
  println(Stream(1,2,3).take(2).foldRight(0)(_+_)) //每次foldRight执行uncons时会计算lazy的take
  println(Stream(1,2,3).exists(_ == 2))
  println("------")
  println(Stream(1,2,3).map(_+1).filter(_ % 2 == 0).toList) //只遍历一次

Stream(lazy...)
hello1
hello2
hello3
Stream(lazy...)
take1
take2
List(1, 2)
------
fold1
fold2
fold3
6
fold1
1
------
take1
fold1
take2
fold2
3
fold1
fold2
true
------
fold1
map1
fold2
fold2
filter2
map2
fold3
fold3
filter3
map3
fold4
filter4
List(2, 4)

Infinite Stream 无穷数据流

object Stream {
    ...
    def constant[A](a: A): Stream[A] = cons(a, constant(a))
    def from(n: Int): Stream[Int] = cons(n, from(n+1))
    def fibs: Stream[Int] = {
      def go (prev: Int, cur: Int): Stream[Int] = {
        cons(prev,go(cur,prev + cur))
      }
      go(0,1)
    }
    //我们不断重复的在cons。而cons的参数则是算法的实现结果
    //A为前一个值，S为下一个值
    def unfold[A,S](z: S)(f: S => Option[(A, S)]): Stream[A] = {
      f(z) match {
        case None => empty
        case Some((a,s)) => cons(a, unfold(s)(f))
      }
    }
    def constantByUnfold[A](a: A): Stream[A] = unfold(a)(_ => Some((a,a)))
    def fromByUnfold(s: Int): Stream[Int] = unfold(s)(s => Some(s,s+1))
    def fibsByUnfold: Stream[Int] = unfold((0,1)){ case (a1,a2) => Some((a1, (a2, a1+a2))) }
}
  println(Stream.constant(1).take(5).toList)
  println(Stream.from(5).take(5).toList)
  println(Stream.fibs.take(5).toList)
  println(Stream.constantByUnfold(1).take(5).toList)
  println(Stream.fromByUnfold(5).take(5).toList)
  println(Stream.fibsByUnfold.take(5).toList)

List(1, 1, 1, 1, 1)
List(5, 6, 7, 8, 9)
List(0, 1, 1, 2, 3)
List(1, 1, 1, 1, 1)
List(5, 6, 7, 8, 9)
List(0, 1, 1, 2, 3)

unfold的工作原理模仿了一种状态流转过程：z是一个起始状态，代表的是一个类型的值。然后用户（caller）再提供一个操作函数f。f的款式是：S => Option[(A,S)]，意思是接受一个状态，然后把它转换成一对新的A值和新的状态S，再把它们放入一个Option。如果Option是None的话，这给了用户一个机会去终止运算，让unfold停止递归。

用unfold实现getMore

def getData(s:Int, l:Int) = Option(s"sql...skip=$s limit=$l")
def getMore(skip: Int, limit: Int) = Stream.unfold(skip){
  s => Some(getData(s, limit), s+limit)
}
println(Stream.getMore(0,10).take(3).toList)

List(Some(sql...skip=0 limit=10), Some(sql...skip=10 limit=10), Some(sql...skip=20 limit=10))

State

case class State[S,+A](run: S => (A, S)) {
    import State._
    def flatMap[B](f: A => State[S,B]): State[S,B] = State[S,B] {
      s => {
        val (a, s1) = run(s)
        f(a).run(s1)
      }
    }
    def map[B](f: A => B): State[S,B] = {
      flatMap { a => unit(f(a)) }
//      s => {
//        val (a, s1) = run(s)
//        (f(a),s1)
//      }
    }
    def map2[B,C](sb: State[S,B])(f: (A,B) => C): State[S,C] = {
      //flatMap {a => sb.map { b => f(a,b) }}
      for {
        a <- this
        b <- sb
      } yield f(a,b)
    }
    def map3[B,C,D](sb: State[S,B], sc: State[S,C])(f: (A,B,C) => D): State[S,D] ={
      for {
        a <- this
        b <- sb
        c <- sc
      } yield f(a,b,c)
    }
  }
  object State {
    def unit[S,A](a: A) = State[S,A](s => (a, s))
  }
  type Stack = List[Int]
  def pop = State[Stack, Int]{ case x :: xs => (x, xs) }
  def push(i: Int) = State[Stack, Unit]{ case xs => ((), i :: xs ) }
  def stackRun: State[Stack, Int] = {
    for {
      _ <- push(13)
      a <- pop
      b <- pop
    } yield a + b
  }
  val (a, s) = stackRun.run(List(10,11,12))
  println(a,s)
  case class Acc(bar: Int)
  object Acc {
    def inc(i : Int) = State[Acc, Int]{s => (s.bar, new Acc(s.bar + i))}
    def cut(i : Int) = State[Acc, Int]{s => (s.bar, new Acc(s.bar - i))}
  }
  println(Acc.inc(2).run(Acc(1)))
  println((for {
    i <- Acc.inc(2)
    j <- Acc.cut(1)
  } yield {println(i,j); i + j}) run Acc(0))
  //这样更好
  implicit class AccOp(acc :Acc) {
    def inc(i: Int) = Acc.inc(i).run(acc)._2
    def cut(i: Int) = Acc.cut(i).run(acc)._2
  }
  println(Acc(0).inc(2).cut(1))

(23,List(11, 12))
(1,Acc(3))
(0,2)
(2,Acc(1))
Acc(1)

Par

object Par {
    import java.util.concurrent._
    type Par[A] = ExecutorService => Future[A]
    def run[A](pa: Par[A])(implicit es: ExecutorService): Future[A] = pa(es)
    def unit[A](a: A): Par[A] = es => {
      new Future[A] {
        def get: A = a
        def isDone = true
        def isCancelled = false
        def get(timeOut: Long, timeUnit: TimeUnit): A = get
        def cancel(evenIfRunning: Boolean): Boolean = false
      }
    }
    def fork[A](pa: => Par[A]): Par[A] = es => {
      es.submit[A](new Callable[A] {
        def call: A = run(pa)(es).get
      })
    }
    def async[A](a: => A): Par[A] = fork(unit(a)) //不被计算
    //applicative
    def map2[A,B,C](pa: Par[A], pb: Par[B])(f: (A,B) => C): Par[C] = {
      import TimeUnit.NANOSECONDS
      es => new Future[C] {
        val fa = run(pa)(es) //在这里按pa的定义来确定在那个线程运行。如果pa是fork Par则在非主线程中运行
        val fb = run(pb)(es)
        def get = f(fa.get, fb.get)
        def get(timeOut: Long, timeUnit: TimeUnit) = {
          val start = System.nanoTime
          val a = fa.get
          val end = System.nanoTime
          //fa.get用去了一些时间。剩下给fb.get的timeout值要减去
          val b = fb.get(timeOut - timeUnit.convert(end - start, NANOSECONDS) , timeUnit)
          f(a,b)
        }
        def isDone = fa.isDone && fb.isDone
        def isCancelled = fa.isCancelled && fb.isCancelled
        def cancel(evenIsRunning: Boolean) = fa.cancel(evenIsRunning) || fb.cancel(evenIsRunning)
      }
    }
    //map2 >> map3 时用右结合 map3(a,b,c)(f) = map2(a, map2(b,c)(f))(f)
    def map3[A,B,C,D](pa: Par[A], pb: Par[B], pc: Par[C])(f: (A,B,C) => D): Par[D] = {
      map2(pa,map2(pb,pc){(b,c) => (b,c)}){(a,bc) => {
        val (b,c) = bc
        f(a,b,c)
      }}
    }
    //monad
    def flatMap[A,B](pa: Par[A])(f: A => Par[B]): Par[B] = {
      es => {
        run(f(run(pa)(es).get))(es)
      }
    }
  }
  import java.util.concurrent._
  implicit val es = Executors.newCachedThreadPool()
  val a = Par.unit({println("a "+Thread.currentThread.getName);4+7})
  val b = Par.async({println("b "+Thread.currentThread.getName);2+1})
  println(Par.run(a).get)
  println(Par.run(b).get)
  import Par._
  val r = Par.map2(async({println(Thread.currentThread.getName); 41+2}),
    async({println(Thread.currentThread.getName); 33+4}))
    {(a,b) => {println(Thread.currentThread.getName); a+b}}(es).get
  println(r)
  val r1 = fork { map2(async({println(Thread.currentThread.getName); 41+2}),
    async({println(Thread.currentThread.getName); 33+4}))
  {(a,b) => {println(Thread.currentThread.getName); a+b}}}(es).get
  println(r1)
  es.shutdown()

a main
11
b pool-1-thread-1
3
pool-1-thread-1
pool-1-thread-2
main
80
pool-1-thread-1
pool-1-thread-3
pool-1-thread-2
80

Monad

1、可以使用for-comprehension

2、支持泛函式的循序命令执行流程，即：在高阶类结构内部执行操作流程。flatMap在这里起了关键作用，它确保了流程环节间一个环节的输出值成为另一个环境的输入值

那么我们可不可以说：Monad就是泛函编程中支持泛函方式流程式命令执行的特别编程模式。

Monad是一个高度概括的抽象模型。好像创造Monad的目的是为了抽取各种数据类型的共性组件函数汇集成一套组件库从而避免重复编码。

//Functor
  trait Functor[F[_]] {
    def map[A,B](a: F[A])(f: A => B): F[B]
  }
  object ListFunctor extends Functor[List] {
    def map[A,B](la: List[A])(f: A => B): List[B] = la map f
  }
  object OptionFunctor extends Functor[Option] {
    def map[A,B](oa: Option[A])(f: A => B): Option[B] = oa map f
  }
  println(ListFunctor.map(List(1,2,3)){_ + 10})
  println(OptionFunctor.map(Some(1)){_ + 10})
  //monad
  trait Monad[M[_]] extends Functor[M] {
    def unit[A](a: A): M[A]
    def flatMap[A,B](ma: M[A])(f: A => M[B]): M[B]
    def map[A,B](ma: M[A])(f: A => B): M[B] = {
      flatMap(ma){a => unit(f(a))}
    }
    //Applicative
//    def map2[A,B,C](ma: M[A], mb: M[B])(f: (A,B) => C): M[C] = {
//      flatMap(ma) { a => map(mb){ b => f(a,b) }}
//    }
//    def map2[A,B,C](ma: M[A], mb: M[B])(f: (A,B) => C): M[C] = {
//      flatMap(ma) { a => map(mb){ b => f(a,b) }}
//    }
//    def map3[A,B,C,D](ma: M[A], mb: M[B], mc: M[C])(f: (A,B,C) => D): M[D] = {
//      map2(ma,
//        map2(mb,mc){(b,c) => (b,c)}
//      ){(a,bc) => {
//        val (b,c) = bc
//        f(a,b,c)
//      }}
//    }
//    def map4[A,B,C,D,E](ma: M[A], mb: M[B], mc: M[C], md: M[D])(f: (A,B,C,D) => E): M[E] = {
//      map2(ma,
//        map2(mb,
//          map2(mc,md){(c,d) => (c,d)}
//        ){(b,cd) => (b,cd)}
//      ){(a,bcd) => {
//        val (b,(c,d)) = bcd
//        f(a,b,c,d)
//      }}
//    }
  }
  val listMonad = new Monad[List] {
    def unit[A](a: A) = List(a)
    def flatMap[A,B](la: List[A])(f: A => List[B]): List[B] = {
      la flatMap f
    }
  }
  val optionMonad = new Monad[Option] {
    def unit[A](a: A) = Some(a)
    def flatMap[A,B](oa: Option[A])(f: A => Option[B]): Option[B] = {
      oa flatMap f
    }
  }

Applicative

trait Applicative[F[_]] extends Functor[F] {
    def unit[A](a: A): F[A]
    def map2[A,B,C](fa: F[A], fb: F[B])(f: (A,B) => C): F[C] = {
      apply(fb)(map(fa)(f.curried)) //map(fa)(a => (b => c)) >>> F[A=>B]
    }
    def apply[A,B](fa: F[A])(fab: F[A =>B]): F[B] = { //<*>
      map2(fab,fa)((f,a) => f(a))
    }
    def map[A,B](fa: F[A])(f: A => B): F[B] = {
      map2(unit(f),fa)((f,a) => f(a))
    }
//    def map[A,B](fa: F[A])(f: A => B): F[B] = {
//      apply(fa)(unit(f))
//    }
    //map3(ma,mb,mc)(f) = apply(mc)(apply(mb)(apply(mc)(unit(f.curried))))
    def map3[A,B,C,D](ma: F[A], mb: F[B], mc: F[C])(f: (A,B,C) => D): F[D] = {
      apply(mc)(apply(mb)
        (apply(ma)(unit(f.curried))))
    }
    def map4[A,B,C,D,E](ma: F[A], mb: F[B], mc: F[C],md: F[D])(f: (A,B,C,D) => E): F[E] = {
      apply(md)(apply(mc)
        (apply(mb)
          (apply(ma)(unit(f.curried)))))
    }
  }
  val optionApplicative = new Applicative[Option] {
    def unit[A](a: A) = Option(a)
    override def map2[A,B,C](ma: Option[A], mb: Option[B])(f: (A,B) => C): Option[C] = (ma, mb) match {
      case (Some(a), Some(b)) => Some(f(a, b))
      case _ => None
    }
}
  val s = optionApplicative.apply(Some(1))(Some[Int => Int](_ + 1))
  println(s)
  implicit class OptionApplicativeOp[A](opt1: Option[A]) {
    def apply[B,C](opt2: Option[A => B]): Option[B] =
      optionApplicative.map2(opt1, opt2)((opt1x, opt2f) => opt2f(opt1x))
    def apply2[B,C](opt2: Option[(A, B) => C]): Option[B => C] =
      optionApplicative.map2(opt1, opt2)((opt1x, opt2f) => opt2f(opt1x, _))
  }
  def inc(x :Int) = x + 1
  def add2(x: Int, y: Int) = x + y
  def add3(x: Int, y: Int, z: Int) = x + y + z
  val s2 = Some(1) apply Some(inc _)
  println(s2)
  val s3 = optionApplicative.map3(Some(1), Some(2), Some(3))(add3)
  println(s3)
  val s4 = Some(1) apply (Some(2) apply2 Some(add2 _))
  println(s4)

Some(2)
Some(2)
Some(6)
Some(3)

更像Haskell的方式

implicit class OptionApplicativeOp1[A,B](opt1: Option[A => B]) {
    def apply(opt2: Option[A]): Option[B] =
      optionApplicative.map2(opt2, opt1)((opt2x, opt1f) => opt1f(opt2x))
  }
  implicit class OptionApplicativeOp2[A,B,C](opt1: Option[(A, B) => C]) {
    def apply(opt2: Option[A]): Option[B => C] =
      optionApplicative.map2(opt2, opt1)((opt2x, opt1f) => opt1f(opt2x, _))
  }
  val s5 = Some(add2 _) apply Some(2) apply Some(1)

Applicative与Monad差别

flatMap和map2的差别，这也代表着Monad和Applicative在行为上的区别

def apply[A,B](ma: Option[A])(f: Option[A => B]): Option[B] = {
      (ma,f) match {
          case (Some(a),Some(f)) => Some(f(a))
          case _ => None
      }
  }
  def flatMap[A,B](ma: Option[A])(f: A => Option[B]): Option[B] = {
      ma match {
          case Some(a) => f(a)
          case _ => None
      }

apply和map的运算都依赖于两个传入参数的状态：只有两个参数都是Some时才会在Some结构内部进行运算。而flatMap的传入函数A=>Option[B]是否运行则依赖于ma状态是否Some，而传入函数运行的结果又依赖于ma内元素A的值。

所以Applicative可以保持运算结果的结构不变，而Monad有可能会造成运算结果的结构变化。

Monad extends Applicative

trait Monad[M[_]] extends Applicative[M]{
  def unit[A](a: A): M[A]
  def flatMap[A,B](ma: M[A])(f: A => M[B]): M[B] = {
      join(map(ma)(f))
  }
  def compose[A,B,C](f: A => M[B], g: B => M[C]): A => M[C] = {
      a => { flatMap(f(a))(g)}
  }
  def join[A](mma: M[M[A]]): M[A] = {
      flatMap(mma)(ma => ma)
  }
   override def apply[A,B](ma: M[A])(fab: M[A => B]): M[B] = {
      flatMap(fab)(f => flatMap(ma)(a => unit(f(a))))
  }
}

apply和map2一样可由flatMap实现
这样所有Monad都可以是Applicative。但是，有些Applicative未必是Monad，因为我们可能无法用某些类型Applicative实例的map2或apply来实现flatMap、join、compose。

Monad Transformer

不同的Functor是可以组合得到F[G[A]]的

 def compose[F[_],G[_]](m: Functor[F], n: Functor[G]) =
      new Functor[({type l[x] = F[G[x]]})#l] { //呵呵
          override def map[A,B](fga: F[G[A]])(f: A => B) = {
              m.map(fga)(ga => n.map(ga)(f))
          }
      }
val fg = compose(listFunctor,optionFunctor)
fg.map(List(Option("abc"),Option("xy"),Option("ryuiyty"))){ _.length }

但是Monad不可以
Monad Transformer可以实现多个Monad效果的累加（stacking effect）

trait Functor[F[_]] {
    def map[A,B](a: F[A])(f: A => B): F[B]
  }
  trait Monad[M[_]] extends Functor[M] {
    def unit[A](a: A): M[A]
    def flatMap[A, B](ma: M[A])(f: A => M[B]): M[B]
    def map[A, B](ma: M[A])(f: A => B): M[B] = {
      flatMap(ma) { a => unit(f(a))}
    }
  }
  implicit val listMonad = new Monad[List] {
    def unit[A](a: A) = List(a)
    def flatMap[A,B](la: List[A])(f: A => List[B]): List[B] = {
      la flatMap f
    }
  }
  case class OptionT[M[_] : Monad,A](run: M[Option[A]]) {
    def map[B](f: A => B): OptionT[M,B] = {
      val m = implicitly[Functor[M]]
      OptionT[M,B](m.map(run)(a => a.map(f)))
    }
    def flatMap[B](f: A => OptionT[M,B]): OptionT[M,B] = {
      val m = implicitly[Monad[M]]
      OptionT[M,B](m.flatMap(run) {
        case Some(a) => f(a).run
        case None => m.unit(None)
      })
    }
  }
// 编译不过的 Some[List[]] 无法组合
//  val c = for {
//    a <- Some(1)
//    b <- List(1,2,3)
//  } yield a + b
//  println(c)
  val c = for {
    a <- OptionT[List, Int](List(Some(1)))
    b <- OptionT[List, Int](List(Some(1), Some(2), Some(3)))
  } yield a + b
  println(c)

OptionT(List(Some(2), Some(3), Some(4)))

OptineT的签名OptionT[M[ _ ] : Monad, A] 和Option[A]比多了个M[ _ ] 的Monad 代表Option主导的Monad栈
StateT的签名为StateT[M[ _ ] : Monad, S, A] 比State[S,A]也是多了个M

这是Monad Transformer的通用模式
1. 类型变为Monad[A] >>> MonadT[M[ _ ] : Monad, A]
2. map则改为先调用M[ _ ] : Monad的map和faltMap再调用Monad[A]自己的map（Functor的组合）
3. flatMap则调用M[ _ ] : Monad的flatMap,然后自己解Monad[A]得到a后执行f(a).run返回M[Monad[A]]，千万不要调用Monad自己的flatMap，因为这样两个Monad是组合不起来的（flatMap套flatMap）其实就是只保留M的flatMap调用，自己解Monad[A]得A再返回M[Monad[A]]
4. MonadT也是个Monad可继续组合下去

//XMonad的Monad Transformer 通用模式
case class XMonadT[M[_] : Monad,A](run: M[XMonad[A]]) {
    def map[B](f: A => B): XMonadT[M,B] = {
      val m = implicitly[Functor[M]]
      XMonadT[M,B](m.map(run)(a => a.map(f))) //map再map是functor组合，返回M[XMonad[A]]
    }
    def flatMap[B](f: A => XMonadT[M,B]): OptionT[M,B] = {
      val m = implicitly[Monad[M]]
      XMonadT[M,B](m.flatMap(run) { a =>
        f(a.get).run //解开a 返回M[XMonad[A]] 这里是关键
      })
    }
  }

Trampoline (Stackless Scala)

trait Trampoline[+A] {
    final def runT: A = resume match {
      case Right(a) => a
      case Left(k) => k().runT
    }
    def flatMap[B](f: A => Trampoline[B]): Trampoline[B] = {
      this match {
        //          case Done(a) => f(a)
        //          case More(k) => f(runT)
        case FlatMap(a,g) => FlatMap(a, (x: Any) => g(x) flatMap f)
        case x => FlatMap(x, f)
      }
    }
    def map[B](f: A => B) = flatMap(a => Done(f(a)))
    def resume: Either[() => Trampoline[A], A] = this match {
      case Done(a) => Right(a)
      case More(k) => Left(k)
      case FlatMap(a,f) => a match {
        case Done(v) => f(v).resume
        case More(k) => Left(() => k() flatMap f)
        case FlatMap(b,g) => FlatMap(b, (x: Any) => g(x) flatMap f).resume
      }
    }
  }
  case class Done[+A](a: A) extends Trampoline[A]
  case class More[+A](k: () => Trampoline[A]) extends Trampoline[A]
  case class FlatMap[A,B](sub: Trampoline[A], k: A => Trampoline[B]) extends Trampoline[B]
  def foldRight[A, B](l :List[A], z: B)(op: (A, B) => B): B = l match {
    case Nil => z
    case h :: t => op(h, foldRight(t, z)(op))
  }
//  println(foldRight((1 to 10000).toList, 0)(_+_)) //stackoverflow
  def foldRight2[A, B](l :List[A], z: B)(op: (A, B) => B): Trampoline[B] = l match {
    case Nil => Done(z)
    case h :: t => More(() => {
      foldRight2(t, z)(op) flatMap {
        a => More(() => Done(op(h, a)))
      }
    })
  }
  println(foldRight2((1 to 10000).toList, 0)((a,b) => {println(a,b);a+b}).runT)

Free Monad

trait Interact[A] //交互数据类型
  //提问，等待返回String类型答案
  case class Ask(prompt: String) extends Interact[String]
  //告知，有没有返回结果
  case class Tell(msg: String) extends Interact[Unit]
  //Tell依赖Ask的结果 这么写编译不过 不是monad
//  for {
//    x <- Ask("What's your first name?")
//    y <- Ask("What's your last name?")
//    _ <- Tell(s"Hello $y $x!")
//  } yield ()
  trait Free[F[_],A] {
    //Monad
    def unit(a: A) = Return(a)
    def flatMap[B](f: A => Free[F,B]): Free[F,B] = this match {
      case Return(a) => f(a)
      case Bind(fa,g) => Bind(fa, (x: Any) => g(x) flatMap f)
      //case Bind(fa,g) => Bind(fa, g andThen (_ flatMap f))
    }
    def map[B](f: A => B): Free[F,B] = flatMap(a => Return(f(a)))
    //Interpreter
    //可以用折叠算法来实现F[_]结构中表达式的转换
    def foldMap[G[_]: Monad](f: F ~> G): G[A] = this match {
      case Return(a) => implicitly[Monad[G]].unit(a)
      case Bind(b,g) => implicitly[Monad[G]].flatMap(f(b))(a => g(a).foldMap(f))
    }
  }
  case class Return[F[_],A](a: A) extends Free[F,A] //表示计算结束
  case class Bind[F[_],I,A](a: F[I], f: I => Free[F,A]) extends Free[F,A] //表示依赖计算 或者延续计算
  implicit def lift[F[_],A](fa: F[A]): Free[F,A] = Bind(fa, (a: A) => Return(a))
  val prg = for {
    x <- Ask("What's your first name?")
    y <- Ask("What's your last name?")
    _ <- Tell(s"Hello $y $x!")
  } yield ()
  println(prg) //返回Monad 紧紧描述算法而已
//  Bind(Ask("What's your first name?"), (a: String) => Return(a)) //fa , g
//  _ => Bind(Ask("What's your last name?"), (a: String) => Return(a))
//  Bind(Ask("What's your first name?"), (a: Any) => Bind(Ask("What's your last name?"), (a: String) => Return(a)))
//  _ => Bind(Tell(s"Hello $y $x!"), (a: Unit) => Return(a))
//
//  Bind(Ask("What's your first name?"), (a: Any) => Bind(Ask("What's your last name?"), (a: String) => Return(a)))
  //Free Monad 分为Monad和Interpreter 是算法和运算分离的
  //Interpreter解译程序形成针对特定运行环境的可运行代码
  //Interpreter程序运算是通过一个转换函数实现的。这个函数把F[_]这样一个算法解译成G[_]这样一个针对可运行环境的Monad运行代码。这种转换就是自然转换（Natural Transformation）
  trait ~>[F[_],G[_]] {
    def apply[A](fa: F[A]): G[A]
  }
  type Id[A] = A
  implicit val idMonad: Monad[Id] = new Monad[Id] {
    def unit[A](a: A) = a
    def flatMap[A,B](fa: A)(f: A => B): B = f(fa)
  }
  object Console extends (Interact ~> Id) { //Interact ~> Id的实现
    def apply[A](i: Interact[A]): A = i match {
      case Ask(prompt) => {
        println(prompt)
        readLine
      }
      case Tell(msg) => println(msg)
    }
  }
  prg.foldMap(Console)