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) } }
意外と考慮すべきことが多くて、自分の短慮を知ることとなった。
教訓
- ドキュメントは最後までしっかり読みましょう
- コップ本はとても重要です
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
を書くことはほとんどないだろう。
これは単に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)
目的
現在のプロジェクトではJSONライブラリとしてplay-jsonを(play scalaと共に)使用している。 play-jsonはドキュメントは豊富なのでググれば大抵の問題は解決できて便利なのだけれども、ググってもやり方が見つからない場合は解決に時間がかかってしまっていた。 これはplay-jsonの基本を理解していなかったからだと思っていて、そこでplay-jsonのソースコードを読み込んでみた。
この記事の目的はそのとき理解したことの整理だ。
play-jsonの基本
JSONの読み込み
JSONを読み込み、任意のクラスAにマッピングする処理は次の二段階で行われる。
- JSONを
JsValue
へ変換する 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
を介した二段階で行われる。
- 任意のクラス
A
をJsValue
に変換する 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を末尾再帰にするだけの正月だった
昨年大晦日から、少しずつS-99: Ninety-Nine Scala Problemsに取り組んでいる。 取り組み方は色々あると思うが、個人的に設定したルールは以下の二つ。
- Listのコンストラクタ(Nil or ::)以外は自作する
- なるべく末尾再帰にこだわる(なぜ末尾再帰にこだわるか)
これで現時点(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が使えなくなってしまう。
対応策として、以下の二点を考え付いた。
- HHKBとシンクラの間で物理的にJP配列を英字配列に変換する
- 仮想デスクトップ上のアプリケーションの前で英字配列に変換する
前者は手軽に行うのは難しそうなので断念し、後者を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(''); }