scala関数型デザイン＆プログラミング Exercise 4.4

Exercise 4.4 OptionのリストをひとつのOptionにまとめるsequence関数を実装せよ。
def sequence[A](a:List[Option[A]]) :Option[List[A]] =
 a match {
 case Nil=>Some(Nil)
 case Some(x)::xs => Some( x::sequence(xs) )
}
と思ったが、sequence(xs)はList[A]でないから、当然エラーが発生する。Optionを取り除くという発想ではだめということがわかる。やはり、これまで通り、flatMapやmapを駆使するとうまくいくようだ。

正解は
def sequence[A](a:List[Option[A]]) :Option[List[A]] =
 a match {
 case Nil=>Some(Nil)
 case x::xs =>  x flatMap( xx => sequence(xs) map(xx::_) )
}
aはOption[A]のリストで、先頭をx、残りがxsとすると
xをflatMapに適用（関数は xx => sequence(xs) map(xx::_)  )
ここで、sequence(xs) map(xx::_) がなかなか発想できなかった。
Optin[List[A]]でなければならないので、Some(xx::(xsのOptionがとれたリスト)）となるようにする必要がある
map(（xsのOptionがとれたリスト）=>xx::（xsのOptionがとれたリスト）)となるようにして、このmapは、何に適用なるかというと
sequence(xs)、つまり（xsのOptionがとれたリスト）のOptionということになる。

別解として、
def sequence_1[A](a: List[Option[A]]): Option[List[A]] =
  a.foldRight[Option[List[A]]](Some(Nil))( (x,y) => map2(x,y)(_ :: _) )
ここで、理由はまだよく理解してないが、[Option[List[A]]]がないとエラーになるようだ。