FP in scala 勉強メモ [PartⅠ 第4章 例外を使わないエラー処理] ref: http://qiita.com/ma2k8/items/64d25b90d83406dfa53d

file0.txt

// Q
リスト4ｰ4のすべての関数をOptionで実装せよ。
各関数を実装するときに、その関数の意味と、それを使用するであろう状況について考えること。
どの関数をいつ使用するかについては、後ほど考察する。
ヒントは以下のとおり。
 - パターンマッチングを使用しても構わないが、
　  mapとgetOrElseを除く関数はすべてパターンマッチングに頼らなくても実装できるはずである。
 -  map,flatMapの実装は、過多シグネチャの情報に基づいて充分に決定できるはずである。
 -  getOrElseはOptionがNoneのバアアイは、指定されたデフォルト値を返す。
 -  orElseは、1つ目のOptionが定義されている場合はそれを返し、そうでない場合は2つ目のOptionを返す。

// answer
  def map[B](f: A => B): Option[B] = this match {
    case None => None
    case Some(x) => Some(f(x))
  }

 def getOrElse[B>:A](default: => B): B = this match {
    case None => default
    case Some(x) => x  
  }

 def flatMap[B](f: A => Option[B]): Option[B] = map(f).getOrElse(None)

 def orElse[B>:A](ob: => Option[B]): Option[B] = this match {
    case None => ob
    case Some(x) => Some(x)  
  }

  def filter(f: A => Boolean): Option[A] = this match {
    case Some(x) if f(x) => Some(x)
    case None => None
  }

// 公式のanswer
 def map[B](f: A => B): Option[B] = this match {
    case None => None
    case Some(a) => Some(f(a))
  }

  def getOrElse[B>:A](default: => B): B = this match {
    case None => default
    case Some(a) => a
  }

  def flatMap[B](f: A => Option[B]): Option[B] =
    map(f) getOrElse None

  /*
  Of course, we can also implement `flatMap` with explicit pattern matching.
  */
  def flatMap_1[B](f: A => Option[B]): Option[B] = this match {
    case None => None
    case Some(a) => f(a)
  }

  def orElse[B>:A](ob: => Option[B]) =
    this map (Some(_)) getOrElse ob

  /*
  Again, we can implement this with explicit pattern matching.
  */
  def orElse_1[B>:A](ob: => Option[B]): Option[B] = this match {
    case None => ob
    case _ => this
  }

  def filter(f: A => Boolean): Option[A] = this match {
    case Some(a) if f(a) => this
    case _ => None
  }
  /*
  This can also be defined in terms of `flatMap`.
  */
  def filter_1(f: A => Boolean): Option[A] =
    flatMap(a => if (f(a)) Some(a) else None)

file1.txt

// Q
flatMapをベースとしてvariance関数を実装せよ。
シーケンスの平均をm、シーケンスの各要素をxとすれば、分散はmath.pow(x - m, 2)の平均となる。
def variance(xs: Seq[Double]): Option[Double]

// answer


// 公式のanswer
  def mean(xs: Seq[Double]): Option[Double] =
    if (xs.isEmpty) None
    else Some(xs.sum / xs.length)

  def variance(xs: Seq[Double]): Option[Double] =
    mean(xs) flatMap (m => mean(xs.map(x => math.pow(x - m, 2))))

file2.txt

// Q
2項関数を使って、Option型の2つの値を結合する総称関数map2を記述せよ。
どちらかのOption値がNoneの場合は、戻り値もNoneになる。
シグネチャは以下のとおり。
def map2[A,B,C](a: Option[A], b: Option[B])(f: (A, B) => C): Option[C]

// answer
  def map2[A,B,C](a: Option[A], b: Option[B])(f: (A, B) => C): Option[C] = (a,b) match {
    case (Some(x), Some(y)) => Some(f(x,y))
    case _ => None
  }

// 公式のanswer
def map2[A,B,C](a: Option[A], b: Option[B])(f: (A, B) => C): Option[C] =
    a flatMap (aa => b map (bb => f(aa, bb)))

file3.txt

// Q
Optionのリストを1つのOptionにまとめるsequence関数を記述せよ。
新しいOptionには、元のリストに含まれているすべてのSome値のリストが含まれる。
元のリストにNoneが1つでも含まれていた場合、この関数の結果はNoneになる。
それ以外の場合は、すべての値のリストを含んだSomeになる。シグネチャは以下のとおり。
def sequence[A](a: List[Option[A]]): Option[List[A]]

// answer
 def sequence[A](a: List[Option[A]]): Option[List[A]] = {
    @annotation.tailrec
    def loop(l: List[Option[A]], x: Option[List[A]]): Option[List[A]] = {
      l match {
        case Some(h) :: List() => x.map(h :: _)
        case Some(h) :: t => loop(t, x.map(h :: _))
        case None :: _ => None
        case _ => println("_"); None
      }
    }
    loop(a, Some(List())).map(_.reverse)
  }

// 公式のanswer
  def sequence[A](a: List[Option[A]]): Option[List[A]] =
    a match {
      case Nil => Some(Nil)
      case h :: t => h flatMap (hh => sequence(t) map (hh :: _))
    }
  /*
  It can also be implemented using `foldRight` and `map2`. The type annotation on `foldRight` is needed here; otherwise
  Scala wrongly infers the result type of the fold as `Some[Nil.type]` and reports a type error (try it!). This is an
  unfortunate consequence of Scala using subtyping to encode algebraic data types.
  */
  def sequence_1[A](a: List[Option[A]]): Option[List[A]] =
    a.foldRight[Option[List[A]]](Some(Nil))((x,y) => map2(x,y)(_ :: _))

file4.txt

