少年易酔學難成

IT/技術的な話題について書きます

Scalaでもパイプラインできるもん！

Scala 小ネタ

Elixirのパイプライン演算子が羨ましくなったので作ってみました。

と言っても、こいつ↓でオブジェクトにパイプライン演算子を生やすだけです。

implicit class Pipe[A](value: A) {
  def |>[B](f: A => B): B = f(value)
}

こんな感じでかけます。

List(List(1,2,3),List(4),List(5)) |> (_.flatten) |> (_.map(Math.pow(_, 2))) // => List(1, 4, 9, 16, 25)

見易く演算子の前で改行を入れる場合はそのままだとエラーになるので、ちょっとカッコ悪いですが.を入れましょう。

List(List(1,2,3),List(4),List(5))
  .|> (_.flatten)
  .|> (_.map(Math.pow(_, 2))) // => List(1, 4, 9, 16, 25)

メソッドチェーンとは違い(メソッドだけでなく)関数のチェーンを型注釈なしで書けるので、割と使い勝手が良さそう。 値クラスに出来ればもっと良いのだけれど。

二分木の畳み込みを末尾再帰化したい人生だった

Scala algorithm

※ この記事はアルゴリズムに詳しくない人が自分の思考の記録のために書いた記事です。 なので書いた内容が合っているかは確証が持てません。 「大間違いだよ、馬鹿野郎！」というツッコミは大歓迎します。

突然どうした

現在、自分はプロジェクトでScalaを使っている。 そのプロジェクトでは毎週木曜日に1時間FPinScalaの勉強会をやっているのだけど、現在読んでいる3章は前にも解いたことがあり、ただ同じように解いてもつまらないのでなるべく末尾再帰の形にするようにしている。

昨日はexercise3.25を解いていた。 この問題は二分木のノードの数をカウントするsize関数を実装せよ、という問題だ。 ここで用いる二分木の定義は以下の通り。

sealed trait Tree[+A]
case class Leaf[A](value: A) extends Tree[A]
case class Branch[A](left: Tree[A], right: Tree[A]) extends Tree[A]

で、size関数は普通に書けば↓のように書ける。

def size[A](tree: Tree[A]): Int = tree match {
  case Leaf(_)      => 1
  case Branch(l, r) => size(l) + 1 + size(r)
}

これの末尾再帰化は二分木だし結構時間かかるのでは…と思ったら、意外にもすぐに末尾再帰化できた。

def size[A](tree: Tree[A]): Int = {
  // ListはFPinScalaで定義した自前のものを使っている
  @annotation.tailrec
  def go[A](tree: Tree[A], acc: Int, notCalculated: List[Tree[A]]): Int = tree match {
    case Leaf(_) => notCalculated match {
      case Nil        => acc + 1
      case Cons(h, t) => go(h, acc + 1, t)
    }
    case Branch(l, r) => go(l, acc + 1, Cons(r, notCalculated))
  }
  go(tree, 0, Nil)
}

二分木を扱う関数で末尾再帰化するイメージは自分にはなかったので、とても感動した。 この例では、未計算のツリーのリストを再帰で渡してやることで難なく末尾再帰化できるのだ。

もう少し突き詰めると、スタックの代わりとなるデータ型をうまく考えてやれば色々なものを末尾再帰化できるようになるのではないか。 例えば、二分木のfoldやmap関数だ。

そして試行錯誤が始まった

元々書いていたfold関数の回答は↓の通り。

def fold[A, B](a: Tree[A])(f: A => B)(g: (B, B) => B): B = a match {
  case Branch(l, r) => g(fold(l)(f)(g), fold(r)(f)(g))
  case Leaf(v)      => f(v)
}

これをまずはこのように修正した。

def fold[A, B](tree: Tree[A])(f: A => B)(g: (B, B) => B): B = {
  @annotation.tailrec
  def go(tree: Tree[A], acc: Option[B], notCalculated: List[Tree[A]])(f: A => B)(g: (B, B) => B): B = tree match {
    case Leaf(v) => notCalculated match {
      case Nil        => acc.map(g(_, f(v))).getOrElse(f(v))
      case Cons(h, t) => go(h, acc.map(g(_, f(v))).orElse(Some(f(v))), t)(f)(g)
    }
    case Branch(l, r) => go(l, acc, Cons(r, notCalculated))(f)(g)
  }
  go(tree, None, Nil)(f)(g)
}

