少年易酔學難成

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

traverseとsequenceをめぐる冒険

事の発端

Scalaを書いているとビジネスロジックの結果の合成などでEitherValidationsequenceメソッドが欲しい!ということがあります。 ちょうど今のプロジェクトでもそういう声が結構あって、「これ、進研ゼミでやったぞ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.companionnewBuilderがいることがわかった。 ということで最終形はこちら。

  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)

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を書くことはほとんどないだろう。 これは単にJsValueJsResultがどのようなものか理解するためだけのものだ。

FunctionalBuilderやJsPathを使って書く

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

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にある。JsPathJsValueへのパスを表現するデータ型だ。 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-jsonJsonオブジェクトにはReads/Writesをマクロで構築する便利なメソッドがいくつか定義されている。 それを用いると以下のように書ける。

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

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

まとめ

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

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

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

目的

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

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

play-jsonの基本

JSONの読み込み

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

  1. JSONJsValueへ変換する
  2. JsValueJsResult[A]に変換する(ここでAは任意のクラス)

JsValueJSONの抽象構文木で、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. 任意のクラスAJsValueに変換する
  2. JsValueJSONに変換する

1の変換はWrites[A]もしくはOWrites[A]によって行われ、2の変換はJson.stringifyなどで行われる(整形の有無などいくつかのメソッドがある)。 Writes[A]OWrites[A]の違いは、Writes[A]AJsValueに変換するがOWrites[A]AJsObjectに変換するというところだ。 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.bodyJsValueとなる。 JsValue#validate[A]は暗黙的(implicit)にReads[A]を引数にとりJsResult[A]を返す。 大抵の場合はJsResult[A]のfoldを使って異常系と正常系の処理を記述する。

まとめ

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

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

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

昨年大晦日から、少しずつ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))
  }
}

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

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

AutoHotKey事始

勤務先の個人用PCがシンクライアント+仮想デスクトップに移行するため、このままでは英字配列のHHKBが使えなくなってしまう。
対応策として、以下の二点を考え付いた。

  1. HHKBとシンクラの間で物理的にJP配列を英字配列に変換する
  2. 仮想デスクトップ上のアプリケーションの前で英字配列に変換する

前者は手軽に行うのは難しそうなので断念し、後者をAutoHotKeyで実現することにした。

パクった参考にしたサイトは以下の通り。
http://ahk.xrea.jp/index.html
http://qiita.com/844196/items/9fc1cd8470a9ad9c3a69

とりあえず、今の設定はこんな感じ。
一番右上のチルダのキーが効かないのが悩み。

*"::send, @
*&::send, {^}
*'::send, &
*(::send, *
*)::send, (
*+0::send, )
*=::send, _
*^::send, =
*~::send, {+}
*@::send, [
*`::send, {{}
[::send, ]
*+{::send, {}}
*]::send, \
*}::send, |
*+::send, :
+*::send, "
LWin::LAlt
LAlt::LWin
RWin::Send, {vkF3sc029}
*vkBA::send, '

JavaScriptで文字コード値⇔文字列変換

作成中のアプリにてエラーメッセージが文字コードで出力されたので、文字列に変換する処理を書いてみた。

/**
 * 文字コード値→文字列
 */
function (cd) {
    var cdArr = cd.replace(/\\u([0-9a-fA-F]{1,4})/g, function () {
        return parseInt(arguments[1], 16) + ',';
    }).split(',');
    return String.fromCharCode.apply(String, cdArr);
}

ついでに逆の処理も書いた。

/**
 * 文字列→文字コード値
 */
function (str) {
    var i = str.length, temp = new Array(i);
    if (str === '') return '\\u0000';
    while (i--) {
        temp[i] = '\\u' + ('000' + str.charCodeAt(i).toString(16)).slice(-4);
    }
    return temp.join('');
}