// Q
traverse関数を実装せよ。mapとsequenceを利用すれば簡単だが、リストを1回だけ調べる、より効率のよい実装にすること。
要するに、traverseの観点からsequenceを実装すれば良い。

// answer
  def traverse[E,B,C](a: List[A])(f: A => Either[E,B]): Either[E,List[B]] =
    a match {
      case Nil => Right(Nil)
      case h :: t => (f(h) map2 traverse(t)(f))(_ :: _) 
  }

// 公式のanswer
  def traverse[E,A,B](es: List[A])(f: A => Either[E, B]): Either[E, List[B]] = 
    es match {
      case Nil => Right(Nil)
      case h::t => (f(h) map2 traverse(t)(f))(_ :: _)
    }

  def traverse_1[E,A,B](es: List[A])(f: A => Either[E, B]): Either[E, List[B]] = 
    es.foldRight[Either[E,List[B]]](Right(Nil))((a, b) => f(a).map2(b)(_ :: _))

file5.txt

// Q
Right値を操作するmap,flatMap,orElse,map2をEitherに追加せよ。
trait Either[+E,+A] {
 def map[B](f: A => B): Either[E, B] = sys.error("todo")

 def flatMap[EE >: E, B](f: A => Either[EE, B]): Either[EE, B] = sys.error("todo")

 def orElse[EE >: E, B >: A](b: => Either[EE, B]): Either[EE, B] = sys.error("todo")

 def map2[EE >: E, B, C](b: Either[EE, B])(f: (A, B) => C): Either[EE, C] = sys.error("todo")
}
// answer
 trait Either[+E, +A] {
  def map[B](f: A => B): Either[E, B] = this match {
    case Right(x) => Right(f(x))
    case Left(e) => Left(e)
  }

  def flatMap[EE >: E, B](f: A => Either[EE, B]): Either[EE, B] = this match {
    case Right(x) => f(x)
    case Left(e) => Left(e)
  }


  def orElse[EE >: E, B >: A](b: => Either[EE, B]): Either[EE, B] = this match {
    case Right(x) => this
    case Left(e) => b
  }

  def map2[EE >: E, B, C](b: Either[EE, B])(f: (A, B) => C): Either[EE, C] = for { x <- this; y <- b } yield f(x,y)

}
// 公式のanswer
sealed trait Either[+E,+A] {
 def map[B](f: A => B): Either[E, B] = 
   this match {
     case Right(a) => Right(f(a))
     case Left(e) => Left(e)
   }

 def flatMap[EE >: E, B](f: A => Either[EE, B]): Either[EE, B] =
   this match {
     case Left(e) => Left(e)
     case Right(a) => f(a)
   }
 def orElse[EE >: E, AA >: A](b: => Either[EE, AA]): Either[EE, AA] =
   this match {
     case Left(_) => b
     case Right(a) => Right(a)
   }
 def map2[EE >: E, B, C](b: Either[EE, B])(f: (A, B) => C): 
   Either[EE, C] = for { a <- this; b1 <- b } yield f(a,b1)
}

file6.txt

// Q
Eitherでsequenceとtraverseを実装せよ。
これらは、エラーが発生した場合に、最初に検出されたエラーを返すものとする。

def sequence[E,A](es: List[Either[E,A]]): Either[E,List[A]]
def traverse[E,A,B](as: List[A])(f: A => Either[E,B]): Either[E,List[B]]

// answer
  def traverse[E, A, B](es: List[A])(f: A => Either[E, B]): Either[E, List[B]] =
    es match {
      case Nil => Right(Nil)
      case h :: t => (f(h) map2 traverse(t)(f))(_ :: _)
    }

  def sequence[E, A](es: List[Either[E, A]]): Either[E, List[A]] =
    es match {
      case Nil => Right(Nil)
      case Left(h) :: _  => Left(h)
      case h :: t => h flatMap (hh => sequence(t) map (hh :: _))
    }

// 公式のanswer
  def traverse[E,A,B](es: List[A])(f: A => Either[E, B]): Either[E, List[B]] = 
    es match {
      case Nil => Right(Nil)
      case h::t => (f(h) map2 traverse(t)(f))(_ :: _)
    }

  def traverse_1[E,A,B](es: List[A])(f: A => Either[E, B]): Either[E, List[B]] = 
    es.foldRight[Either[E,List[B]]](Right(Nil))((a, b) => f(a).map2(b)(_ :: _))

  def sequence[E,A](es: List[Either[E,A]]): Either[E,List[A]] = 
    traverse(es)(x => x)

file7.txt

// Q
リスト4-10の実装では、名前と年齢が両方とも無効であったとしても、map2はエラーを1つしか報告できない。
両方のエラーを報告するには、何を変更する必要があるか。
map2を変更するのか、それともmkPersonのシグネチャを変更するのか。
あるいは、新しい構造を追加して、この要件をEitherよりも効果的に満たす新しいデータ型を作成することは可能か。
そのデータ型では、orElse、travase、sequenceの振る舞いはどのように変化するか。

// 公式のanswer
There are a number of variations on Option and Either. If we want to accumulate multiple errors, a simple
approach is a new data type that lets us keep a list of errors in the data constructor that represents failures:
trait Partial[+A,+B]
case class Errors+A extends Partial[A,Nothing]
case class Success+B extends Partial[Nothing,B]
There is a type very similar to this called Validation in the Scalaz library. You can implement map, map2,
sequence, and so on for this type in such a way that errors are accumulated when possible (flatMap is unable to
accumulate errors--can you see why?). This idea can even be generalized further--we don't need to accumulate failing
values into a list; we can accumulate values using any user-supplied binary function.
It's also possible to use Either[List[E],_] directly to accumulate errors, using different implementations of
helper functions like map2 and sequence.