が、これは実装の途中で悪手だと気づいた。 これは木の左側からLeafを見つけ次第たたみ込んでいるので元々のfold関数と評価の順番が変わってしまっている。 畳み込み関数gの実装によっては出力される答えが変わってしまうだろう。

ここで元々のfold関数の評価順を守ろうとすると別の問題が出てくる。 再帰呼び出しで渡すデータは未計算のツリーだけではなく左側のLeafで計算した値も必要になるのだ。

この問題の解決方法はなかなか思い浮かばなかった。

途中、notCalculated: List[Tree[A]]の他に、別の引数として左側のリーフを計算した値leftAcc: Option[B]も一緒に渡す事も検討したが、 処理するLeafが左側であるのか右側であるのかわからないのでうまく行かない。

ここで初めてfoldを実装するには関数がツリーの構造を知る必要があるのだと気づいた。

そこでnotCalculated: Tree[A]ではなく(Option[B], List[Tree[A]])のようなデータを渡したらどうかとも考えたが、データ構造がやや複雑に思えたので断念し、他に良いアイデアも思い浮かばなかったのでこの日は諦めた。

試行錯誤二日目

昨晩考えても答えが出なかったので、ちょっと一旦PCを離れて紙と鉛筆で考えてみることにした。

その結果、次の再帰に渡したいデータは、右のLeafの場合も左のLeafの場合も計算の小計だがBranchを処理する場合は未計算のツリーであることに気づいた。 そこで次の再帰に渡したいデータをstack: List[Either[B, Tree[A]]]に格納し、stackに格納されたデータ型によって関数が元のツリーの構造を判断するようにした。

それがこちらの実装。

def fold[A, B](tree: Tree[A])(f: A => B)(g: (B, B) => B): B = {
  @annotation.tailrec
  def go(tree: Tree[A], stack: List[Either[B, Tree[A]]])(f: A => B)(g: (B, B) => B): B = tree match {
    case Leaf(v) => stack match {
      case Cons(Right(next), rest) => go(next, Cons(Left(f(v)), rest))(f)(g) // 左枝の場合
      case Cons(Left(leftAcc), Cons(Right(next), rest)) => go(next, Cons(Left(g(leftAcc, f(v))), rest))(f)(g) // 右枝の場合
      case Cons(Left(leftAcc), Cons(Left(acc), _)) => g(acc, g(leftAcc, f(v))) // 右端のLeaf到達パターン1
      case Cons(Left(leftAcc), Nil) => g(leftAcc, f(v)) // 右端のLeaf到達パターン2
      case Nil => f(v) // この場合はLeafのみのTree
    }
    case Branch(l, r) => go(l, Cons(Right(r), stack))(f)(g)
  }
  go(tree, Nil)(f)(g)
}

自分はこれを書いた後、とても後悔することになった。 よく確かめもせず周囲に完成したと吹聴してしまったからだ。

これは全く正しく動作しない。

右側に偏った木をfoldしようとすると、未計算の木がstack奥深くに格納されてしまうのでパターンマッチで拾えず、未計算の木を残したまま計算が終了してしまうからだ。

これを解消するために、常に未計算の木が先頭に来るまで計算を進めることにした。

def fold[A, B](tree: Tree[A])(f: A => B)(g: (B, B) => B): B = {
  @annotation.tailrec
  def eval(stack: List[Either[B, Tree[A]]]): List[Either[B, Tree[A]]] = stack match {
    case Cons(Left(e1), Cons(Left(e2), rest))   => eval(Cons(Left(g(e2, e1)), rest))
    case Cons(Left(e1), Cons(r@Right(_), rest)) => Cons(r, Cons(Left(e1), rest)) // 呼出元で木を取り出しやすいよう入れ替え
    case _                                      => stack
  }
  @annotation.tailrec
  def go(tree: Tree[A], stack: List[Either[B, Tree[A]]]): B = tree match {
    case Leaf(v) =>
      // 計算済みの値がstackに連続して溜まると未計算の木が取り出せないので出来るだけ計算を進める
      eval(Cons(Left(f(v)), stack)) match {
        case Cons(Right(next), rest) => go(next, rest)
        case Cons(Left(e1), _)       => e1 // 最後まで評価が終わっているはず
        case Nil                     => f(v)
      }
    case Branch(l, r) => go(l, Cons(Right(r), stack))
  }
  go(tree, Nil)
}

