『データ指向アプリケーションデザイン』を読んだ ー 第I部 データシステムの基礎

『データ指向アプリケーションデザイン』を読んで特に印象に残ったところをメモとして残します。分厚いので数回に分けます。
書籍が素晴らしいので、詳細はそちらを読んでみてください。

データ指向アプリケーションデザイン ―信頼性、拡張性、保守性の高い分散システム設計の原理

はじめに

データ指向とは、データの量や複雑さ、変化の速度が主な課題となるアプリケーションのことを指す。目的を達成するためにどのような種類の技術を用いるのが適切か的確に判断し、優れたアプリケーションのアーキテクチャ基盤を構築するためのツール群の組み合わせ方を理解できるようになることを目指す。

1章 信頼性、スケーラビリティ、メンテナンス性に優れたアプリケーション

ソフトウェアシステムにおける重要な3つの課題

• 信頼性。システムは障害があったとしても正しく動作し続けるべき。
• スケーラビリティ。データ量の増加、トラフィック量の増加などといった成長に対して、無理のない方法で対応可能であるべき。
• メンテナンス性。時間が経つにつれて多くの人が関わるが、それらの人がシステムに生産的に関われるべき。

2章 データモデルとクエリ言語

リレーショナルモデルとドキュメントモデル

ドキュメントデータモデルの良さは以下のような点

1. スキーマの柔軟性
2. ローカリティから来る優れたパフォーマンス
3. データ構造がアプリケーションのものに近い場合がある

特にアプリケーションの構造が一体多の関係からなるツリー構造を持ち、そのツリー全体が通常は一度にロードされる場合、ドキュメントデータモデルを利用するのは良い考えとなる。 その一方で、アプリケーションが多対多の関係を必要とするなら、ドキュメントモデルの魅力は薄れる。

多くのドキュメントデータベースにおけるJsonサポートでは、ドキュメント内におけるスキーマを強制しない。スキーマがないということは、任意のキーとバリューをドキュメントに追加できるということ。スキーマレスという言葉がよく使われるが、厳密には スキーマオンリード （データ構造は暗黙的であり、データの読み取り時に解釈される）であり、逆にリレーショナルデータベースなどでは スキーマオンライト と呼ばれている。スキーマオンリードはドキュメントの構造が統一されていない場合にはメリットとなる。

3章ストレージと抽出

データベースを駆動するデータ構造

データベースから特定のキーの値を効率的に見つけるためにはインデックスが必要となる。インデックスがない場合は O(n) の計算コストがかかり、スケーラブルではない。インデックスは、データから作られる追加のデータ構造として存在している。

インデックスはデータの書き込みのたびに更新する必要があるため、書き込み速度を低下させる。読み出しクエリは高速にしてくれるので、重要なトレードオフとなる。

インデックスの管理方法にはいくつか種類がある。

• ハッシュインデックス。インメモリのハッシュマップの中には、全てのデータに対してデータファイル中のバイトオフセットをマッピングする。こうすることで、ディスクに保存されているファイルのどの場所に目的のデータがあるか検索することができる。ファイルが一定の大きさを超えると、新しくセグメントファイルを作成して新しい書き込みは新しいファイルへと行う。とはいえ、このインメモリハッシュマップがメモリに収まり切る必要がある。
• SSTable（Sorted String Table）。SSTableはファイルの中身がキーでソートされている。この場合は全てのデータをインメモリに持つ必要はない。なぜなら、それぞれのファイルの先頭の単語だけわかれば、どのセグメントファイルにアクセスすれば良いかわかるため。このログ指向ファイルシステムから構築されたインデックス構造はLSMツリー（Log-Structured Merge-Tree）と呼ばれる。
• Bツリー。SSTableと同様に、キーとバリューのペアをキーでソートされた状態で保持する。n個のキーを持つBツリーの深さは常に O(logn) となる。ログ型のインデックス構造とは異なり、データを上書きする。

一般的に、SSTableから構築されたインデックスのLSMツリーは書き込みを高速に処理でき、Bツリーは読み取りが高速に行えるものとみなされている。ただし、LSMツリーではファイルのコンパクション処理が実行中の読み書きに影響を与える場合や、書き込みを受け付けるペースに対してコンパクションが追いつかなくなる可能性に注意が必要となる。

列指向ストレージ

多くのオンライン分析処理データベース（OLAPデータベース）では、ストレージは行指向でレイアウトされている。CSVを想像するとイメージがしやすい。その一方で、データウェアハウスでは列指向ストレージを用いている。一つの行に含まれる値をまとめて保持するのではなく、それぞれの列に含まれる全ての値を保存する。

