ガチャピンの引き出し

学んだことをなるべく体系的に纏めて記事にします。

独立性/分離性とトランザクション分離レベル

RDBMSがもつ独立性/分離性(isolation) という特性とトランザクション分離レベル(isolation level) についての記事です。

独立性/分離性(isolation)

複数のトランザクションを同時に実行する前提で、トランザクション中に行われる操作の過程が他の操作から隠蔽される性質のことです。あるデータに対する読み書きを行う場合に、他のトランザクションが処理途中のデータを読み込んでしまうことによって、不都合が生じる可能性があります。このような不都合を発生させないように、複数のトランザクションが同時に実行されても、完了してないトランザクションが他のトランザクションに影響しない特性のことを独立性/分離性と言います。いわゆるACIDのIの部分です。

トランザクション分離レベル(isolation level)

独立性/分離性を完全に保証するには直列処理を行うしかないのですが、それではパフォーマンスがでません。つまり、独立性/分離性とRDBMSの性能はトレードオフの関係にあります。この「直列処理では性能が出ないので、厳密なものを少し諦めつつ緩めていくことで、性能と実用性がいい感じにバランス取れるのでは？」ということを実現するのがトランザクション分離レベルです。

基本的な分離レベルは4つあります。ANSI/ISO SQL標準で定められているものです。

分離レベル ダーティーリード ファジーリード ファントムリード ロストアップデート 性能 内容
SERIALIZABLE ○ ○ ○ ○ 遅 直列処理にする。同時処理しない。
REPEATABLE READ ○ ○ △ × ↓ トランザクション開始時のデータのみ見える。
READ COMMITTED ○ × × × ↓ コミット後の変更のみ見える
READ UNCOMMITTED × × × × 速 コミット前の変更も見える。

速度と独立性/分離性のトレードオフになっているのが確認できます。速度を求めるほど、独立性/分離性が低くなり、他のトランザクションに影響を与える度合いが大きくなります。

RDBMSごとに実装の誤差はあり、MySQLのInnoDBの場合はMVCCを実装していて、REPEATABLE READの場合でもファントムリードは発生しないようになっています。ロストアップデートは発生します。ロストアップデートを防ぐためにFOR UPDATEでロックを取得すると、ファントムリードは発生するようになります。詳細はロストアップデートを試すところに書きます。

ダーティーリード (Dirty Read)

コミット前の書き込みデータを、別のトランザクションが読み込む現象。

ファジーリード (Fuzzy Read)

同一トランザクション内で2度読み込みを行う場合に、別のトランザクションのコミットが原因で、1度読み取ったデータが更新または削除される現象。つまり、同じ問い合わせを繰り返し（リピート）実施しても、同じ結果になることを保証しないという意味。非再現リード(Non-Repeatable Read)とも呼ばれる。

ファントムリード (Phantom Read)

同一トランザクション内で2度読み込みを行う場合に、別のトランザクションのコミットが原因で、1度目の読み取りでは存在しなかったデータが出現すること。ファジーリードがデータの更新(削除)に対する内容であることに対し、ファントムリードはデータの出現である。

ロストアップデート

あるトランザクションで変更した値を、他のトランザクションが上書きして変更すること。先に実施した変更内容は失われる。

実践トランザクション分離レベル (MySQL)

MySQL(5.7.19)を使いながら実際に挙動を確認します。事前に適当なテーブルとデータを作成しましょう。