これで、正しく動くようになった。(たぶん)

さてfoldさえできれば、mapを実装することは簡単だ。

def map[A, B](tree: Tree[A])(f: A => B): Tree[B] = {
  fold(tree)(v => Leaf(f(v)): Tree[B])(Branch(_, _))
}

パフォーマンスなどの議論は詳しくないから抜きにして、とりあえず二分木の畳み込みを末尾再帰化するという目的は達成できたように思える。

{1,2,3,5,7}みたいなリストを"1-3,5,7"に変換する

Scala algorithm

電車で移動中にタイムラインに流れて来てちょっと面白そうだということで実装してみた。

スマートに書けるかな、と思ったけどそんな事はなかった。

object ListConverter {
  /**
    * {1,2,3,5,7}みたいな配列（またはリスト）を“1-3,5,7”に変換する
    */
  def toSequenceString(list: List[Int]): String = {
    val sorted = list.sorted
    sorted.lastOption match {
      case None       => ""
      case Some(last) =>
        val (grouped, _) = sorted.init.foldRight((List(List(last)), last)) {
          case (cr, (h :: t, prv)) if prv - 1 == cr => ((cr :: h) :: t, cr)
          case (cr, (acc, _))                       => (List(cr) :: acc, cr)
        }
        grouped.map {
          case Nil      => ""
          case h :: Nil => h.toString
          case l        => s"${l.head}-${l.last}"
        }.mkString(",")
    }
  }
  /**
    * “1-3,5,7”をList(1,2,3,5,7)に変換する(toSequenceStringの逆変換)
    */
  def sequenceStringToList(str: String): Either[Throwable, List[Int]] = {
    def map2[E, A, B, C](e1: Either[E, A], e2: Either[E, B])(f: (A, B) => C): Either[E, C] = for {
      a <- e1
      b <- e2
    } yield f(a, b)

    str.split(",").map { s =>
      s.split("-") match {
        case Array(from, to) => Try((from.toInt to to.toInt).toList).toEither
        case Array(numStr)   => Try(List(numStr.toInt)).toEither
        case _               => Left(new IllegalArgumentException(s"パースできない文字列: $str"))
      }
    }.foldRight[Either[Throwable, List[Int]]](Right(List()))(map2(_, _)(_ ++ _))
  }
}

良いやり方を思い付いたら、また公開する。

traverseとsequenceをめぐる冒険

Scala

事の発端

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)
  }
}

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

教訓

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

play-jsonについて学ぶ(2)

Scala PlayFramework play-json

Readsをどのように書くか

前回のエントリでplay-jsonのReads/Writesの意味とPlay Frameworkでの使い方を確認したので、実際にReads/Writesをどのように書くかを考えてみる。 今回はReads。

愚直にReadsを書く

JsValue => Aの処理を最も愚直に書けば以下のようになる。

case class SampleJson(
  f1: String,
  f2: Int,
  f3: NestedJson
)

case class NestedJson(
  f4: String
)

implicit val nestedJsonReads: Reads[NestedJson] = Reads[NestedJson] {
  case JsObject(fields) => fields.get("f4").map(StringReads.reads(_).fmap(NestedJson)).getOrElse(JsError(__ \ "f4", "error.required"))
  case _                => JsError(__, "error.expected.jsobject")
}

implicit val sampleJsonReads: Reads[SampleJson] = Reads[SampleJson] {
  case JsObject(fields) =>
    (
      fields.get("f1").map(StringReads.reads(_)).getOrElse(JsError(__ \ "f1", "error.required")),
      fields.get("f2").map(IntReads.reads(_)).getOrElse(JsError(__ \ "f2", "error.required")),
      fields.get("f3").map(nestedJsonReads.reads(_)).getOrElse(JsError(__ \ "f3", "error.required")).repath(__ \ "f3")
    ) match {
      case (JsSuccess(f1, _), JsSuccess(f2, _), JsSuccess(f3, _)) => JsSuccess(SampleJson(f1, f2, f3))
      // フィールドのどれか一つの読み取りがエラーのケース
      case (err@JsError(_),   JsSuccess(_, _),  JsSuccess(_, _))  => err
      case (JsSuccess(_, _),  err@JsError(_),   JsSuccess(_, _))  => err
      case (JsSuccess(_, _),  JsSuccess(_, _),  err@JsError(_))   => err
      // 二つのフィールドの読み取りがエラーのケース
      case (err1@JsError(_), err2@JsError(_), JsSuccess(_, _))    => JsError.merge(err1, err2)
      case (err1@JsError(_), JsSuccess(_, _), err2@JsError(_))    => JsError.merge(err1, err2)
      case (JsSuccess(_, _), err1@JsError(_), err2@JsError(_))    => JsError.merge(err1, err2)
      // 全てのフィールドの読み取りがエラーのケース
      case (err1@JsError(_), err2@JsError(_), err3@JsError(_))    => JsError.merge(JsError.merge(err1, err2), err3)
    }
  case _                => JsError(__, "error.expected.jsobject")
}