列指向ストレージの特徴の一つとして、圧縮が容易という点がある。しばしば一つの列の中のuniqueな値は行数に比べて小さくなるので、それに対応するビットマップエンコーディングを行うことで圧縮することができる。

4章 エンコーディングと進化

後方互換性と前方互換性

システムの構築は、変化に容易に適合できるようにするべきである。これを進化性と呼ぶ。システムが進化性を保ち動作し続けるためには、互換性に気をつける必要がある。

• 後方互換性：古いコードによって書かれたデータを新しいコードが読めること
• 前方互換性：新しいコードによって書かれたデータを古いコードが読めること

後方互換性は、新しいコードを書く人が古いデータを知っていれば対応可能。一方で前方互換性は新しいデータで追加された分を古いコードが無視する対応が必要なので比較的難しい。

これらの互換性は、例えばローリングアップデート中を考えるとサポートする必要性をイメージしやすい。

言語固有のフォーマット

Javaの java.io.Serializable Rubyの Marshal Pythonの pickle など、プログラミング言語自体がインメモリオブジェクトをバイト列にエンコードする機能を持つことも多い。これは特定のプログラミング言語と密に結合しており、他の言語でデータを読むのが難しくなってしまう。一時的な目的を除いて、特定の言語の組み込みエンコーディングを使うのは良くない考え。

Json, XML のバイナリエンコーディング

Json と XML はバイナリ文字列をサポートしていない。そのため、Base64を使ってバイナリデータをエンコードする方法が使われる。これは正しく動くが、データサイズが33%増加してしまう。

Json や XML はバイナリフォーマットと比べると多くの容量を使用するため、バイナリエンコーディングも開発されている（例：Jsonにおける MessagePack）。しかし、削減できる容量はわずかであり、それだけのために人間が読めないフォーマットにする価値があるかは怪しい。

Protocol Buffers

Protocol Buffers (protobuf) は Google で開発されたライブラリで、バイナリエンコーディングのライブラリ。エンコードするデータに対するスキーマを必要とする。エンコーディング後のデータはフィールド名をバイト列に含まないという点で、MessagePack のような Json のバイナリエンコーディングと大きく異なる。その代わりに1, 2, 3...という数値がフィールドタグとして割り当てられる。この数値はスキーマ定義に書かれている数値であり、スキーマ定義があることによるフィールド名そのものを書くことなくフィールド名を特定することができる。

Protocol Buffers におけるスキーマの進化

Protocol Buffers はどのようにして後方・前方互換性を保ちつつスキーマの変化を扱うのだろうか。

エンコードされたレコードは単にバイナリエンコードされたフィールドを繋げたものにすぎない。それぞれのフィールドはフィールドタグで識別され、データ型が付与される。つまりフィールドタグが非常に重要。タグを変更するとエンコード済みの既存の全データが不正なものとなってしまうため、フィールド名を変更することはできるがフィールドタグは変更できない。

前方互換性

新しいタグ番号を使用することによって、スキーマには新しいフィールド加えることができる。古いコードでは認識できないタグ番号を持つ新しいフィールドを無視する。参考：https://developers.google.com/protocol-buffers/docs/proto3#updating

後方互換性

古いフィールドは新しいコードでも読み取ることができる。注意が必要なのは、古いフィールドを新しいコードでも読み取るために、新しく追加するフィールドは必須にできないという点。

続き

hiramekun.hatenablog.com

【Scala】Monocleを使ってみたメモ

何の記事か

こちらの『Scala Design Patterns』の11章前半です。

Scala Design Patterns: Design modular, clean, and scalable applications by applying proven design patterns in Scala, 2nd Edition (English Edition)

Lensパターンの実装方法の一つとして scalaz.Lens が紹介されていましたが、他に紹介されていた Monocle を使って書き換えてみようというメモです。

Lensパターンとは

Lensパターンは、ネストが深くなっているオブジェクトの一部だけプロパティを書き換えたい、その一方でイミュータブルなオブジェクトを使用したいときなどに使われます。例えば以下のようなオブジェクトで、User から user.company.address.city.country.code を書き換えようとすると大量のコードを書く必要が出てきます。

classDiagram
  class User {
    +name: String
    +company: Company
    +address: Address
  }
  class Company {
    +name: String
    +address: Address
  }
  class Address {
    +number: Int
    +street: String
    +city: City
  }
  class City {
    +name: String
    +country: Country
  }
  class Country {
    +name: String
    +code: String
  }
  
  User *-- Company
  User *-- Address
  Company *-- Address
  Address *-- City
  City *-- Country

例えばこんな感じにプロパティを一つ書き換えただけなのに、 Country を含むオブジェクトを全てcopyして作り直す必要があります。