CREATE TABLE `users` (
  `id` bigint(20) NOT NULL AUTO_INCREMENT,
  `name` varchar(255) DEFAULT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

INSERT INTO users (name) VALUES ('user1'),('user2'),('user3'),('user4'),('user5');

複数のトランザクションを前提にした話なので、クライアントはAとBの2つ立ち上げた状態で試します。

ダーティーリード (Dirty Read)

READ UNCOMMITTEDにしてダーティーリードを再現します。

A & B

mysql> SET SESSION tx_isolation="read-uncommitted";
Query OK, 0 rows affected (0.00 sec)

A

mysql> begin;
Query OK, 0 rows affected (0.00 sec)

mysql> INSERT INTO users (name) VALUES ('user6');
Query OK, 1 row affected (0.00 sec)

B

mysql> select * from users;
+----+-------+
| id | name  |
+----+-------+
|  1 | user1 |
|  2 | user2 |
|  3 | user3 |
|  4 | user4 |
|  5 | user5 |
|  6 | user6 |
+----+-------+
6 rows in set (0.00 sec)

コミット前のデータが別のクライアントから見えていて、実際に取得できていることがわかります。

A

mysql> rollback;
Query OK, 0 rows affected (0.00 sec)

B

mysql> select * from users;
+----+-------+
| id | name  |
+----+-------+
|  1 | user1 |
|  2 | user2 |
|  3 | user3 |
|  4 | user4 |
|  5 | user5 |
+----+-------+
5 rows in set (0.00 sec)

コミット前のデータなので、ロールバックすることでデータが無くなったことを確認できます。次は、READ COMMITTEDにしてダーティーリードが発生しなくなることを確認しましょう。

A & B

mysql> SET SESSION tx_isolation="read-committed";
Query OK, 0 rows affected (0.00 sec)

A

mysql> begin;
Query OK, 0 rows affected (0.00 sec)

mysql> INSERT INTO users (name) VALUES ('user6');
Query OK, 1 row affected (0.00 sec)

B

mysql> select * from users;
+----+-------+
| id | name  |
+----+-------+
|  1 | user1 |
|  2 | user2 |
|  3 | user3 |
|  4 | user4 |
|  5 | user5 |
+----+-------+
5 rows in set (0.00 sec)

さっきは見えていたコミット前のデータが見えなくなりました。後処理でAの方はロールバック。

A

mysql> rollback;
Query OK, 0 rows affected (0.01 sec)

ファジーリード (Fuzzy Read)

READ COMMITTEDにしてファジーリードを再現します。

A & B

mysql> SET SESSION tx_isolation="read-committed";
Query OK, 0 rows affected (0.00 sec)

A

mysql> begin;
Query OK, 0 rows affected (0.00 sec)

mysql> select * from users;
+----+-------+
| id | name  |
+----+-------+
|  1 | user1 |
|  2 | user2 |
|  3 | user3 |
|  4 | user4 |
|  5 | user5 |
+----+-------+
5 rows in set (0.01 sec)

B

mysql> begin;
Query OK, 0 rows affected (0.00 sec)

mysql> update users set name="user100" where id=1;
Query OK, 1 row affected (0.00 sec)
Rows matched: 1  Changed: 1  Warnings: 0

mysql> commit;
Query OK, 0 rows affected (0.00 sec)

A

mysql> select * from users;
+----+---------+
| id | name    |
+----+---------+
|  1 | user100 |
|  2 | user2   |
|  3 | user3   |
|  4 | user4   |
|  5 | user5   |
+----+---------+
5 rows in set (0.00 sec)

同一トランザクション内で、他のトランザクションがコミットした内容が反映され、新しいデータを取得できました。次はREPEATABLE READにしてファジーリードが発生しないことを確認しましょう。

その前に、後処理。

A

mysql> rollback;
Query OK, 0 rows affected (0.01 sec)

では、REPEATABLE READにして確認しましょう。

A & B

mysql> SET SESSION tx_isolation="repeatable-read";
Query OK, 0 rows affected (0.00 sec)

A

mysql> begin;
Query OK, 0 rows affected (0.00 sec)

mysql> select * from users;
+----+-------+
| id | name  |
+----+-------+
|  1 | user1 |
|  2 | user2 |
|  3 | user3 |
|  4 | user4 |
|  5 | user5 |
+----+-------+
5 rows in set (0.00 sec)

B

mysql> begin;
Query OK, 0 rows affected (0.00 sec)

mysql> update users set name="user100" where id=1;
Query OK, 1 row affected (0.01 sec)
Rows matched: 1  Changed: 1  Warnings: 0

mysql> commit;
Query OK, 0 rows affected (0.01 sec)

A

mysql> select * from users;
+----+-------+
| id | name  |
+----+-------+
|  1 | user1 |
|  2 | user2 |
|  3 | user3 |
|  4 | user4 |
|  5 | user5 |
+----+-------+
5 rows in set (0.00 sec)

mysql> rollback;
Query OK, 0 rows affected (0.00 sec)

mysql> select * from users;
+----+---------+
| id | name    |
+----+---------+
|  1 | user100 |
|  2 | user2   |
|  3 | user3   |
|  4 | user4   |
|  5 | user5   |
+----+---------+
5 rows in set (0.00 sec)

同一のトランザクション内ではファジーリードは発生していないことが確認できます。トランザクションを抜けて、再度データを確認すると、他のトランザクションがcommitしたデータが取得できました。

ファントムリード (Phantom Read)

上述の通り、InnoDBの場合はREPEATABLE READでは発生しないので、READ COMMITTEDで再現を行います。

A & B

mysql> SET SESSION tx_isolation="read-committed";
Query OK, 0 rows affected (0.00 sec)

A

mysql> begin;
Query OK, 0 rows affected (0.00 sec)

mysql> select * from users;
+----+---------+
| id | name    |
+----+---------+
|  1 | user100 |
|  2 | user2   |
|  3 | user3   |
|  4 | user4   |
|  5 | user5   |
+----+---------+
5 rows in set (0.00 sec)

B

mysql> begin;
Query OK, 0 rows affected (0.00 sec)

mysql> INSERT INTO users (name) VALUES ('user6');
Query OK, 1 row affected (0.00 sec)

mysql> commit;
Query OK, 0 rows affected (0.00 sec)

A

mysql> select * from users;
+----+---------+
| id | name    |
+----+---------+
|  1 | user100 |
|  2 | user2   |
|  3 | user3   |
|  4 | user4   |
|  5 | user5   |
|  8 | user6   |
+----+---------+
6 rows in set (0.00 sec)

同一トランザクション内で、他のトランザクションから新規追加されたデータを取得できました。次はSERIALIZABLEにしてファントムリードが発生しないことを確認しましょう。

後処理を忘れずに。

A

mysql> rollback;
Query OK, 0 rows affected (0.01 sec)

では、SERIALIZABLEに変更しましょう。

A & B

mysql> SET SESSION tx_isolation="serializable";
Query OK, 0 rows affected (0.00 sec)

A

mysql> begin;
Query OK, 0 rows affected (0.00 sec)

mysql> select * from users;
+----+---------+
| id | name    |
+----+---------+
|  1 | user100 |
|  2 | user2   |
|  3 | user3   |
|  4 | user4   |
|  5 | user5   |
|  8 | user6   |
+----+---------+
6 rows in set (0.00 sec)

B

mysql> begin;
Query OK, 0 rows affected (0.00 sec)

mysql> INSERT INTO users (name) VALUES ('user7');
ERROR 1205 (HY000): Lock wait timeout exceeded; try restarting transaction

直列なので、Aのトランザクションが終わるのを待って、B側がタイムアウトしています。

ロストアップデート

少し本筋と逸れますが、ロストアップデートにも触れておきましょう。MySQLのREPEATABLE READはMVCCを実装しているので一貫性読み取りは実現しているが、完全な一貫性読み取りは実現しておらず、読み取り処理だけであれば大きな問題はないのですが、更新を伴う場合は特に気をつける必要があります。

よく聞くロックとらないと危険だよねーという、そんな話です。

REPEATABLE READで試します。

A & B

mysql> SET SESSION tx_isolation="repeatable-read";
Query OK, 0 rows affected (0.00 sec)

トランザクションを開始。

A

mysql> begin;
Query OK, 0 rows affected (0.00 sec)

mysql> select * from users where id = 1;
+----+---------+
| id | name    |
+----+---------+
|  1 | user100 |
+----+---------+
1 row in set (0.00 sec)

Bでもトランザクションを開始して、UPDATEをかける。

B

mysql> begin;
Query OK, 0 rows affected (0.00 sec)

mysql> select name into @x from users where id = 1;
Query OK, 1 row affected (0.00 sec)

mysql> update users set name=concat(@x, 'B') where id=1;
Query OK, 1 row affected (0.00 sec)
Rows matched: 1  Changed: 1  Warnings: 0

mysql> commit;
Query OK, 0 rows affected (0.01 sec)

mysql> select * from users where id = 1;
+----+----------+
| id | name     |
+----+----------+
|  1 | user100B |
+----+----------+
1 row in set (0.00 sec)

A側でもUPDATEをかける。

A

mysql> update users set name=concat(@x, 'A') where id=1;
Query OK, 1 row affected (0.01 sec)
Rows matched: 1  Changed: 1  Warnings: 0

mysql> commit;
Query OK, 0 rows affected (0.00 sec)

mysql> select * from users where id = 1;
+----+----------+
| id | name     |
+----+----------+
|  1 | user100A |
+----+----------+
1 row in set (0.01 sec)

AでUPDATEしたことにより、BでUPDATEしていた内容が消えてなくなりました。これがロストアップデートです。FOR UPDATEを使う、または SERIALIZABLEにすることでSELECT毎に行ロックを取ることで解決します。

上記の例では故意的にselectして値を保持しているので、値を保持しないで良いような簡単なものであればUPDATEだけで解決しますが、アプリケーションを実装していると必ずしもそういうものばかりでは無いはずです。

FOR UPDATEを使うことで、REPEATABLE READ では発生しなかったはずのファントムリードが発生する状態になります。試してみましょう。

FOR UPDATEを使ってREPEATABLE READ でファントムリードを発生させる

A & B

mysql> SET SESSION tx_isolation="repeatable-read";
Query OK, 0 rows affected (0.00 sec)

A

mysql> begin;
Query OK, 0 rows affected (0.00 sec)

mysql> select * from users;
+----+----------+
| id | name     |
+----+----------+
|  1 | user100A |
|  2 | user2    |
|  3 | user3    |
|  4 | user4    |
|  5 | user5    |
|  8 | user6    |
|  9 | user7    |
+----+----------+
7 rows in set (0.00 sec)

B

mysql> begin;
Query OK, 0 rows affected (0.00 sec)

mysql> INSERT INTO users (name) VALUES ('user8');
Query OK, 1 row affected (0.00 sec)

mysql> commit;
Query OK, 0 rows affected (0.00 sec)

A

mysql> select * from users;
+----+----------+
| id | name     |
+----+----------+
|  1 | user100A |
|  2 | user2    |
|  3 | user3    |
|  4 | user4    |
|  5 | user5    |
|  8 | user6    |
|  9 | user7    |
+----+----------+
7 rows in set (0.00 sec)

mysql> select * from users for update;
+----+----------+
| id | name     |
+----+----------+
|  1 | user100A |
|  2 | user2    |
|  3 | user3    |
|  4 | user4    |
|  5 | user5    |
|  8 | user6    |
|  9 | user7    |
| 13 | user8    |
+----+----------+
8 rows in set (0.00 sec)

REPEATABLE READの場合において、通常のselectではファントムリードは発生していないが、FOR UPDATEを使うことでファントムリードが発生していることがわかる。これはInnoDBのREPEATABLE READではその時の最新の値、つまり最も新しいバージョンが読み取られるという仕様だからだそうだ。

全てを防ぐ必要がある場合はやはりSERIALIZABLEにするのが良いが、性能をはじめとしたトレードオフがあるので、状況に応じた選択をする必要がありそうですね。

他のトランザクション分離レベル

Snapshotなどをはじめとした他の分離レベルもあるようです。ひとまずは基礎として上記4つを抑えれば良いと思いますが、せっかくなのでリンクでご紹介させて頂きます。

まとめ

データの読み書きが複数同時に走った時に不都合が発生しないような特性を独立性/分離性と言い、全てを直列処理することで独立性/分離性を保証できますが、性能とのトレードオフがあるため、トランザクション分離レベルが用意されています。トランザクション分離レベルは複数存在し、その設定を変更することで性能と独立性/分離性を良い按配に設定できます。

参考

Scalaで型クラスとアドホック多相

某純粋関数型言語に触れた事がある方はきっと知っている型クラス。今回はScalaで実際のコードを使いながら、具体的にどんなものなのかを説明します。

型クラスとは

関数型言語でアドホック多相を実現するために存在します。

アドホック多相なので、オブジェクト指向言語で近いものはオーバーロードです。
インターフェースと良く比較されますが、オブジェクト指向言語で言うインターフェースは部分型多相を実現するものなので、多相という概念レベルで実現したいことが違います。

多相についてはこの記事に書いていますので、ぜひご覧頂けますと。

thashiii.hatenablog.com

オーバーロードとの違いとして、オーバーロードが既存の型を拡張するのに対し、型クラスは共通のインターフェース(関数)を定義し、既存の型を拡張せずに静的に振る舞いを追加するところです。

この定義された共通のインターフェース(関数)を型クラス、実装している型のことを型クラスのインスタンスと言います。

余談ですが、オブジェクト指向言語で言う型やクラスとは異なるので、一旦忘れましょう。クラスを知っているが故に混乱するというパターンが凄く多いです。私もそうでした。。。orz

Scalaで型クラスに入門する

Scalaはハイブリッドな言語なので、オーバーロードと型クラスの両方でアドホック多相を実現することができます。

まずは簡単な関数の例として、show関数の実装を見てみましょう。

def show(a: String): String = a

scala> show("hello")
res0: String = hello

String型を引数にとって、そのまま返却しています。簡易例なので特に難しくもない普通(?)の関数です。String型専用の関数なので、Int型を引数に取ることができません。

String型専用では困るので、Int用の関数を定義してみます。

def show(a: Int): String = a.toString

scala> show(1)
res1: String = 1

scala> show("hello")
<console>:13: error: type mismatch;
 found   : String("hello")
 required: Int
       show("hello")
            ^

同じ関数名なので、Int型を受け付ける関数を定義したことにより、String型を受けつける関数を上書きしてしまいました。StringとIntの両方に対応したいので、関数名を変えましょう。

def showString(a: String): String = a
def showInt(a: Int): String = a.toString

scala> showString("hello")
res3: String = hello

scala> showInt(1)
res4: String = 1

違う名前で関数を定義することで、StringとIntの両方に対応しました。但し、これでは多相とは言いません。それぞれの実装(具象型)に対して、呼び出し元が直接依存して、意識して関数を呼び出しています。全く抽象化できていません。

この課題を解決するのがアドホック多相であり、オーバーロードであり、型クラスです。

オーバーロード

オーバーロードはオブジェクト指向言語でアドホック多相を実現するものです。上記のshow関数の例をオブジェクト指向な方法で実現してみましょう。

class Shower {
  def show(a: String): String = a
  def show(a: Int): String = a.toString
}

scala> val s = new Shower()
s: Shower = Shower@67c61551

scala> s.show("hello")
res5: String = hello

scala> s.show(1)
res6: String = 1

オブジェクト指向なので、データと振る舞い(実装)を1つにしたクラスを定義します。 show関数を持ったオブジェクトのインスタンスを生成し、そのオブジェクトを通してshow関数を呼び出すことで様々な型に対応できます。

アドホック多相のみは実現できていますが、既存の型を拡張しています。自作の型に対しては実現できそうですが、StringやIntなどの標準の型やライブラリで定義されている型を拡張することはできません。

※ アドホック多相の簡易例なので、Mixinやtraitなどを用いた説明は実施しません。

型クラス

型クラスは関数型言語でアドホック多相を実現するものです。show関数での例を見てみましょう。

trait Show[A] {
  def show(a: A): String
}

def show[A](a: A)(implicit x: Show[A]): String = x.show(a)

implicit val ShowString: Show[String] = new Show[String] {
  def show(a: String): String = a
}
implicit val ShowInt: Show[Int] = new Show[Int] {
  def show(a: Int): String = a.toString
}

scala> show("hello")
res10: String = hello

scala> show(1)
res11: String = 1

一般的に普及しているオブジェクト指向はクラスベースなので、あくまでクラスが主役で、そのクラスに関数を生やしました。型クラスは関数型な解決方法なので、関数が主役です。
show関数が主役なので、show関数とは何かをまず定義します。例で言うtraitの部分です。それに付随してString型の場合はshowString、Int型の場合はshowIntと引数の型ごとの関数の振る舞い(実装)を定義することができます。

Scalaではtraitでインターフェースを定義し、引数で渡ってきた型を見て、暗黙的に実行する処理を決めています。その結果、show関数という1つの名前で複数の型に対応でき、その処理は共通のインターフェースで定義されたものになっています。

※ このStringやIntのようにshow関数を実行できる型のことを型クラスのインスタンスと言います。

オブジェクト指向のように、オブジェクトに対してメソッドとして生やすような処理にすることもできます。

implicit class ShowOps[A](a: A) {
  def show(implicit x: Show[A]): String = { x.show(a) }
}

scala> "hello".show
res2: String = hello

scala> 1.show
res3: String = 1

こうすることで、StringやIntなどの標準の型を拡張せずに、振る舞い(実装)を追加できていることが確認できます。

オープンクラスと拡張関数 (オマケ)

アドホック多相に限らず、既存の型(標準のString型やInt型を含む)を拡張できる機能と言えば、真っ先に思いつくのがRubyのオープンクラスとKotlinの拡張関数ですね。

・Rubyのオープンクラス

class String
  def show
    self
  end
end

class Integer
  def show
    self.to_s
  end
end


irb(main):016:0* "hello".show()
=> "hello"

irb(main):034:0> 1.show()
=> "1"

・Kotlinの拡張関数

fun String.show() = this
fun Int.show() = this.toString()

>>> "hello".show()
hello

>>> 1.show()
1

どちらも既存の型を直接拡張せずに振る舞い(実装)を外から追加しています。Kotlinではオーバーロードがあるので、拡張関数とインターフェースの両方を組み合わせることで型クラスに限りなく近いことができそうです。Rubyはオーバーロードがそもそも無いそうです。動的言語ですし、それはそれで正しい気がします。

既存の型に対して振る舞い(実装)を追加できますが、あくまでオブジェクト指向ベースです。クラスがあって、そのクラスに外から関数を追加し、オーバーロードでアドホック多相を実現はできます。一方で、型クラスは関数を定義して、その関数を実行できるオブジェクト(型クラスのインスタンス)と振る舞いを定義します。

主がオブジェクトなのか関数なのかというのは細かい違いかもしれませんが、型クラスを理解するのに重要な要素です。

まとめ

型クラスの概念から実装までをScalaを用いて学びました。 論文を元にした型クラスの歴史などは、私も詳しくはないのですが、必要十分なレベルで型クラスのイメージを掴んで頂けたのではないでしょうか。 オブジェクト指向言語の文脈で理解しようとせず、関数型な考え方とアドホック多相を実現するものだという視点を持つことで、理解が進みます。ぜひ、今後の設計や新しい言語の理解に役立つ記事になっていますと幸いです。

ポリモーフィズム再入門

実は、ポリモーフィズムが複数存在することをご存知でしょうか。

Javaの入門書であったり、オブジェクト指向について学んでいると必ず遭遇しますが、とっつきづらく、あまり理解していない(する必要もないかも)という場面に良く出会います。

この記事では、言語機能と照らし合わせながら、文字だけでない実践に近い形で、複数のポリモーフィズムを紹介します。

ポリモーフィズムとは

ポリモーフィズム（polymorphism / 多相性）とは、複数の異なる型に対して、共通のインタフェースを提供すること です。つまり、抽象化の話になります。実装を定義する具象型(実装)とは別に、抽象的なインターフェースを用意することで、具象型(実装)を持ちつつも、共通のインターフェースを通じて処理を実行できます。

※ 余談ですが、オブジェクト指向言語の持つ性質/概念の一つという説明も見ますが、オブジェクト指向言語に限った話ではなく、関数型言語にも多相性の概念は存在します。

いろんなポリモーフィズム

ポリモーフィズム（polymorphism / 多相性）にも種類があります。
言語機能としては利用しているが、ポリモーフィズムだと意識していない物も(もしかしたら)あるかもしれません。以下に代表的なものを列挙しましたので、是非ご一読下さい。

部分型(サブタイプ)多相 subtype polymorphism

共通の上位型をもつ複数の型を、1つの名前で扱うような多相を部分型(サブタイプ)多相と言います。オブジェクト指向言語の文脈で、単にポリモーフィズム と言うと部分型(サブタイプ)多相のことです。入門書などで取り上げられ、継承やインターフェースを用いる最も見慣れたものです。

abstract class Animal { def cry() }

class Dog extends Animal { def cry() = println("ワン") }
class Cat extends Animal { def cry() = println("ニャー" )}

val animals:List[Animal] = List(new Dog(), new Cat())

scala> animals.foreach(_.cry)
ワン
ニャー

Dog型やCat型などの具象型ではなく、Animal型という抽象型を通して関数を呼び出しています。Animal型は広義でのインターフェースなので、具象型が何かを気にすることがなく関数を呼び出すことができます。

構造的部分型のようなダック・タイピングで多相を実現するケースもあるので、必ずしも継承が必要な訳ではありません。

パラメータ多相 Parametric polymorphism

型に依存しない共通の振る舞い・性質を定義し、型の情報は引数(型パラメータ)で受け取ります。このような多相をパラメータ多相と言います。いわゆるGenerics（ジェネリクス／総称型）のことで、型パラメータAと何らかの振る舞い・性質をセットにした型を生成します。代表例はリストです。

val animals:List[Animal] = List(new Dog(), new Cat())

良く見る例ですが、List[A] に対し、 Animalを型パラメータとして渡しています。
他にもFuture[A] は将来A型の値を保持する可能性のある型で、Option[A] はA型の値を保持するか何も保持していない型のことです。

List[A] 、Future[A] 、Option[A] のように型パラメータを受け取り、具体的な型を返す型のことを 型コンストラクタと言います。

以下にミニマムな実装例を載せます。

def f[A](x: A) = x

scala> f[Int](1)
res6: Int = 1

scala> f[String](1)
<console>:13: error: type mismatch;
 found   : Int(1)
 required: String
       f[String](1)

class MyCollection[A](var v: A) {
  def set(a: A) = { v = a }
  def get(): A = v
}

scala> val c = new MyCollection[Int](1)
c: MyCollection[Int] = MyCollection@5c4cc644

scala> c.get()
res0: Int = 1

scala> c.set(10)

scala> c.get()
res2: Int = 10

scala> c.set("hello")
<console>:13: error: type mismatch;
 found   : String("hello")
 required: Int
       c.set("hello")

アドホック多相 Ad hoc polymorphism

ある関数が、引数の型によって異なる振る舞い(実装)を持つような多相のことをアドホック多相と言います。オブジェクト指向言語のオーバーロードや、関数型言語の型クラスなどがそれに該当します。

オーバーロード

同じ名前の関数を引数だけ変えて複数定義します。対応している言語であれば、これだけで実現できます。

class Dog { 
  def cry() = println("ワン") 
  def cry(s: String) = println(s) 
}

scala> val dog = new Dog()
dog: Dog = Dog@55c581e4

scala> dog.cry()
ワン

scala> dog.cry("ニャー")
ニャー
型クラス

型クラス自体の説明は、逸脱した内容なので割愛します。
実行結果を見ると、同じ関数で引数が違う場合に、振る舞いが変わっていることが確認できます。
狭義でのインターフェースとよく比較されますが、インターフェースが部分型(サブタイプ)多相を実現するものに対し、型クラスはアドホック多相を実現するものです。

trait Show[A] {
  def show(a: A): String
}

// 関数として実行用
def show[A](a: A)(implicit x: Show[A]): String = x.show(a)

// 型クラスのインスタンス
implicit val ShowString: Show[String] = new Show[String] {
  def show(a: String): String = a
}
implicit val ShowInt: Show[Int] = new Show[Int] {
  def show(a: Int): String = a.toString + "!"
}

scala> show("aaa")
res0: String = aaa

scala> show(1)
res1: String = 1!

// メソッドとして生やす
implicit class ShowOps[A](a: A) {
  def show(implicit x: Show[A]): String = { x.show(a) }
}

scala> "aaa".show
res2: String = aaa

scala> 1.show
res3: String = 1!

高階多相 higher-order polymorphism

パラメータ多相の拡張版で型コンストラクタを型引数に取るような多相のことを高階多相と言います。 型コンストラクタを引数にとる型コンストラクタのことで、代表例はファンクターです。

trait Functor[F[_]] {
 def fmap[A, B](f: F[A])(g: A => B): F[B]
}

型コンストラクタは、型パラメータを引数に取って型を返す型のことで、代表例はリストです。List[String], List[Int] と利用しますが、ファンクターはFunctor[List], Functor[Option] のように型コンストラクタ(F[_])を与えることができます。
単純なパラメータ多相では、型コンストラクタを引数に取ることはできません。このようなパラメータ多相の拡張版が高階多相です。

高カインド多相（higher-kinded polymorphism）などとも呼ばれ、現状では決まった呼ばれ方は存在しないようです。私は高階多相 or 高カインド多相と呼ぶ事にしています。

まとめ

今回はポリモーフィズム（polymorphism / 多相性）について纏めました。
ポリモーフィズムにも種類があり、どの多相性を実現するための言語機能かを意識する事で、捉え方や視点が変わります。
例えば、型クラスとインターフェースの違いなどが話題にあがりますが、多相性という概念レベルで違うものを実現しようとしている事を知れば、違いをよりイメージしやすくなるでしょう。

型クラスやファンクターなど、この記事では書ききれないような内容については別記事を書きます。それでは！

参考

参考にさせて頂いた先輩方ありがとうございます。

モノイドで畳み込み

関数型プログラミングに出てくるモノイド(Monoid)という概念に触れてみる。

モノイドとは

単位元(ゼロ値) と 型を結合するための二項演算子(2引数関数) を持つ型のこと。 型の結合を抽象化するため、畳み込みなどで力を発揮する。

Haskellでの定義。

class Monoid a where
  mempty  :: a
  mappend :: a -> a -> a
  mconcat :: [a] -> a
  mconcat = foldr mappend mempty

単位元をmempty 、二項演算子をmappendと定義している。

Haskellの場合は、標準の型クラスとして定義され、mconcatも定義に含まれる。 mconcatは、モノイドのリストを受け取り、その全てを結合した結果を返す関数である。foldrで右畳み込みする処理がデフォルトとして実装されている。デフォルト実装で十分なケースがほとんどの為、memptyとmappendを定義するだけで、新たなモノイドを作成できる。

Scalaでモノイド

Scalaの標準機能ではないので、自作する or Scalazを使おう。

trait Monoid[A] {
  def mempty: A
  def mappend(a: A, b: A): A
}

シンプルなモノイド

シンプルなモノイドでイメージを掴もう。数値を足し算するモノイド、文字列連結するモノイド、リストを連結するモノイドの例を実装する。

trait Monoid[A] {
  def mempty: A
  def mappend(a: A, b: A): A
}

val IntMonoid: Monoid[Int] = 
    new Monoid[Int] {
      def mempty: Int = 0
      def mappend(a: Int, b: Int): Int = a + b
    }

val StringMonoid: Monoid[String] = 
    new Monoid[String] {
      def mempty: String = ""
      def mappend(a: String, b: String): String = a + b
    }

def ListMonoid[A]: Monoid[List[A]] = 
    new Monoid[List[A]] {
      def mempty: List[A] = List.empty
      def mappend(a: List[A], b: List[A]): List[A] = a ::: b
    }


scala> IntMonoid.mempty
res0: Int = 0

scala> IntMonoid.mappend(1, 2)
res1: Int = 3

scala> StringMonoid.mempty
res2: String = ""

scala> StringMonoid.mappend("a", "b")
res3: String = ab

scala> ListMonoid.mempty
res4: List[Nothing] = List()

scala> ListMonoid.mappend(List(1, 2), List(3))
res5: List[Int] = List(1, 2, 3)

モノイドで畳み込み

シンプルなモノイドを畳み込み処理に利用してみる。

trait Monoid[A] {
  def mempty: A
  def mappend(a: A, b: A): A
}

object Monoid {
  implicit val IntMonoid: Monoid[Int] = 
    new Monoid[Int] {
      def mempty: Int = 0
      def mappend(a: Int, b: Int): Int = a + b
    }

  implicit val StringMonoid: Monoid[String] = 
    new Monoid[String] {
      def mempty: String = ""
      def mappend(a: String, b: String): String = a + b
    }

  implicit def ListMonoid[A]: Monoid[List[A]] = 
    new Monoid[List[A]] {
      def mempty: List[A] = List.empty
      def mappend(a: List[A], b: List[A]): List[A] = a ::: b
    }
}

def sum[A: Monoid](xs: List[A]): A = {
  val m = implicitly[Monoid[A]]
  xs.foldLeft(m.mempty)(m.mappend)
}


scala> sum(List(1, 2, 3))
res0: Int = 6

scala> sum(List("a", "b", "c"))
res1: String = abc

scala> sum(List(List(1, 2, 3), List(4, 5, 6),  List(7, 8, 9)))
res2: List[Int] = List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9)