この書き方だと見通しが悪くなるし、フィールドの数が増えた場合に対応するのは大変だ。 二つのJsResultをマージする関数を作り、それを元に3つ、4つのJsResultをマージする方が簡単だろう。

def apply2[A, B, C](r1: JsResult[A], r2: JsResult[B])(f: (A, B) => C) = {
  case (e1@JsError(_), e2@JsError(_))       => JsError.merge(e1, e2)
  case (e@JsError(_),  _)                   => e
  case (_,             e@JsError(_))        => e
  case (JsSuccess(v1, _), JsSuccess(v2, _)) => JsSuccess(f(v1, v2))
}

def apply3[A, B, C, D](r1: JsResult[A], r2: JsResult[B], r3: JsResult[C])(f: (A, B, C) => D) = (apply2(r1, r2)((_, _)), r3) match {
  case (e1@JsError(_), e2@JsError(_))             => JsError.merge(e1, e2)
  case (e@JsError(_),  _)                         => e
  case (_,             e@JsError(_))              => e
  case (JsSuccess((v1, v2), _), JsSuccess(v3, _)) => JsSuccess(f(v1, v2, v3))
}

implicit val sampleJsonReads: Reads[SampleJson] = Reads[SampleJson] {
  case JsObject(fields) =>
    apply3(
      fields.get("f1").map(StringReads.reads(_)).getOrElse(JsError("error.required")).repath(__ \ "f1"),
      fields.get("f2").map(IntReads.reads(_)).getOrElse(JsError("error.required")).repath(__ \ "f2"),
      fields.get("f3").map(nestedJsonReads.reads(_)).getOrElse(JsError("error.required")).repath(__ \ "f3")
    )(SampleJson)
  case _                => JsError(__, "error.expected.jsobject")
}

もちろん、上記のように愚直にReadsを書くことはほとんどないだろう。 これは単にJsValueやJsResultがどのようなものか理解するためだけのものだ。

FunctionalBuilderやJsPathを使って書く

もちろん、apply2, apply3を自前で用意する必要はない。 JsResultはplay.api.libs.functional.FunctionalBuilderのandを使えばいい。

implicit val sampleJsonReads: Reads[SampleJson] = Reads[SampleJson] {
  case JsObject(fields) =>
    (
      fields.get("f1").map(StringReads.reads(_)).getOrElse(JsError("error.required")).repath(__ \ "f1") and
      fields.get("f2").map(IntReads.reads(_)).getOrElse(JsError("error.required")).repath(__ \ "f2") and
      fields.get("f3").map(nestedJsonReads.reads(_)).getOrElse(JsError("error.required")).repath(__ \ "f3")
    )(SampleJson)
  case _                => JsError(__, "error.expected.jsobject")
}

まだコードにはボイラープレートが残っている。 一つはJsObjectとその他の場合のパターンマッチ。 二つめはfields.get(...).map(...).getOrElse(JsError("error.required")).repath(__ \ ...)の箇所だ。

この問題を解決する方法がJsPathにある。JsPathはJsValueへのパスを表現するデータ型だ。 JsPathにあるread[T]を使えば以下のように書ける。

implicit val sampleJsonReads: Reads[SampleJson] = (
  (__ \ "f1").read[String] and
  (__ \ "f2").read[Int] and
  (__ \ "f3").read[NestedJson]
)(SampleJson)

read[T]は暗黙のパラメータとしてReads[T]を要求するので、String/Int/NestedJsonのReadsがimplicitのスコープ内でimplicit付きで定義されている必要がある。(明示的に渡す必要はない)