val userFixed = user.copy(
  company = user.company.copy(
    address  = user.company.address.copy(
      city = user.company.address.city.copy(
        country = user.company.address.city.country.copy(
          code = user.company.address.city.country.code.toUpperCase
        )
      )
    )
  )
)

そこで役に立つのがLensパターンのようです。変更したいプロパティにレンズを通してフォーカスするイメージらしいのですが、具体的なLensパターンの実装自体は未調査です。

scalaz.Lens

本の中でLensパターンを実現しているライブラリとしてまず紹介されているのは、scalaz.Lens です。Lens[A, B] は LensFamily[A, A, B, B] のエイリアスとなっていました。 LensFamily[A1, A2, B1, B2] は更新前後で型が変わる場合に対応しているのですが、変わらない場合は基本的に Lens[A, B] を使うのが良さそうです。

/**
 * A Lens Family, offering a purely functional means to access and retrieve
 * a field transitioning from type `B1` to type `B2` in a record simultaneously
 * transitioning from type `A1` to type `A2`.  [[scalaz.Lens]] is a convenient
 * alias for when `A1 === A2`, and `B1 === B2`.
 *
 * The term ''field'' should not be interpreted restrictively to mean a member of a class. For example, a lens
 * family can address membership of a `Set`.
 *
 * @see [[scalaz.PLens]]
 *
 * @tparam A1 The initial type of the record
 * @tparam A2 The final type of the record
 * @tparam B1 The initial type of the field
 * @tparam B2 The final type of the field
 */
sealed abstract class LensFamily[A1, A2, B1, B2]

type Lens[A, B] = LensFamily[A, A, B, B]

Lensのgetterとsetterを Lens.lensu(setter, getter) で定義してあげます。lensu の関数定義は以下の通りです。

def lensu[A, B](set: (A, B) => A, get: A => B): Lens[A, B] 

使用する側ではUser -> Company のように、クラス -> クラスのプロパティ という感じで順にアクセスする方法を定義します。

object User {
  val userCompany: Lens[User, Company] = Lens.lensu[User, Company](
    (u, company) => u.copy(company = company),
    _.company
  )

  val userAddress: Lens[User, Address] = Lens.lensu[User, Address](
    (u, address) => u.copy(address = address),
    _.address
  )

  val companyAddress: Lens[Company, Address] = Lens.lensu[Company, Address](
    (c, address) => c.copy(address = address),
    _.address
  )

  val addressCity: Lens[Address, City] = Lens.lensu[Address, City](
    (a, city) => a.copy(city = city),
    _.city
  )

  val cityCountry: Lens[City, Country] = Lens.lensu[City, Country](
    (c, country) => c.copy(country = country),
    _.country
  )

  val countryCode: Lens[Country, String] = Lens.lensu[Country, String](
    (c, code) => c.copy(code = code),
    _.code
  )
}

そして、andThen のエイリアスである >=> を使って繋げてます。こうすることで、User から Country.code までたどることができます。

  val userCompanyCountryCode: Lens[User, String] = userCompany >=> companyAddress >=> addressCity >=> cityCountry >=> countryCode

// こっちは compose を使ったもの。表記が逆になるだけでやってることは同じ。
  val userCompanyCountryCodeCompose: Lens[User, String] = countryCode <=< cityCountry <=< addressCity <=< companyAddress <=< userCompany

Monocle

本の中で具体的に紹介されていたのは scalaz.Lens でしたが、より便利なライブラリとしてお勧めされていた Monocle · Access and transform immutable data を使って書き換えてみようと思います。

まず、Monocleはサイトを見ると Scala 2.13 以降に対応しているようなので、サンプルプロジェクトのScalaのバージョンを2.12から上げます。ScalaTestやMockitoなどのプロジェクトに含まれている他のライブラリのバージョンも、Scalaのバージョンに追従して上げる必要がありました。

scalaVersion := "2.13.8"

libraryDependencies ++=  {
  Seq(
    ...
    "dev.optics" %% "monocle-core"  % "3.1.0",
    "dev.optics" %% "monocle-macro" % "3.1.0",
    ...
  )
}

基本的にはサイトに書いてある通りで、以下のような流れになります。

• foo.focus で foo オブジェクトの持っているプロパティ内部に注目
• focus の中で指定したプロパティを、 modify によって変更
• 変更後のオブジェクトを取得

簡単ですね。

  val ivanFixed = ivan.focus(_.company.address.city.country.code).modify(_.toUpperCase)

暗黙的に AppliedFocusOps に変換しているらしいのですが、中身はマクロで書かれていて理解はまだできませんでした。

出力結果を見ると確かに UK と大文字になっていることが確認できます。