それぞれ定義したモノイドの通りに畳み込み(結合)できていることが分かる。
渡された引数の型によって振る舞いが変わるのは型クラス(アドホック多相)の話になるが、モノイドを定義し、その定義されたモノイドを使って畳み込み(結合) が実現できた事が分かる。

(追記) 型クラスの記事を書きました。thashiii.hatenablog.com

まとめ

モノイドは型の結合を抽象化し、単位元(ゼロ値) と 二項演算子(結合するための関数) を持っていることが分かった。
Haskellでは標準の型クラスとして存在し、Scalaでも例のように実現することができる。
使い所は畳み込み処理で、Haskellではデフォルトの実装(foldr)が提供されている。

参考

Pythonとsum関数で学ぶラムダ式と高階関数

この記事は、Pythonとsum関数を使って、ラムダ式と基本的な高階関数を学びつつ、あわよくば関数型プログラミングに入門しちゃおうという趣旨の記事です。

sum関数とは

要素の合計を出力する関数です。Pythonの標準関数にも存在します。

>>> sum([1, 2, 3, 4, 5])
15

sum関数を実装してみる

もし、sum関数を自作するとなった場合、どんな実装が考えられるでしょうか。
※ 上記サンプルと同じで、引数はint型のリストに限定します。

......

............