実はこの書き方だと渡されたJsValueがJsObjectではなかった時のエラーメッセージが"error.path.missing"になるという細かい違いがあるのだが、それはここでは無視する。 また、Option[T]にマッピングするような任意項目の読み取りをしたい場合はreadNullable[T]を使えば"error.path.missing"で怒られることはない。

これでだいぶスッキリした書き方になった。

え？いちいちパスを書くのも面倒くさい？SampleJsonのフィールド名から組み立てられないのか？ もちろん、その要求に応える方法も、ある。

macroを使った書き方

play-jsonのJsonオブジェクトにはReads/Writesをマクロで構築する便利なメソッドがいくつか定義されている。 それを用いると以下のように書ける。

implicit val nestedJsonReads: Reads[NestedJson] = Json.reads[NestedJson]
implicit val nestedJsonReads: Reads[NestedJson] = Json.reads[SampleJson]

わずか二行でReads[SampleJson]の作成に必要な全てのコードが書けてしまった。

まとめ

Readsの書き方を、愚直な書き方から怠惰な書き方まで一通り追った。

もし、怠惰な書き方でうまく行かないような場面に遭遇しても、最悪愚直な書き方に戻って実現すればいいと思えば心健やかにコーディングできるはずだ。 多分、そういった心のゆとりがある方がスマートなやり方を思いつけるはずだ、、、。

play-jsonについて学ぶ(1)

Scala PlayFramework play-json

目的

現在のプロジェクトではJSONライブラリとしてplay-jsonを(play scalaと共に)使用している。 play-jsonはドキュメントは豊富なのでググれば大抵の問題は解決できて便利なのだけれども、ググってもやり方が見つからない場合は解決に時間がかかってしまっていた。 これはplay-jsonの基本を理解していなかったからだと思っていて、そこでplay-jsonのソースコードを読み込んでみた。

この記事の目的はそのとき理解したことの整理だ。

play-jsonの基本

JSONの読み込み

JSONを読み込み、任意のクラスAにマッピングする処理は次の二段階で行われる。

  1. JSONをJsValueへ変換する
  2. JsValueをJsResult[A]に変換する(ここでAは任意のクラス)

JsValueはJSONの抽象構文木で、JSONの値型に対応するサブクラス(JsNull, JsObject, JsArray, JsBoolean, JsString, JsNumber)が存在する。 JsResult[A]はAへの変換結果を表すクラスで、成功すればJsSuccess[A]、失敗すればJsErrorとなる、いわばEither[L, R]に似たクラスだ。

1の変換はJson.parseによって行われ、2の変換はReads[A]によって行われる。 ここでJSONの文法に合致しない不正なJSONが与えられた場合、Json.parseで使われているJacksonの例外(JsonParseExceptionなど)がスローされる。 2でJsValueからAへの変換に失敗した場合は例外ではなくJsErrorで通知される。JsErrorはその失敗原因をerrors: Seq[JsonValidationError]によって保持している。

Json.parseはドメインに依存しない処理なので、ユーザはReads[A]を定義することによって目的の処理を得る。

JSONの書き出し

JSONの書き出しも読み込みと同じくJsValueを介した二段階で行われる。

  1. 任意のクラスAをJsValueに変換する
  2. JsValueをJSONに変換する

1の変換はWrites[A]もしくはOWrites[A]によって行われ、2の変換はJson.stringifyなどで行われる(整形の有無などいくつかのメソッドがある)。 Writes[A]とOWrites[A]の違いは、Writes[A]はAをJsValueに変換するがOWrites[A]はAをJsObjectに変換するというところだ。 OWrites[A]はWrites[A]を継承(trait OWrites[-A] extends Writes[A])している。

ほとんどの場合JSONはトップレベルはObjectとなるので、OWrites[A]の使用が妥当であるように思えるが、後述するような小さなWrites[A]を組み合わせて大きなWrites[A]を作っていくスタイルであればWrites[A]を使用した方が良いだろう。

読み込みの場合と同じく、Json.stringifyはドメインに依存しない処理となるので、ユーザはWrites[A]を定義することによって目的の処理を得る。

Play FrameworkのActionにおけるplay-json

Reads/Writesのイメージを固めるために、Play Frameworkでのplay-jsonの典型的な使用例を挙げる。

implicit val sampleJsonReads: Reads[SampleJson] = Json.reads[SampleJson] // Reads[SampleJson]の定義。定義の意味については後述する。