User(Ivan,Company(Castle Builders,Address(1,Buckingham Palace Road,City(London,Country(United Kingdom,uk)))),Address(1,Geneva Lake,City(geneva,Country(Switzerland,CH))))
Capitalize UK code...
User(Ivan,Company(Castle Builders,Address(1,Buckingham Palace Road,City(London,Country(United Kingdom,UK)))),Address(1,Geneva Lake,City(geneva,Country(Switzerland,CH))))

【Scala】Optionモナドをcats.Monadを使って書いてみる

何の記事か

Scala Design Patterns で例として挙げられていた Optionモナドを、 cats.Monad を用いて書き換えてみます。以前 Scala Design Patterns のモナドに関する章を噛み砕いで追いました。

hiramekun.hatenablog.com

では cats の Monad を使うとどのように書けるのだろうか？と思い、色々調べながら実験した内容をメモしました。

cats.Monad

cats.Monad の定義は以下の通りです。

trait Monad[F[_]] extends FlatMap[F] with Applicative[F]

• FlatMap[F] は文字通り flatMap を持つもの
• Applicative[F] は ap と pure を持ち、Functor[F] を継承している。pure は以前のブログでまとめたところの unit に相当する部分だと理解
• Functor[F] は map を提供していることを以前のブログでもまとめている

これを使って Scala Design Patterns にあるように Option モナドを書き換えてみようと思います。

まずはcats公式のサンプルを見てみます。すると、すでに Applicative[Option] が存在する場合の例が載っていました。

If Applicative is already present and flatten is well-behaved, extending the Applicative to a Monad is trivial.

import cats._

implicit def optionMonad(implicit app: Applicative[Option]) =
  new Monad[Option] {
    // Define flatMap using Option's flatten method
    override def flatMap[A, B](fa: Option[A])(f: A => Option[B]): Option[B] =
      app.map(fa)(f).flatten
    // Reuse this definition from Applicative.
    override def pure[A](a: A): Option[A] = app.pure(a)

    @annotation.tailrec
    def tailRecM[A, B](init: A)(fn: A => Option[Either[A, B]]): Option[B] =
      fn(init) match {
        case None => None
        case Some(Right(b)) => Some(b)
        case Some(Left(a)) => tailRecM(a)(fn)
      }
  }

tailRecM は初めて見る関数ですが、これは cats の主張として「Monadを再帰的に処理する場面は多々あり、末尾再帰にしないとスタックオーバーフローが発生するので、Monadを定義する際に強制的に末尾再帰を定義させる」とのことです。

In addition to requiring flatMap and pure, Cats has chosen to require tailRecM which encodes stack safe monadic recursion, as described in Stack Safety for Free by Phil Freeman. Because monadic recursion is so common in functional programming but is not stack safe on the JVM, Cats has chosen to require this method of all monad implementations as opposed to just a subset.

例を見ると、catsのMonadは継承するものではなく引数としてimplicitに与えるイメージのようですね。（なぜ継承ではなく移譲になっているのかは、もう少し理解を深める必要がありそうです。）

書き換えてみる

さて、Applicative の実装は今回のやりたいことから外れるので、Applicative を利用しているところを書き換えていこうと思います。

• flatMap は値が Some だったらその中身に対して受け取った関数を実行すれば良い。
• pure は引数を受け取るコンストラクタなので、Some を返せば良い

以上を踏まえると、今回作る MyOption は次のように定義することができます。

implicit def optionMonad: Monad[MyOption] =
  new Monad[MyOption] {
    override def pure[A](x: A): MyOption[A] = MySome(x)
                                                                                                 
    override def flatMap[A, B](fa: MyOption[A])(f: A => MyOption[B]): MyOption[B] = fa match {
      case MySome(value) => f(value)
      case MyNone() => MyNone()
    }
                                                                                                 
    @tailrec
    override def tailRecM[A, B](a: A)(f: A => MyOption[Either[A, B]]): MyOption[B] = f(a) match {
      case MySome(Right(value)) => MySome(value)
      case MySome(Left(value)) => tailRecM(value)(f)
      case MyNone() => MyNone()
    }
  }

次にこれを実際にどのようにして MyOption から使うのかですが、自分は

• MyOption のコンパニオンオブジェクトに先ほどの optionMonad を implicit に定義し、
• MyOption のコンストラクタに implicit で渡す

ようにしてみました。

object MyOption {
  implicit def optionMonad: Monad[MyOption] = ...
}
sealed class MyOption[A](implicit val optionMonad: Monad[MyOption]) {
  def flatMap[B](f: A => MyOption[B]): MyOption[B] = optionMonad.flatMap(this)(f)