実装できましたでしょうか？

スタンダードな実装だと、こうでしょうか。

def sum(xs):
  result = 0
  for i in xs:
    result += i
  return result

再帰で書くと、こうでしょうか。

def sum(xs):
  if not xs:
    return 0
  return xs[0] + sum(xs[1:])

スタンダードな答えが一番多そうですね。再帰で答えた方は少なかったのではないでしょうか。どちらも良く見る優秀な解の1つだと思います。

ただし、ここで1つお伝えすることがあります。

そう。この記事のゴールは、ラムダ式と高階関数を使って関数型スタイルなsum関数を実装することです。

つまり、上記の答えだけでは、NG...とまではいかずとも物足りないような状況です。

この記事では、関数型なスタイルにまだ触れたことがない方が、実際に触れてみて、関数型プログラミングを知る。そのきっかけになればと思って書きました。

それでは、実際に見ていきましょう。

※ 既に関数型な答えをイメージされた方に関しては、この記事でお伝えできることは多分ないです。「いいね」だけ押して頂いた後、閉じて頂いても大丈夫です(笑)

ラムダ式

ラムダ式を用いることで無名関数(名前のない関数)を作成できます。
一般的に、高階関数の引数として渡す為の名前が不要な小さな関数を作成するのに用います。

>>> def plus(x, y):
...     return x + y
...
>>> f = lambda x, y: x + y # 変数への代入はPEP8では非推奨
>>>
>>> plus(1, 2)
3
>>> f(1, 2)
3

