traverseとsequenceをめぐる冒険

事の発端

Scalaを書いているとビジネスロジックの結果の合成などでEitherやValidationのsequenceメソッドが欲しい！ということがあります。 ちょうど今のプロジェクトでもそういう声が結構あって、「これ、進研ゼミでやったぞFP in Scalaで書いたぞ！」と思ってたので共通処理として実装してみることにした。

ただ、FP in Scalaでやったとはいえ、実際にマージされるまではそれなりに試行錯誤があったので、その過程をメモ。

最初に書いたコード

まずはEitherのsequence/traverseを実装した。

implicit class EitherOps[E, A](e: Either[E, A]) {
  def map2[EE >: E, B, C](o: Either[EE, B])(f: (A, B) => C): Either[EE, C] =
    for {
      a <- e
      b <- o
    } yield f(a, b)
}

implicit class SeqOps[A](seq: Seq[A]) {
  def traverse[E, B](f: A => Either[E, B]): Either[E, Seq[B]] = {
    seq.map(f).foldRight[Either[E, Seq[B]]](Right(Nil))(_.map2(_)(_ +: _))
  }
  def sequence[E, B](implicit ev: A =:= Either[E, B]): Either[E, Seq[B]] = {
    seq.traverse(identity(_))
  }
}

すると(Right(1): Either[String, Int]).sequenceとした時にCannot prove that Either[Int,Int] =:= Either[E,B]と怒られた。

なんでじゃい！あってるじゃろがい！scalacの分からず屋！と思ったが、ある人に聞いたところ、 "A =:= Either[E, B] であるかどうかは、sequenceの呼び出しの型パラメータE, Bが確定しないとわからないので、型パラメータなしで呼び出すと型が一致してるかどうか判定しようがない。" ということだった。

型クラスを分ければいいじゃない。

さて、いちいち型パラメータ付きで呼び出すのも気が利かない。 少し考えて結局↓のように型クラスを分けることにした。

implicit class EitherOps[E, A](e: Either[E, A]) {
  def map2[EE >: E, B, C](o: Either[EE, B])(f: (A, B) => C): Either[EE, C] =
    for {
      a <- e
      b <- o
    } yield f(a, b)
}
implicit class SeqEitherOps[E, A](seq: Seq[Either[E, A]]) {
  def sequence: Either[E, Seq[A]] = {
    seq.traverse(identity(_))
  }
}
implicit class SeqOps[A](seq: Seq[A]) {
  def traverse[E, B](f: A => Either[E, B]): Either[E, Seq[B]] = {
    seq.map(f).foldRight[Either[E, Seq[B]]](Right(Nil))(_.map2(_)(_ +: _))
  }
}

ただ、このコードにも問題が残っていて、mapで中間データを作ってしまっているしtraverseが戻り値同型の法則に反しているとの指摘を受けた。 foldRightの初期値にNilを使っているので、seqがVectorであってもListを返してしまうのだ。

さて、これをどうしたものか。 S[_] <: Seq[_]みたいな型を取るようにしても要素が空の新しいインスタンスを生成できないし...。 と少し悩んだところで、前日の勉強会でCanBuildFromとは何者かという話題が上がったのを思い出した。

Builderを使えばいいじゃない。

CanBuildFromが何者かはよく話を聞いてなかったのでその場では理解できなかったのでわからない。 けどコップ本25章やここを読んで書いてみた。(多分、二つとも元の文章は同じ)

implicit class EitherOps[E, A](e: Either[E, A]) {
  def map2[EE >: E, B, C](o: Either[EE, B])(f: (A, B) => C): Either[EE, C] =
    for {
      a <- e
      b <- o
    } yield f(a, b)
}
implicit class SeqEitherOps[E, A](seq: Seq[Either[E, A]]) {
  def sequence: Either[E, Seq[A]] = {
    seq.traverse(identity)
  }
}
implicit class SeqOps[A](seq: Seq[A]) {
  def traverse[E, B](f: A => Either[E, B])(implicit bf: CanBuildFrom[Seq[A], B, Seq[B]]): Either[E, Seq[B]] = {
    seq.foldRight[Either[E, Seq[B]]](Right(bf(seq).result))((a, acc) => f(a).map2(acc)(_ +: _))

これでVector渡せばVectorが帰ってくるし、List渡せばListが帰ってくるのでめでたしめでたし。

って思ってたらまたまた↓の指摘を受けた。

• CanBuildFrom受け取らなくてもいけるで
• せっかくBuilderつかってるんだから戻り値の作成にも使いなさいよ
• ヒントはコップ本25章に書いてあるで(え、読んだけど？)

もう一度コップ本25章を読み直したら、seq.companionにnewBuilderがいることがわかった。 ということで最終形はこちら。

  implicit class EitherOps[E, A](e: Either[E, A]) {
    def map2[EE >: E, B, C](o: Either[EE, B])(f: (A, B) => C): Either[EE, C] =
      for {
        a <- e
        b <- o
      } yield f(a, b)
  }
  implicit class SeqEitherOps[E, A](seq: Seq[Either[E, A]]) {
    def sequence: Either[E, Seq[A]] = {
      seq.traverse(identity)
    }
  }
  implicit class SeqOps[A](seq: Seq[A]) {
    def traverse[E, B](f: A => Either[E, B]): Either[E, Seq[B]] = {
      seq.foldLeft[Either[E, Builder[B, Seq[B]]]](Right(seq.genericBuilder))({ (acc, a) =>
        acc.map2(f(a))(_ += _)
      }).map(_.result)
    }
  }

要素追加が+=になってfoldRightを使う理由がなくなったのでfoldLeftに変えている。

Validationもほぼ同じ運命を辿りながらこうなった。

object Validation {
  def map2[E, A, B, C](e1: Either[E, A], e2: Either[E, B])(f: (A, B) => C)(implicit semigroup: Semigroup[E]): Either[E, C] = {
    (e1, e2) match {
      case (Left(l),  Right(_)) => Left(l)
      case (Right(_), Left(l))  => Left(l)
      case (Left(l1), Left(l2)) => Left(semigroup.append(l1, l2))
      case (Right(a), Right(b)) => Right(f(a, b))
    }
  }
  def traverse[E: Semigroup, A, B](seq: Seq[A])(f: A => Either[E, B]): Either[E, Seq[B]] = {
    seq.foldLeft[Either[E, Builder[B, Seq[B]]]](Right(seq.genericBuilder))({ (acc, a) =>
      map2(acc, f(a))(_ += _)
    }).map(_.result)
  }
  def sequence[E: Semigroup, A](seq: Seq[Either[E, A]]): Either[E, Seq[A]] = {
    traverse(seq)(identity)
  }
}

意外と考慮すべきことが多くて、自分の短慮を知ることとなった。

教訓

• ドキュメントは最後までしっかり読みましょう
• コップ本はとても重要です