  def map[B](f: A => B): MyOption[B] = optionMonad.map(this)(f)
}

case class MySome[A](value: A) extends MyOption[A]

case class MyNone[A]() extends MyOption[A]

extends MyOption[A] で MyOption[A] のコンストラクタ引数が足りないので、Scalaのコンパイラは implicit に定義されたものを探しに行きます。この時に、コンパニオンオブジェクトの中に含まれている implicit 定義もコンパイラの探索対象となります。

変換のソース型か期待されるターゲット型のコンパニオンオブジェクトの中に含まれているimplicit定義も、コンパイラーの探索対象に入る

Scalaスケーラブルプログラミング 第4版, p.415 より引用

IntelliJの View: Show Implicit Hints を on にすると、暗黙的に渡されているパラメータを表示することができるのですが、それを使うと、きちんと引数に渡されていることが確認できます。

まとめ

使ってあげるとこんな感じになり、map/flatMap が実装されているので for 式でも書くことができます。

object Main {
  def main(args: Array[String]): Unit = {
    val result = for {
      x <- MySome(1)
      y <- MySome(2)
    } yield {
      x + y
    }
    println(result) // MyOption(3)
  }
}

今回作成したMyOptionのコードをまとめると以下のようになります。

（Scala with cats や fpinscala も進めていきたいなあ...）

参考

• Monad - Typelevel.scala
• Applicative - Typelevel.scala
• Scala Cats library for dummies- part 4 | by Idris Kabir | Medium
• Cats | Monad

【因果推論】媒介された影響の排除

こちらの第3章後半です

入門 統計的因果推論

媒介

ある変数が別の変数に影響を与える場合、直接影響を与える場合と間接的に影響を与える場合とが存在し、この二つを分離することは一般的には難しい。間接的な影響のことを、媒介された影響と呼ぶ。

例として、採用に性別による差別が存在するかどうか調査したいとする。今回は以下の4つの変数が関わっているとし、からへの直接的な効果を計測したい。

• : 性別
• : 採用
• : 資格
• : 収入

まず資格について条件付けをする場合を考えてみる。条件付けするというのはつまり、 とを比べるということだ。この二つに差があれば、性別が採用決定に影響を及ぼしていると判断することができる。

しかし、今回のように収入 という交絡因子を含む場合は条件付けによって比べることはできない。なぜなら、資格 で条件づけることによって、 と が と通じて従属になってしまうためだ。（資格 を条件付けするために収入 に影響を及ぼし、収入 が採用 へと影響を及ぼすため。）

であれば、資格 について条件付けをする代わりに、資格を固定すれば良い。変数を固定するのは、他の変数がどんな値を取ろうとも、その値に固定されるという意味であり、その変数に向かう矢印を全て削除することと同義である。

介入と固定に関しては過去記事を参照

hiramekun.hatenablog.com

したがって、今回の場合の直接効果、CDE (controlled direct effect) は以下で定義される。

より一般的に、 が と の間の媒介変数である時、 の値を から に変化させたときの のCDEは

となる。

これは、 について調整することで次のように式変形ができる。

【因果推論】逆確率重み付け法

こちらの第3章後半です

入門 統計的因果推論

以前効果検証入門でも学習していましたが、表記方法や捉え方が異なっていたため、まとめてみました。

hiramekun.hatenablog.com

前提

逆確率重み付け法とは、バックドア基準やフロントドア基準を満たしている共変量 に対して、傾向スコアを持ちいることで効率的に を求める方法である。（下図はバックドア基準を が満たしている例）

バックドア基準やフロントドア基準を使えば、実際に介入することなく効果量を計算することができる。このためには、基準を満たす共変量 を見つけて、調整化公式を適用すれば良い。

ここで調整化公式を思い出すと、いずれも に関して総和を取っている。

• バックドア基準：
• フロントドア基準：

これは、 の取りうる値が大きくなればなるほど計算量は大きくなるということを表している。

傾向スコアと逆確率重み付け法

これを解決するのが、傾向スコア と 逆確率重み付け法 である。

傾向スコアは で表される関数で、効果検証入門によると以下のような意味を持ち、ロジスティック回帰などで求めることができるという。

傾向スコア とは、各サンプルにおいて介入が行われる確率のこと。傾向スコアを用いた分析は、介入が行われた仕組みに注目し、介入グループと非介入グループのデータの性質を近くするする操作を行う。

『効果検証入門』用語まとめ - ひらめの日常

ベイズの法則より、

これ合わせて、調整化公式の の分母分子に傾向スコアをかけて式変形をすると、以下が導出される。

つまり、母集団のそれぞれのケースの確率を、傾向スコアで割れば良い。