通常の関数は、事前定義なしに引数として渡すことはできませんが、ラムダ式(無名関数) であれば可能です。

>>> def exec(f, x): return f(x) # 高階関数。plus1関数や無名関数を受け取り実行する。
...
>>> def plus1(x): return x + 1
...
>>>
>>> exec(lambda x: x + 1, 1) # ラムダ式(無名関数)は直接埋め込むことができる
2
>>> exec(plus1, 1) # 事前定義した関数は渡すことができる
2
>>> exec(def plus1(x): return x + 1, 1) # 関数は直接埋め込むことができない
  File "<input>", line 1
    exec(def plus1(x): return x + 1, 1)
           ^
SyntaxError: invalid syntax
>>>

このように、名前がいらないような小さな関数(処理)を、関数定義せず引数として渡すような使い方をします。

難しいと言われ、煙たがられるシーンをたまに見ますが、決してそんなことはありません。いつも使っている関数に名前がないだけなんです。

ちなみに、ラムダ式で書く場合はreturnは不要です。

高階関数

Pythonでは関数自体を変数に代入したり、引数として受け取ったり、戻り値として返すことができます。 *1

この関数を引数として受け取る関数や関数を戻り値として返す関数 のことを高階関数 と言います。
代表的な高階関数としてmap filter reduce があります。