def sample: Action[JsValue] = Action.async(parse.json) { implicit request =>
  request.body.validate[SampleJson].fold(
    errs => Future.successful(BadRequest), // JsErrorの場合の処理(errsはSeq[JsonValidationError]型)
    json => { // JsSuccessの場合の処理(jsonはSampleJson型)
      // 何か処理
    }
  )
}

Action[A]はRequest[A]を受け取ってResultを返すRequest[A] => Resultの関数だ。 Request[A]はA型に変換されたbodyを持つリクエストという意味なので、このサンプルでのrequest.bodyはJsValueとなる。 JsValue#validate[A]は暗黙的(implicit)にReads[A]を引数にとりJsResult[A]を返す。 大抵の場合はJsResult[A]のfoldを使って異常系と正常系の処理を記述する。

まとめ

ここまでが、play-jsonのReads/Writesを理解する上での基本だと考えている。 自分はこれを理解するまで、Readsを書くのにとても苦労していた。

ということで、次回はReadsの書き方についてまとめてみようと思う。

S-99: Ninety-Nine Scala ProblemsのP07を末尾再帰にするだけの正月だった

Scala algorithm

昨年大晦日から、少しずつS-99: Ninety-Nine Scala Problemsに取り組んでいる。 取り組み方は色々あると思うが、個人的に設定したルールは以下の二つ。

これで現時点(2018/01/08)ではP26まで解いていたのだが、P07・P26においては技量が足らず末尾再帰化を諦めていた。 しかし私の中のリトル佐藤が、年始休暇も終わるというのにこの体たらくでは悔いが残るといっているので、せめてP07だけでも末尾再帰化することにした。

まず、問題はこいつ。

P07 (**) Flatten a nested list structure.
Example:
scala> flatten(List(List(1, 1), 2, List(3, List(5, 8))))
res0: List[Any] = List(1, 1, 2, 3, 5, 8)

注意したいのはflattenのシグニチャが def flatten(list: List[Any]): List[Any] となるところだろうか。 例えばこいつが def flatten[A](list: List[List[A]]): List[A] であれば問題は簡単で、以下のように書けば良いはずだ。

def flatten[A](list: List[List[A]]): List[A] = {
  @annotation.tailrec
  def go(acc: List[A], list: List[List[A]]): List[A] = list match {
    case Nil       => acc
    case e :: rest => go(addAll(acc, e), rest)
  }

  go(Nil, list)
}

しかし、実際のシグニチャが def flatten(list: List[Any]): List[Any] であることにより、末尾再帰を諦め、以下のコードとなってしまっていた。 このコードでは、縦(Listのネスト)方向にも横(Listの要素)方向にも再帰をしなければならないため、再帰(goの部分)が二回出現している。

def flatten(list: List[Any]): List[Any] = {
  // TODO 末尾再帰にできぬ...できぬのだ!!
  def go(acc: List[Any], maybeList: Any): List[Any] = maybeList match {
    // Listの場合
    case e :: rest => go(go(acc, e), rest)
    case Nil       => acc
    // それ以外
    case e         => e :: acc
  }

  P05.reverse(go(Nil, list)) // P05では末尾再帰のreverseを定義している
}

しばし、こういう場合は末尾再帰にできないものと考えていた。 しかし、正月休みで休養・アルコール・気合が充分な状態で再度検討してみると、goが縦・横方向への再帰のため二回出現しているから末尾再帰ができないのだから縦横で別々の関数を使うようにすれば末尾再帰化できるのではないか、と考えた。

このアイデアを用いて書いたコードがこれ。

@annotation.tailrec
def flatten(list: List[Any]): List[Any] = {
  // もちろん、addとかaddAllは自前で末尾再帰化したコードを用意している
  @annotation.tailrec
  def go(acc: List[Any], list: List[Any]): List[Any] = list match {
    case (l: List[Any]) :: rest => go(addAll(acc, l), rest)
    case e :: rest              => go(add(acc, e), rest)
    case Nil                    => acc
  }

  // 型注釈を付けないとコンパイル通らない理由はいずれ調査されるだろう...
  if (forall(list, (e => !e.isInstanceOf[List[Any]]): Any => Boolean)) {
    list
  } else {
    flatten(go(Nil, list))
  }
}

予想通り、再帰の方向で別々の関数に分ければ末尾再帰化できた。

この解法が汎用的に使えるかどうかを考えるにはちょっと酔っ払いすぎていてよくわからないけども、とにもかくにも前に進むことができた。