※ 『効果検証入門』では確率ではなく期待値を求めていた点などで式の表現が異なっている。

何が嬉しいか

これにより、計算量は調整化公式を用いる時と比べて削減できている。例えば、の取りうる値が数百万あったとする。それに対して、得られたデータが数百件だったとする。この時、

• 調整化公式を用いると、例えばがバックドア基準を満たしていた場合、全てのに対して を計算する必要がある。
• 逆確率重み付け法を用いると、観測されていない は考慮に入れなくて良いため、観測された分のみ計算すれば良くなる。

この辺も後で読みたい

逆確率重み付け（IPW）のイメージ。

まず、簡単な例から答えを準備。飽和モデルでは、ノンパラg-formulaとIPWは一致することを利用します。

共変量Lで条件つけることで交換可能性が成立するとします。
つまりこの時、AとYとの「関連」は、AのYへの「効果」と考えられます。 https://t.co/ugeVA6S7w4 pic.twitter.com/ijthimurXE

— Sato Shuntaro｜佐藤俊太朗 (@Shuntarooo3) March 26, 2022

【Scala】Scala Design Patterns - Chapter10 - Monads

はじめに

『Scala Design Patterns』 という本を、会社の輪読会で呼んでいるのですが、モナド周りの説明が難しかったので自分なりに日本語で咀嚼してみた内容になります。具体的には、『Scala Design Patterns』の265ページ、Chapter10-Monads の内容です。

Scala Design Patterns: Design modular, clean, and scalable applications by applying proven design patterns in Scala, 2nd Edition (English Edition)

ソースコードは出版社のGitHubリポジトリにあります。

github.com

（「モナド何も分からん」から、「モナドちょっと分からん」くらいにはなりました）

Monad の定義

本の中の定義

Monads are functors that have the unit and flatMap methods and follow the monad rules.

ということで、モナドの定義を知るためには Functors とは何かを知る必要がある。

Functorsとは

map メソッドを持ち、以下の決まりに則ったものを呼ぶ。これらを Functor則 と呼ぶことがある。

• Identity: map(x) (i => i) == x
• Composition: map(map(x) (i => y(i))) (i => z(i)) と map(x) (i => z(y(i))) は等しい。
• map メソッドはデータ構造自体を変更することはない。データの表現を変えるだけ。

実際には以下のようなコードが Functor となる。

trait Functor[F[_]] {
  def map[T, Y](l: F[T])(f: T => Y): F[Y]
}

map メソッドが定義されており、F は保ったまま、その中の T を Y へと変換している。

これの具体的な実装は、例えば List の場合以下のようになる。

val listFunctor: Functor[List] = new Functor[List] {
  override def map[T, Y](l: List[T])(f: T => Y): List[Y] = l.map(f)
}

Monadとは

Monads are functors that have the unit and flatMap methods and follow the monad rules.

flatMap, unit, map

• flatMap とは、map した後に flatten すること。
• unit はコンストラクタと同義。
• map は flatMap と unit を用いて表現することができる。
  • f: T => Y の結果を unit で包んであげて、その後で flatten するイメージ。

前節で取り上げた Functor とは異なり、map などの関数の引数としてデータを受け取るのではなく、Functor自体がデータを保持しているとする。モナドの定義から、flatMap を Monad 側に持たせ、map の具体的な実装は Monad 内で flatMap と unit を用いて表している。

trait Functor[T] {
  def map[Y](f: T => Y): Functor[Y]
}

trait Monad[T] extends Functor[T] {

  def unit[Y](value: Y): Monad[Y]
  
  def flatMap[Y](f: T => Monad[Y]): Monad[Y]
  
  override def map[Y](f: T => Y): Monad[Y] =
    flatMap(i => unit(f(i)))
}

モナド則

• Identity law: 恒等写像に対して map をしてもデータは変わらない。また、unit メソッドに対して flatMapをしてもデータは変わらない。unit はモノイドで言うところの単位元。
  • map(x)(i => i) == x
  • flatMap(x) (i => unit(i)) == x

• The unit law

  • unit(x).flatMap { y => f(y) } == f(x)
  • unit(x).map { y => f(y) } == unit(f(x))

• Composition: 複数の map や flatMap は合成することができ、順番によって違いは生まれない。（副作用が生まれる場合はこれが満たされないので注意が必要）

  • x.map(i => y(i)).map(i => z(i)) と x.map(i => z(y(i))) は等しい。
  • x.flatMap(i => y(i)).flatMap(i => z(i)) と x.flatMap(i => y(i).flatMap(j => z(j))) は等しい

何が嬉しいのか