map関数

関数 と リスト を受け取り、リストの各要素に関数を適用した新しいリストを返す関数です。
各要素に特定の処理を行いたい場合に利用します。

# REPL表示用にlist関数を利用しています。

# 1を足す
>>> list(map(lambda x: x + 1, [1, 2, 3, 4, 5]))
[2, 3, 4, 5, 6]

# 2乗する
>>> list(map(lambda x: x ** 2, [1, 2, 3, 4, 5]))
[1, 4, 9, 16, 25]

# 文字を含んだタプルにする
>>> list(map(lambda x: (x, str(x)), [1, 2, 3, 4, 5]))
[(1, '1'), (2, '2'), (3, '3'), (4, '4'), (5, '5')]

filter関数

真偽値(bool)を返す関数 と リスト を引数に受け取り、条件に合う要素を抽出したリストを返す関数です。
特定の条件に合う要素を抽出したい場合に利用します。

# REPL表示用にlist関数を利用しています。

# 偶数
>>> list(filter(lambda x: x % 2 == 0 , [1, 2, 3, 4, 5]))
[2, 4]

# 3以上
>>> list(filter(lambda x: x >= 3 , [1, 2, 3, 4, 5]))
[3, 4, 5]

# ゼロ値
>>> list(filter(lambda x: not x, [True, False, 1, 0, "a", "", [], [1,2,3]]))
[False, 0, '', []]

