ScalaでEitherのリストを畳み込む

久しぶりにアプリケーションで再帰のコードを書いたのでメモ。

Eitherになるリスト

リストに返り値がEitherになる関数を先頭から適用していき、その結果をひとつのEitherとして返す関数が欲しい。
Leftが発生した場合はその値を返す。

def sample1[A, B, C](list: List[A], f: A => Either[B, C]): Either[B, List[C]]

foldLeft

畳み込みなので foldLeft を使うとこのようになる。

def sample1[A, B, C](list: List[A], f: A => Either[B, C]): Either[B, List[C]] = {
  list.foldLeft[Either[B, List[C]]](Right(Nil)) {
    case (Right(acc), x) => f(x).map(_ :: acc)
    case (l, _)          => l
  }.map(_.reverse)
}

リストでの関数適用順が逆になりLeftの結果が変わってしまうため foldRight を使って map(_.reverse) を除去することはできない。

再帰

sample1ではLeftが発生した後もリストの走査が続いているが、Leftが出た時点で終了させたい。
また、アキュムレーターを要素ごとに毎回matchするのも計算量はともかく、読む時のノイズになるため除去したい。

scalaにはコレクションの走査を中断する方法がいくつかあるが、再帰で表現した場合はこうなる。

def sample2[A, B, C](list: List[A], f: A => Either[B, C]): Either[B, List[C]] = {
  @tailrec
  def rec(acc: List[C], xs: List[A]): Either[B, List[C]] = xs match {
    case x :: tail =>
      f(x) match {
        case Right(r) => rec(r :: acc, tail)
        case Left(l)  => Left(l)
      }
    case Nil =>
      Right(acc)
  }
  rec(Nil, list).map(_.reverse)
}

whileループ

Scalaではmutableにwhileループを使うこともできる。ライブラリではよく見られる実装方法である。

def sample3[A, B, C](list: List[A], f: A => Either[B, C]): Either[B, List[C]] = {
  val builder = List.newBuilder[C]
  var these: List[A] = list
  while (list.nonEmpty) {
    f(list.head) match {
      case Right(r) => builder.addOne(r)
      case Left(l)  => return Left(l)
    }
    these = these.tail
  }
  Right(builder.result())
}

終わり

scalaでは標準ライブラリで一通りのコレクション操作ができるため、自分で繰り返しを書く機会は少ない。ライブラリの実装ではmutableにwhileループで実装している場合が多い。それでもmutableのコードは注意が必要であることには変わらないため、アプリケーションコードでは避けたい。機会は少ないがScalaでも再帰は書くことがあるので覚えておきたい。

このケースであれば関数型ライブラリでも解決できそうだが。