状態を隠蔽して、重要な部分のみに注目することができるようになると書いてある。具体例がないと実感できないので、本に載っている具体例を見てみる。

Monads help us hide this state from the user and just expost the important parts as well as abstract the way we deal with errors, and so on.

具体例

Optionモナド

まずは基底クラスである Option を定義する。

sealed trait Option[A] extends Monad[A]

そして、具体的な実装である Some と None を実装する。

case class Some[A](a: A) extends Option[A] {
  override def unit[Y](value: Y): Monad[Y] = Some(value)
  override def flatMap[Y](f: A => Monad[Y]): Monad[Y] = f(a)
}

case class None[A]() extends Option[A] {
  override def unit[Y](value: Y): Monad[Y] = None()
  override def flatMap[Y](f: (A) => Monad[Y]): Monad[Y] = None()
}

副作用の隠蔽という点では、適していない例のように思う。Some と None を同じtraitから定義し、map, flatMap が定義してあるおかげで for文で書けるという嬉しさはある。

IOモナド

ファイルから行を読み取り、その全てを大文字にしてあtらしいファイルに書き出すプログラムを考える。「状態」として今回は FileIOState の数値をincrementする。

まずはIOの状態を保持する State を定義する。

sealed trait State {
  def next: State
}

IOAction は、古い State から、新しい State と操作の結果のタプルを返す関数を継承している。unit, map, flatMap を実装しており、モナド則を満たしている。

flatMap では、

1. 新しい IOAction を返す。
2. その新しい IOAction は apply で古い IOAction の apply を呼び出し、実行結果として新しい State と結果のタプルを受け取る。
3. 受け取った結果を引数とし、 flatMap で受け取った関数 f: T => IOAction[Y] を実行。
4. 実行した結果の IOAction である action2 に新しい State を渡し、apply を呼び出す。

ここまで全て、flatMap 実行時には呼び出しがされておらず、IOAction#apply が呼び出されて初めて実行されることに注意する。つまり副作用は flatMap 時点では発生していない。

sealed abstract class IOAction[T] extends ((State) => (State, T)) {

  def unit[Y](value: Y): IOAction[Y] = IOAction.unit(value)

  def flatMap[Y](f: (T) => IOAction[Y]): IOAction[Y] = {
    val self = this
    new IOAction[Y] { // 1
      override def apply(state: State): (State, Y) = {
        val (state2, res) = self(state) // 2
        val action2 = f(res) // 3
        action2(state2) // 4
      }
    }
  }

  def map[Y](f: T => Y): IOAction[Y] =
    flatMap(i => unit(f(i)))
}

object IOAction {

  def apply[T](result: => T): IOAction[T] =
    new SimpleAction[T](result)
  
  def unit[T](value: T): IOAction[T] =
    new EmptyAction[T](value)

  // 名前渡しで引数を受け取り、実行時に評価する
  private class SimpleAction[T](result: => T) extends IOAction[T] {
    override def apply(state: State): (State, T) =
      (state.next, result)
  }
  
  // unitを呼び出した時に状態を変えないような実装が必要
  private class EmptyAction[T](value: T) extends IOAction[T] {
    override def apply(state: State): (State, T) = 
      (state, value)
  }
}

具体的な使い方を見る。いずれも IOAction の引数は名前渡しなので、この時点では実行されず、受け取った IOAction に対して apply を呼んだ時に初めて実行される。

package object io {
  def readFile(path: String): IOAction[Iterator[String]] =
    IOAction(Source.fromFile(path).getLines())

  def writeFile(path: String, lines: Iterator[String]): IOAction[Unit] =
    IOAction({
      val file = new File(path)
      printToFile(file) { p => lines.foreach(p.println) }
    })

  private def printToFile(file: File)(writeOp: PrintWriter => Unit): Unit = {
    val writer = new PrintWriter(file)
    try {
      writeOp(writer)
    } finally {
      writer.close()
    }
  }
}

そして、FileIOを実行できるクラスを定義する。State の実装である FileIOState は privateにすることで、外から状態を作れないようにしている。

run でやっていることは、次のような意味になる。

1. runIOで IOAction を定義する。
2. IOaction の apply を、 FileIOStateの初期値を渡して実行する。

action を実行するまで副作用が発生しておらず、副作用を局所化できているのが嬉しい点。

abstract class FileIO {
  
  private class FileIOState(id: Int) extends State { 
    override def next: State = new FileIOState(id + 1)
  }

  def run(args: Array[String]): Unit = {
    val action = runIO(args(0), args(1))
    action(new FileIOState(0))
  }

  def runIO(readPath: String, writePath: String): IOAction[_]
}

実際の使い方としては次の通り。

object FileIOExample extends FileIO {
  