reduce関数

2つの値を受け取り1つの値を返す関数と リスト を受け取り、1つの値を返す関数です。
リストを纏めて1つの値にしたい時(例: 合計値が欲しい時など)に利用します。
一般的に畳み込みと呼ばれたりします。 reduceではなくfoldと呼ぶ人も多いです。

>>> from functools import * # Python3

# 掛ける
>>> reduce(lambda x, y: x * y, [1, 2, 3, 4, 5])
120

# 文字列連結
>>> reduce(lambda x, y: str(x) + str(y), [1, 2, 3, 4, 5])
'12345'

これだけでも必要十分なのですが、実はreduce関数には3つ目の引数があります。
この第3引数はアキュムレータと呼ばれています。
畳み込みに初期値を設定できるものだと思って頂ければOKです。

>>> from functools import * # Python3

# 初期値を100
>>> reduce(lambda x, y: x * y, [1, 2, 3, 4, 5], 100)
12000

# 初期値を空文字 初期値の型が入ったので、x側のstr関数が不要になる。
>>> reduce(lambda x, y: x + str(y), [1, 2, 3, 4, 5], '')
'12345'

ちなみに、reduceの処理は以下相当なコードになります。 とっつきづらい人は、これをイメージして頂けると良いと思います。

result = 0                    # 初期値
for i in [1, 2, 3, 4, 5]:     # リスト 
    result += i               # 処理(関数適用)
