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

Exercise 7.5 このsequenceという関数を記述せよ。追加のプリミティブは必要ない。runを呼び出さないこと。
def sequence[A](ps:List[Par[A]]):Par[List[A]]

いろいろ解答例がでていた。
def sequence_simple[A](l: List[Par[A]]): Par[List[A]] =
  l.foldRight[Par[List[A]]](unit(List()))((h,t) => map2(h,t)(_ :: _))
このfoldRightを使う方法は、すでにこれまでにもでてきたパターン。


def sequenceRight[A](as: List[Par[A]]): Par[List[A]] =
  as match {
    case Nil => unit(Nil)
    case h :: t => map2(h, fork(sequence(t)))(_ :: _)
  }

こちらは、効率いい方法ということのようだけれど、難しい。
def sequenceBalanced[A](as: IndexedSeq[Par[A]]): Par[IndexedSeq[A]] = fork {
  if (as.isEmpty) unit(Vector())
  else if (as.length == 1) map(as.head)(a => Vector(a))
  else {
    val (l,r) = as.splitAt(as.length/2)
    map2(sequenceBalanced(l), sequenceBalanced(r))(_ ++ _)
  }
}

def sequence[A](as: List[Par[A]]): Par[List[A]] =
  map(sequenceBalanced(as.toIndexedSeq))(_.toList)