  def main(args: Array[String]): Unit = {
    run(args)
  }
  
  override def runIO(readPath: String, writePath: String): IOAction[_] =
    for {
      lines <- readFile(readPath)
      _ <- writeFile(writePath, lines.map(_.toUpperCase))
    } yield ()
 
  // 以下と同じ
  // override def runIO(readPath: String, writePath: String): IOAction[_] = {
  //   readFile(readPath).flatMap { lines =>
  //     writeFile(writePath, lines.map(_.toUpperCase))
  // }
}

2021年振り返りと2022年のインプット目標

2021年にどんな本を読んだかや、2022年にはどんな本を読みたいかを残しておきます。

一昨年書いたのはこちら。 hiramekun.hatenablog.com

2021年振り返り

去年の目標は24冊だったようです。

24冊読む を目標にやります。現時点で読もうと思っている本を上げておき、随時見直すようにしたいと思います。

途中の本もあるのですが、読み終わった本を数えると実際は 30冊 でした。目標達成ですね、嬉しいです。今年は教育系の本は読書会に参加して読み進めたおかげでコンスタントに消化することができました。他の参加者の方々に感謝です。

その一方で去年後半にだいぶ失速した印象があるので、今年は一年通してモチベーションを高く持ち続けたいですね。

数学/統計

• Rによる教育データ分析入門 (90%)
  • scrapbox.io
• 分析者のためのデータ解釈学入門
• 効果検証入門
  • hiramekun.hatenablog.com
• プログラミングのための線形代数
  • hiramekun.hatenablog.com
• プログラミングのための確率統計

エンジニアリング

• サーバ/インフラを支える技術
• エンジニアの知的生産術
• エンジニアリング組織論への招待
  • hiramekun.hatenablog.com
• レガシーコードからの脱却
  • hiramekun.hatenablog.com
• Javaパフォーマンス
• sbt in Action: The simple Scala build tool

• Akka実践バイブル

  • hiramekun.hatenablog.com
  • hiramekun.hatenablog.com

• Scala Design Patterns: Design modula 2nd Edition (70%)

• イラストでわかるDockerとKubernetes
• 増補改訂版 Java言語で学ぶデザインパターン入門
  • hiramekun.hatenablog.com
• クラウド時代のネットワーク入門
• 日本語スタイルガイド(第3版)
  • hiramekun.hatenablog.com
• 技術者のためのテクニカルライティング入門講座
  • hiramekun.hatenablog.com
• 達人に学ぶSQL徹底指南書 第2版 初級者で終わりたくないあなたへ
• Adaptive Code ~ C#実践開発手法 第2版 (第3部 SOLID原則)
  • hiramekun.hatenablog.com

教育

• OECD Education2030プロジェクトが描く教育の未来:エージェンシー、資質・能力とカリキュラム
  • hiramekun.hatenablog.com
• グラフィック学習心理学―行動と認知
• スタンフォードが中高生に教えていること
• 教育AIが変える21世紀の学び : 指導と学習の新たなかたち
• 教育効果を可視化する学習科学
  • hiramekun.hatenablog.com
  • hiramekun.hatenablog.com
  • hiramekun.hatenablog.com
• 教育は何を評価してきたのか
• 実力も運のうち　能力主義は正義か？
• 子どもがつまずかない教師の教え方10の「原理・原則」
  • hiramekun.hatenablog.com
• 教師崩壊 先生の数が足りない、質も危ない
  • hiramekun.hatenablog.com
• 学力と階層
  • hiramekun.hatenablog.com

その他

• 独学大全
• エッセンシャル思考 最少の時間で成果を最大にする

2022年の目標

2022年はinputもなのですが、自分の中で知識をまとめ直して消化することを意識していきたいです。なので、以下のことに注力します。

• これまでに読んできた本の内容をブログにまとめる
• 仕事で使った知識をアウトプットする

新しい本の目標は7冊程度とします。

数学/統計

• Rによる教育データ分析入門 を読み終わり、内容の概略をまとめる。
• 教育実践データの統計分析
• 入門 統計的因果推論
• 仕事ではじめる機械学習 第2版
• プログラミングのための確率統計 の内容をまとめる
• ゼロからできるMCMC の内容をまとめる

エンジニアリング

• Scala Design Patterns: Design modula 2nd Edition
• 現場で役立つシステム設計の原則
• Javaパフォーマンス の内容をまとめる

教育

教育系の本は、読書会で読み進めるものを随時追加するイメージです。

• 教育DXで「未来の教室」をつくろう

その他

• ヤングケアラー 介護する子どもたち
• インプットではないですが、dotfilesレポジトリの中身を整理しておきたいです。
  • github.com