return result                 # 戻り値

糖衣構文(シンタックスシュガー)だと言いたいが、書き方的に相当怪しいので控える。

map / filter / reduce を合わせて使ってみる
>>> from functools import * # Python3

# 1〜10までの偶数の積を出す
>>> reduce(lambda x, y: x * y, filter(lambda x: x % 2 == 0 , range(1, 11)))
3840

# 100までの整数のうち7の倍数のみを2乗し、文字列連結する
>>> reduce(lambda x, y: x + "/" + str(y), map(lambda x: x ** 2, filter(lambda x: x % 7 == 0 , range(1, 101))), '')
'/49/196/441/784/1225/1764/2401/3136/3969/4900/5929/7056/8281/9604'

このように、高階関数( map / filter / reduce) を使うことで、リスト *2 に対して任意の関数を適用し、多彩な操作を行う事ができます。

実行する関数を入れ替えるだけで、振る舞いを変え、違う結果を得る事ができます。

sum関数を関数型スタイルで実装してみる

ラムダ式と高階関数は難しかったでしょうか？ それとも簡単でしたか？

これで基礎は終えたので、最後にsum関数を作ってみましょう。

おさらいすると、sum関数は要素の合計を出力する関数です。
※ 今回は、引数をint型のリストに限定しています。

リストの合計値ということは、畳み込みを行い、リストから1つの値を算出する必要がありそうです。

畳み込みに使う関数はどんな関数でしょうか？

int型のリストの合計を出力したいので、2つの数値を足し算する関数ですね。

lambda x, y: x + y # 2つの数値を足し算する関数

と

reduce(f, [1,2,3,4,5]) # fの関数を使って畳み込む処理

が必要そうですね。

これを元に、sum関数を作成すると、おそらくこうなるのではないでしょうか。

from functools import * # Python3

def sum(xs):
    return reduce(lambda x, y: x + y, xs)

うん。凄く簡単でシンプルですね。

これで手続き型や再帰を使わないsum関数を作ることができました。

まとめ

今回は、ラムダ式と高階関数からsum関数の実装を通して、関数型プログラミングの一部に触れました。

もちろん、関数型プログラミングは、ラムダ式や高階関数だけでなく奥が深いものだとは思います。

一方で、普段、手続き型やオブジェクト指向型なプログラミングのみを行っている方には新鮮で面白いものになっているのではないでしょうか。 (そうなっていたら良いなと思います。)

今回は焦点を絞った基礎的な内容でしたが、是非、興味があれば、これをきっかけに関数型プログラミングの世界に足を踏み入れて頂けると嬉しいです。

さいごに

この記事で何かしらの学びがあったよーという方、是非いいねを押して頂けると嬉しいです。

それではまた。

*1: 関数が`ファーストクラスオブジェクト、第一級オブジェクト、第一級関数。他のデータ同様に変数に代入したり引数として渡したりできる。

*2: 厳密にはリストだけではなくPythonに限るとiterableなオブジェクト。