序文

二十年ほど前、私はイギリスで初めての仕事に就いた。職場へは電車で通勤する必要があったため、一日に一時間ほど邪魔の入らない読書の時間を得ることができた。初めて『計算機プログラムの構造と解釈』のことを耳にしたのは、ちょうどその頃である。この本は表紙の絵柄から「魔術師本（Wizard Book）」とも呼ばれ、開発者たちのあいだで特別な敬意をもって語られていた。学校を卒業したばかりの、優れた開発者を目指していた自分にとって、それはまさに最適な一冊のように思われた。私はその本を購入し、通勤のあいだに読み進めた。ほとんどの演習問題は頭の中で解いた。『計算機プログラムの構造と解釈』は当時すでに古典であり、そのプログラミングスタイルは時代遅れだったが、その核心となる概念は時代を超えるものだった。それはまさに衝撃的で、自分の進む道を決定づけるきっかけとなった。私はその道をいまでも歩み続けている。

その道程におけるもうひとつの重要なできごとは、十年ほど前に Dave とともに『Scala with Cats』の執筆を始めたことである。同書では Cats ライブラリに含まれる主要な型クラスとそれらを用いたソフトウェア構築について解説しようとした。私たちがともに書き上げたこの本には誇りを感じている。だが、時を経て経験を重ねるうちに、型クラスは関数型プログラミングによるソフトウェア構築というパズルの一片にすぎないことが明らかになった。関数型プログラミングが提供するすべてのツールを活用してソフトウェアを効果的に構築する方法を示すには、対象範囲をもっと広げなければならない。とはいえ、一冊の本を書くのは大変な作業であり、私たちが他のプロジェクトに忙殺されていたこともあり、『Scala with Cats』は何年ものあいだほとんど手を加えられないままだった。

2020年ごろ、もう一度『Scala with Cats』に取り組みたいという気持ちが私の中に湧いてきた。当初の計画は、Scala3 に対応させるための単なる改訂にすぎなかった。Dave は他の仕事で忙しかったため、私は単独で執筆を進めることにした。だが、執筆を進めるうちに、前著に欠けていた話題を盛り込みたいと思っている自分に気づいた。『Scala with Cats』が良い本だったとすれば、今回は素晴らしい本を目指したかった。私がソフトウェア構築について学んできたことのほぼすべてを詰め込んだ一冊にしたかった。その内容にとって『Scala with Cats』というタイトルはもはやふさわしくなかったので、内容に見合った新しい名前を採用した。その『Functional Programming Strategies in Scala with Cats』こそ、いまあなたが読んでいるこの本である。この本があなたの助けとなることを願っている。そして、かつて私が『計算機プログラムの構造と解釈』に心を打たれたように、若い開発者の心を動かす本になれば幸いである。

『Scala with Cats』版 序文

本書の目的はふたつある。第一に、モナド、ファンクター、およびその他の関数型プログラミングのパターンを、プログラム設計の構造化手法として紹介すること。第二に、それらの概念が Cats においてどのように実装されているかを知ってもらうことである。

関数型プログラミングにおけるモナドやそれに関連する概念は、オブジェクト指向でいうところのデザインパターンに相当する。いずれも、アーキテクチャ上の構成要素として、コードの中に繰り返し登場する。ただし、オブジェクト指向のパターンとは主に次の二点において異なる。

• 定義が形式的であり、それゆえ正確であること
• 極めて（本当に極めて）一般性が高いこと

この一般性の高さゆえに、これらの概念は理解しづらいものになっている。抽象概念は誰にとっても難しい。しかし、モナドなどの概念がこれほど多様な場面に応用できるのは、この一般性のおかげでもある。

本書では、これらの概念がどのように機能しどこで使えるのかというメンタルモデルを構築できるよう手助けしたい。そのためにこれらの概念をさまざまな角度から見ていく。具体的には、発展的なケーススタディやいくつもの小さな例、簡潔な図式表記、そしてもちろん数学的な定義も用意している。どれかひとつでも読者のみなさんの理解の助けになるものがあれば幸いである。

では、始めよう。

バージョンについて

本書は Scala 3.3.4 および Cats 2.10.0 を対象として書かれている。 以下に、必要な依存関係と設定を含んだ最小限の build.sbt を示す¹。

scalaVersion := "3.3.4"

libraryDependencies +=
  "org.typelevel" %% "cats-core" % "2.10.0"

scalacOptions ++= Seq(
  "-Xfatal-warnings"
)

テンプレートプロジェクト

準備の手間を省けるよう Giter8 テンプレートを用意している。以下のコマンドでテンプレートをクローンできる。

$ sbt new scalawithcats/cats-seed.g8

このコマンドにより、依存ライブラリとして Cats を含んだサンドボックスプロジェクトが生成される。生成された README.md を参照すれば、サンプルコードの実行方法や、インタラクティブな Scala コンソールの起動手順を確認できる。

この cats-seed テンプレートは最小限の構成になっている。もっと多くのライブラリやツールを含んだ構成から始めたい場合は、Typelevel の sbt-catalysts テンプレートを利用するとよいだろう。

$ sbt new typelevel/sbt-catalysts.g8

このコマンドにより、単体テストやドキュメントのテンプレートに加えて、複数の依存ライブラリやコンパイラプラグインを備えたプロジェクトが生成される。詳細については catalysts および sbt-catalysts のプロジェクトページを参照してほしい。

本書の表記

本書には技術的な情報やプログラムコードが多数含まれている。文章構成を明確にし、重要な概念を強調するために、以下のような表記規約を用いる。

表記規約

新たに導入される用語や語句はイタリック体で示す。初出以降は通常フォントで表記される。

プログラムコード中の用語、ファイル名、ファイルの内容は、等幅フォント（monospace font） で表記する。単数形と複数形の区別はしていない点に注意してほしい。たとえば java.lang.String を指して String や Strings と表記することがある。

外部リソースへの参照はハイパーリンクによって示される。API ドキュメントへの参照は、scala.Option のようにハイパーリンクと等幅フォントを組み合わせて表記する。

ソースコード

ソースコードのブロックは次のように記述される。可能な場合はシンタックスハイライトが適用される。

object MyApp extends App {
  println("Hello world!") // Print a fine message to the user!
}

ほとんどのコードは mdoc を通じて処理され、コンパイル可能であることが保証されている。 mdoc は内部的に Scala コンソールを使用するため、ときには出力をコメント形式で示すこともある。

"Hello Cats!".toUpperCase
// res2: String = "HELLO CATS!"

強調枠

特定の内容を際立たせるために、次の二種類の強調枠（callout box）を使用する。

ライセンス

本書は CC BY-SA 4.0 の下でライセンスされている。ライセンスの全文は http://creativecommons.org/licenses/by-sa/4.0/ にて閲覧できる²。

本書の一部は、Dave Pereira-Gurnell および Noel Welsh による『Scala with Cats』を元にしている。同書は CC BY-SA 3.0 の下でライセンスされている。

1 関数型プログラミング戦略

これは、関数型プログラミングの流儀でコードを書くための戦略について、Scala を通して捉え、解説した本である。もし、Scala についてはほぼ理解しているものの、この言語を効果的に用いる方法に何か不足を感じているのであれば、この本はあなたに最適だろう。また、Scala についてあまり知らない場合でも、関数型プログラミングの学習の一環として Scala を学ぶ心構えができているなら、そんなあなたにもこの本は適している。この本では、モナドやモノイドといった一般的な関数型プログラミングの抽象概念を扱うが、それ以上に、関数型プログラマらしい思考方法について教えることを目指している。思考の結果としてのコードだけでなく、思考過程について記述しており、特に私がメタ認知的プログラミング戦略と呼ぶものに焦点を当てている。

ほとんどのプログラマは、自分がコードを発想し記述するプロセスを説明せよと言われても戸惑うのではないだろうか。一部の人は「テスト駆動開発」や「ペアプログラミング」を挙げるかもしれないが、一般的なプログラマからそれ以上の説明を期待するのは難しいだろう。それらのテクニックはどちらも90年代後半に登場したエクストリームプログラミングに由来している。その後、この分野に新たな知見が積み重ねられていることを期待したが、現実はそうではなかったようだ。とはいえ、これは開発者の責任というより、彼らの多くが明示的な手法を教えられていないことに原因がある。IT業界は確かにアジャイルやカンバンボードなどの形でプロセスについて語ることが好きだし、近年ではプログラミング教育の対象を拡げるために大変な努力が費やされている。しかし、実際のプログラミング、つまりシステム開発の要であるコードを生み出す部分は、いまだに魔法のように扱われることが多い。

関数型プログラマは単純なアイデアを言い表すのに難解な言葉を使いたがる。だから、私が「メタ認知的プログラミング戦略」に惹かれるのも当然だろう。このフレーズの意味を解き明かしてみよう。「メタ認知」とは「考えることについて考える」という意味である。多くの研究が、学習におけるメタ認知の有益性と、それが専門性を養うための重要な要素であることを示している。ただし、メタ認知を「自分の考えについて考える」というひとつの事柄として大雑把に捉えるだけでは不十分である。解像度を上げれば、メタ認知されるのはさまざまな戦略の集まりであり、一般的なものもあれば、特定の分野に特化したものもある。ここから「メタ認知的プログラミング戦略」という概念が生まれる。これは、熟練したプログラマが使用するさまざまな思考戦略に、明確に名前と説明をつけるということである。

メタ認知的プログラミング戦略は、初心者にも熟練者にも有益だと私は考えている。初心者に対しては、プログラミングをより体系的で再現可能なプロセスにすることができる。ほとんどの場合、コードを生み出すのに魔法は不要となり、明確に定義された手順を適用すればよくなる。その利点はそのまま熟練者にも当てはまる。少なくとも私の経験ではそうだった（私は専門家を名乗るに十分な期間プログラムを書いてきたと思っている）。明確なプロセスがあれば、毎日それを同じ方法で実行すればよい。コードの読み書きはシンプルになり、脳のリソースをもっと重要な問題に集中させることが可能となる。ある意味、これは製造業、特に「トヨタ方式」がもたらしたプロセスや標準化の利点をプログラミングにもちこもうとする試みだと言える。トヨタのプロセスでは、作業者が自分の仕事の進め方を考え、それをどう改善できるか思考することが求められる。これは実質的に、組み立てラインにおけるメタ認知である。これは、作業者が日々の業務に全神経を集中させる必要がなく、思考に余裕があってはじめて可能となる。トヨタが先駆けた自動車製造における生産性と品質の劇的な向上は、このアプローチの有効性を示している。ソフトウェア開発は自動車製造ほど一様ではないが、それでも同様の恩恵が期待できるだろう。特に、現在の業界がまだ未熟な状態であることを考えればなおさらである。

次に問題となるのは、どのようなメタ認知的戦略が利用可能であるか、である。その答えを考えるのに関数型プログラミングが特に適していると私は考えている。関数型プログラミング研究の主要なテーマは、役立つコード構造を発見し、名前を付けることである。有用な抽象概念が発見され普及すれば、プログラマが何か問題に直面したときに、その抽象概念でその問題を解決することができるかどうか検討可能になる。これは90年代にデザインパターンのコミュニティが行ったことと本質的には同じだが、重要な違いがある。それは、関数型プログラミングの学術的コミュニティが形式的なモデルを非常に重視しているため、関数型プログラミングの構成要素はデザインパターンが欠いている精密さをもっていることである。とはいえ、プログラミングのプロセスは、単に完成したコード構造の分類にとどまらず、コードがどのように発想されてくるかという現実的な過程を含む。コードは通常、完全な形でキーボードから生まれるわけではなく、反復的な精緻化の中で構造を見出される。この点に関して関数型プログラミングの学術コミュニティはあまり語っていないが、「型駆動開発」などの技法に関する強い実践的な知恵がある。

私は、プログラミングおよびプログラミング教育を行う中で、過去10年ほどにわたり幅広く戦略を集めてきた。それらの中には他者から学んだものもあるし、自分自身で発見したものもある。たとえば、『How to Design Programs』やその多くの派生書から大きな影響を受けている。だが、突き詰めると、ここで紹介する内容に真新しいものはない。私の貢献は、これらの戦略を一か所にまとめて提示することにある。

1.1 コードを考えるための三つのレベル

それでは、プログラミングについて考えることについて考えていこう。コードについて考えるための三つの異なるレベルを記述したモデルを用いる。それらのレベルとは、上から順にパラダイム（paradigm）、理論（theory）、そして技法（craft）である。各レベルは、それより下位のレベルに対して指針を提供してくれる。

パラダイムレベルとは、オブジェクト指向や関数型プログラミングといったプログラミングパラダイムのことを指す。これらの用語には馴染みのある方も多いと思うが、プログラミングパラダイムとは一体何だろうか。私にとって、プログラミングパラダイムの核心は、よいコードとはどういうものかを緩やかに定める一連の原則である。また、「これらの原則に従ったコードは、そうでないコードよりも優れている」という暗黙の主張もパラダイムには含まれている。関数型プログラミングにおける原則は合成（composition）と推論（reasoning）であると私は考えている。このふたつの原則については改めて説明する。一方、オブジェクト指向プログラマは、たとえば SOLID 原則をコーディングにおける意思決定の指針として挙げるかもしれない。

パラダイムは、異なる実装戦略の中からいずれかを選ぶための基準を示してくれるという点で重要である。プログラミングの課題には多くの解決策が存在するが、どのアプローチを取るべきかを、パラダイムによって示される原則にもとづいて判断することができる。たとえば、関数型プログラマであれば、特定の実装についてどれだけ簡単に理解し実行結果を予測できるか、それがどれだけ合成可能であるかを検討するだろう。パラダイムがないというのは、そういった選択を行うための基準がないということである。

理論レベルでは、パラダイムのもつ概略的な原則が具体的で明確に定義されたテクニックに翻訳される。それらのテクニックは、パラダイム内の多くの言語に適用できるが、この段階でもまだコードレベルの具体性はもたない。オブジェクト指向の世界では、デザインパターンがその一例であり、関数型プログラミングにおいては、代数的データ型がその一例である。多くの関数型プログラミング言語、たとえば Haskell や O’Caml は代数的データ型をサポートしているし、マルチパラダイム言語である Rust、Scala、Swift なども同様にサポートしている。

プログラミング戦略の大部分は理論レベルにおいて見出される。

技法レベルでは、具体的なコードや、それに関連する言語固有のニュアンスを取り扱う。Scala における例として、代数的データ型は Scala2 では sealed trait と final case class を使って実装され、Scala3 では enum で実装される。このレベルには、Scala でコンパニオンオブジェクトにコンストラクタを配置するなど、上位レベルには存在しなかった、慣用的なコードを書くための多くの考慮事項が存在する。

次節では関数型プログラミングのパラダイムについて説明し、本書の残りの部分では主に理論と技法に焦点を当てる。理論は特定の言語に依存しないが、技法は Scala に特化したものとなる。関数型プログラミングのパラダイムへと進む前に、ふたつの点を強調しておきたい。

1. パラダイムは社会的構築物であり、時間とともに変化する。現在のオブジェクト指向プログラミングは、元々 Simula や Smalltalk で使用されていた流儀とは異なるし、今日の関数型プログラミングも、初期の LISP のコードとは大きく異なる。

2. この三層構造は、あくまで思考のためのツールに過ぎない。現実の世界はもっと複雑である。

1.2 関数型プログラミング

この本は、関数型プログラミングの技法と実践について書かれている。ここで、関数型プログラミングとは何か、そして関数型の流儀でコードを書くとはどういうことか、という疑問が当然に生じる。関数型プログラミングを、ファーストクラス関数のような言語機能の集合として捉えたり、不変データと純粋関数を使うプログラミングスタイルとして定義したりするのは一般的で（純粋関数とは、同じ入力に対して常に同じ出力を返す関数のこと）、私も当初はそのように考えていた。だが、今では、関数型プログラミングの核心は局所推論（local reasoning）と合成（composition）であると考えている。言語機能やプログラミングスタイルは、これらの目標を達成するための手段に過ぎない。次に、局所推論と合成の意味と価値について説明しよう。

1.2.1 関数型プログラミングとは何か

関数型プログラミングはソフトウェア品質に関する仮説であると私は考えている。実行する前に理解できるソフトウェア、そして小さく再利用可能なコンポーネントで構築されたソフトウェアの方が、書くことも保守することも容易だという考え方である。前者の特性は「局所推論」として知られており、後者は「合成」と呼ばれている。

局所推論とは、コードの一部を他から切り離して理解できるということを意味する。たとえば、1 + 1 という式は、天気やデータベースの状態、現在の Kubernetes クラスタの状況に関係なく、その意味を理解可能である。外部要因が式の意味を変えることはない。この例は単純ですこし滑稽だが、要点をよく表している。関数型プログラミングの目標のひとつは、この特性をコード全体に拡げることである。

局所推論について理解しようとするなら、それが何でないかを考えることが役立つかもしれない。可変状態を共有していると局所推論はできなくなる。なぜなら、共有された状態に依存すると、そのコードの動作を他のコードが知らないうちに変えてしまう可能性があるからである。敷衍すると、多くのウェブフレームワークやグラフィックスライブラリに見られるような、グローバルな可変の設定オブジェクトも使うことができない。使えば、任意のコードがその設定を変更できてしまう。また、メタプログラミングも慎重に管理する必要がある。モンキーパッチも他のコードが明示的でない方法でコードを変更できてしまうので、避けるべきである。このように、局所推論が可能となるようコードを適応させるには、かなり大きな変更が必要になることがある。しかし、関数型プログラミングを取り入れた言語で作業するのであれば、このプログラミングスタイルが基本となる。

合成とは、小さなものを組み合わせて大きなものを作ることを指す。たとえば、数は合成可能である。どんな数でも、1を足せば新しい数が得られる。レゴもまた合成可能である。ブロック同士をくっつけることで組み立てることができる。ここで我々が指している合成という概念では、組み合わせる元となる要素が、合成をしたあとも変化しないことが求められる。たとえば、1 と 1 を足して 2 を作るとき、その結果として新しい数が得られるが、この操作は1そのものの意味を変えるわけではない。

よくあるプログラミングのタスクをモデル化する合成的手法は、探してみると結構見つかる。多くのフロントエンド開発者に馴染みのある例としては、React コンポーネントがある。React コンポーネントは、複数のコンポーネントを組み合わせて作成することができる。また、HTTP ルートも合成的手法でモデル化される。ひとつのルートとは、HTTP リクエストからハンドラ関数、もしくはルートが一致しなかったことを示す値へとマッピングする関数で、ルートを論理和として組み合わせることで、特定のルートが一致しなければ別のルートを試す、という挙動を実現する。パイプライン処理にも順次的な合成がよく利用される。パイプラインのあるステージを最初に実行し、その後に別のステージを実行する、というものである。

1.2.1.1 型

型は厳密には関数型プログラミングの一部ではないが、関数型言語の中でも静的型付けされたものがもっともよく用いられているので、言及しておく価値がある。型はコンパイラが効率的なコードを生成するのを助けるが、関数型プログラミングにおける型はコンパイラだけでなくプログラマのためのものでもある。型はプログラムの特性を表現し、型チェッカーはそれらの特性が守られていることを自動的に保証してくれる。たとえば、関数が何を受け取り、何を返すかや、ある値がオプションであるといったことを型が示してくれる。さらに、プログラムに対する自分の仮定を型で表現し、型チェッカーにそれが正しいかどうかを確認してもらうこともできる。たとえば、コードのある場所においてエラーは発生しないと想定していることを型でコンパイラに伝えることができる。型チェッカーはそれが正しいかどうかを教えてくれる。このように、型はコードに対する推論を行うためのもうひとつのツールとなる。

型システムはプログラムを特定の設計へと導く。型チェッカーと効果的に連携するためには、型チェッカーが理解できる作法でコードを設計することが要求されるからである。洗練された型システムが多くの言語に導入されるにつれて、それらの言語を使うプログラマは自然と関数型プログラミングのスタイルへと移行する傾向がある。

1.2.2 関数型プログラミングは何でないか

私の考えでは、関数型プログラミングの本質は不変性や「評価の置換モデル」などではない。これらは、局所推論と合成を可能にするための手段に過ぎず、目的ではないのである。たとえば、不変なコードは常に局所推論を可能にするが、可変性を避けなくても局所推論を行うことはできる。整数のコレクションを合計する例を考えてみよう。

def sum(numbers: List[Int]): Int = {
  var total = 0
  numbers.foreach(x => total = total + x)
  total
}

この実装では total 変数の値を変更しているが、問題はない。そのような操作が行われていることは外部からはわからないし、sum の利用者は引き続き局所推論を行うことができる。sum の内部では total に関して慎重に考察する必要があるが、このコードブロックは十分に小さいため、特に問題を引き起こすことはないだろう。

この場合、可変変数を使いながらも、我々はコードについて推論できるし、Scala コンパイラもこれを問題なしと判断できる。Scala は可変性を認めており、これを適切に使用するかどうかはプログラマに委ねられている。より表現力のある型システム、たとえば Rust のような機能を持つ型システムであれば、sum がシステムの他の部分から観測される変更を認めていないことを保証できるだろう³。可変性を全面的に禁止することによって問題が生じないことを保証するアプローチもある。Haskell はこの方法を採用している。

可変性は合成にも影響を与える。たとえば、ある値が内部状態に依存している場合、それを合成すると予期しない結果を生む可能性がある。Scala の Iterator を考えてみよう。Iterator は次の値を生成するために内部状態を保持している。ふたつの Iterator があり、それらを組み合わせてふたつの入力から値を返す Iterator を作りたいと思ったとする。このような合成をするには zip メソッドを使う。

この合成は、ふたつの別々のジェネレータを zip に渡せば、正しく動作する。

val it = Iterator(1, 2, 3, 4)

val it2 = Iterator(1, 2, 3, 4)

it.zip(it2).next()
// res3: Tuple2[Int, Int] = (1, 1)

だが、同じジェネレータを二度使用すると、期待と異なる結果になる。

val it3 = Iterator(1, 2, 3, 4)

it3.zip(it3).next()
// res4: Tuple2[Int, Int] = (1, 2)

関数型プログラミングにおける一般的な解決策は可変状態を避けることだが、他の方法も考えられる。たとえば、エフェクト追跡システムを使用すれば、同じメモリ領域を使用するふたつのジェネレータの組み合わせを避けることができる。しかし、これらのシステムはまだ研究段階にある。

私の考えでは、不変性（および純粋性や参照透過性、そして覚えていないが何とかというもっと難解な概念）が関数型プログラミングと結びついているのは、それらが局所推論と合成を保証するからである。そして、最近まで、可変性の安全な使い方と問題を引き起こす使い方を自動的に区別できる言語ツールは存在しなかった。不変性の制約を受け入れることは、関数型プログラミングの望ましい特性を確保するためのもっとも簡単な方法だが、言語が進化するにつれて、これが過去の遺物と見なされる可能性もある。

1.2.3 なぜ重要なのか

局所推論と合成について述べてきたが、その利点についてはまだ触れていない。これらが望ましいとされる理由は、それによって知識を効率的に活用できるからである。この点について詳しく説明しよう。

局所推論が重要なのは、コードベースの規模が大きくなっても、コードを理解する能力がスケールするからである。モジュールAとモジュールBをそれぞれ単独で理解できるなら、それらがひとつのプログラム中で一緒に用いられたとしても、その理解が変わることはない。定義上、AとBの両方が局所推論を可能とする場合、B（または他のコード）がAについての理解を変えることはないし、その逆も同じことが言える。もし局所推論ができなければ、新しいコードを1行追加するごとに、既存のコード全体を再確認して何が変わったのかを理解する必要が生じる。コードは、サイズが大きくなり、相互作用（およびそれに伴うかもしれない挙動）の数が急増するにつれて、理解するのが指数関数的に難しくなる。局所推論は合成的であると言える。モジュールAによるモジュールB呼び出しを理解したいなら、AおよびB、そしてAがBに対して行う呼び出しの内容を理解するだけでよい。

数とレゴを合成の例として見てきたが、これらには共通する興味深い性質がある。それらを組み合わせる操作（たとえば、数の場合は加算や減算、レゴの場合は「ブロックをくっつける」操作）を行うと、操作前と同じ種類のものが得られるという点である。数に数を掛ければ結果は数になるし、ふたつのレゴをくっつけたものも依然としてレゴである。この性質は閉包性と呼ばれ、ものを組み合わせたときに同じ種類のものが得られることを意味する。閉包性があるということは、合成操作（時にはコンビネータとも呼ばれる）を任意の回数適用できることを意味する。どれだけ1を足しても結果は数であり、さらに加算や減算、乗算を行うことができる。モジュールAについて理解しており、Aによって提供されるコンビネータが閉包性を持っていれば、新しい概念を学ばなくとも、Aを使って非常に複雑な構造を作ることができる。これは、関数型プログラマがモナドのような抽象概念を好む理由のひとつでもある（単に難しい言葉が好きだからではない）。これらの抽象概念は、ひとつのメンタルモデルをさまざまなコンテキストで使うことを可能にしてくれる。

ある意味、局所推論と合成は同じコインの裏表のような関係にある。局所推論は合成的であり、合成は局所推論を可能にする。どちらもコードを理解しやすくしてくれる。

1.2.4 重要性のエビデンス

ここまで関数型プログラミングを支持する議論を行ってきたが、その考えに偏りがあることを認めよう。私はたしかに関数型プログラミングのほうが命令型プログラミングよりも優れたコード開発手法であると信じている。しかし、その主張を裏付けるエビデンスは存在するだろうか。関数型プログラミングの有効性についての研究はあまり行われていないが、静的型付けに関しては十分な研究がなされている。静的型付け、特に洗練された型システムを用いるケースは、関数型プログラミングのよい代替指標となると考えられるので、そのエビデンスについて見ていこう。

私がよく訪れるインターネットの片隅では、静的型付けが生産性に与える影響はほとんどないという声がよく聞かれた。しかし、調査してみたところ、静的型付けが生産性を向上させるという主張を支持する結果が多数見られることに驚いた。たとえばこの論文の文献レビュー（第2.3節、16〜19ページ）は、特に最新の研究を中心に静的型付けを支持する結果が多いことを示している。ただし、Dan Luu がレビューで言及しているとおり、これらの研究の多くは規模が小さく、比較的経験の浅い開発者を対象としている。私の考えでは、関数型プログラミングの真価は大規模なシステムで発揮される。また、プログラミング言語は他のツールと同様に、効果的に使用するためには熟練が必要である。経験の浅い開発者が言語間の有意差を示すのに十分なスキルをもっているかは疑わしい。

私が思うに、関数型プログラミングの有効性を示すもっとも使えそうなエビデンスは、ビジネスの現場で関数型プログラミングが広く採用されているという事実である。たとえば TypeScript や React の採用が広範囲に拡大を続けていることを考えてみるとよい。TypeScript や React によって体現されている関数型プログラミングが無価値だと言うなら、それらの技術へと移行した何千人もの JavaScript エンジニアが思い違いをしていると主張することになる。そのような主張はいずれ説得力を失うだろう。

これはもちろん、5年後に我々がみんな Haskell を使っているという意味ではない。むしろ、90年代のオブジェクト指向プログラミングへの移行に似たものとなる可能性が高い。Smalltalk はオブジェクト指向の典型例だったが、オブジェクト指向を開発現場の主流へと押し上げたのは、C++ や Java のような身近な言語だった。関数型プログラミングの場合、おそらく Scala、Swift、Kotlin、Rust などの言語や、JavaScript や Java のような主流言語が引き続き関数型の特徴を取り入れていくことになるだろう。

1.2.5 導入の最後に

ここまで、関数型プログラミングについて私見を述べてきた。私の考えでは、関数型プログラミングの本質的な目標は局所推論と合成であり、不変性などのプラクティスは目標を実現するための手段でしかない。この定義に異論を唱える人もいるかもしれないが、それはそれでかまわない。言葉はそれを用いるコミュニティによって定義され、意味は時とともに変化するものである。

関数型プログラミングが形式的な推論を重視していることにはいくつかの含意が伴う。それについて簡単に触れておきたい。

第一に、私の経験上、関数型プログラミングの価値がもっとも発揮されるのは、大規模なシステムにおいてである。小規模なシステムでは、詳細をすべて脳内に留めておくことができる。プログラムが大きくなり誰も全体を理解できなくなったときこそ、局所推論は真価を発揮する。小規模なプロジェクトに関数型プログラミングを使うべきではないと言っているのではない。プログラミングスタイルを命令型から関数型へ切り替えたとしても、おもちゃのような小規模プロジェクトではその利点を実感しにくいだろうということである。

関数型プログラミングの基礎にある形式モデルは、コードを体系的に組み立てることを可能にしてくれる。書かれたコードからその性質や振る舞いを抽出するのではなく、あるべき性質からコードを導くのだから、これはある意味で推論とは真逆の営みである。これは学術的に聞こえるかもしれないが実際にはとても実践的であり、私自身がコードを書く際に用いる手法でもある。

最後に、推論はコードを理解する唯一の方法ではない。推論の限界や、コードを理解するための他の手法、そして状況に応じたさまざまな戦略について理解することが重要である。

本書の最初のパートでは基盤となる戦略を構築していく。それ以降の部分は、基盤となるその戦略の上に構築され練り上げられていく。2章ではデータモデリングの主要な手段である代数的データ型について見ていく。3章では余データについて取り扱う。これは、代数的データの反対、別の言い方をすれば双対となるものである。型クラスについては4章で、そしてインタープリタの基礎については5章で議論する。以上4つの戦略はすべてコードの構造を記述するものである。たとえば、コードのある部分を指して、ここに書かれているのが代数的データ型であるとか型クラスであるとかとラベル付けすることができる。また、型に従うといった、コードを書く上で役立つが直接コードに反映されるわけではない戦略も登場する。

2 代数的データ型

この章では、プログラミング戦略の最初の例として代数的データ型（algebraic data type）を取り上げる。論理積と論理和を使って表現できるデータはすべて代数的データ型である。代数的データ型をただ認識するだけで、以下の三つが手に入る。

• Scala におけるデータ表現
• 代数的データ型を他の型に変換するための構造的再帰の骨組み
• 他の型から代数的データ型を構築するための構造的余再帰の骨組み

重要なのは、実装非依存のデータ表現から、そのデータを扱うための実装固有の興味深い部分の多くを自動的に導き出すことができるという点である。

まず、データの例をいくつか紹介し、そこから、代数的データ型を導く共通の構造を抽出する。その後、Scala2 と Scala3 での代数的データ型の表現を見ていく。次に、代数的データ型を変換するための構造的再帰に触れ、続いて、代数的データ型を構築するための構造的余再帰について説明する。最後に、代数的データ型の代数について考察する。これは本書の内容にとって必須ではないが、興味深いテーマである。

2.1 代数的データ型の構築

まず、いくつかの異なる分野からデータ例を挙げてみよう。これらは簡略化されてはいるが、いずれも実際のアプリケーションにおける典型と言えるものである。

ディスカッションフォーラムのユーザは通常、表示名、メールアドレス、そしてパスワードといった情報をもつ。また、ユーザには通常、特定のロールが割り当てられる。たとえば、一般ユーザ、モデレータ、管理者など。これを以下に整理しておく。

• ユーザは、表示名、メールアドレス、パスワード、ロールから構成される
• ロールは、一般ユーザ、モデレータ、管理者のうちのいずれかである

eコマースストアの製品は、在庫管理単位（製品の各バリエーションに対する一意の識別子）、名前、説明、価格、割引率といった情報をもっている。

二次元ベクターグラフィックスでは、図形をパスとして表現することが一般的に行われる。パスは、仮想ペンの一連の動きで構成される。よくあるものとして、直線、ベジエ曲線、または目に見える結果を伴わない移動が挙げられる。直線には終点があり（始点は暗黙的に決まる）、ベジエ曲線にはふたつの制御点と終点があり、移動には終点がある。

上記すべての例に共通しているのは、個々の要素、いわば「原子」が論理積または論理和で結びつけられているという点である。たとえば、ユーザは表示名およびメールアドレスおよびパスワードおよびロールから構成されている。2Dアクションは、直線またはベジエ曲線または移動である。これが代数的データ型の核となる考え方で、代数的データ型とは、論理積や論理和で結びつけられたデータのことをいう。逆に言えば、データを論理積や論理和で表現できる場合、それは代数的データ型であると言える。

2.1.1 直和と直積

関数型プログラマとしては、単純な概念にちょっと難しそうな専門用語をつけずにはいられないものである。

• 直積型は論理積を意味し、
• 直和型は論理和を意味する

代数的データ型は直和型と直積型で構成される。

2.1.2 閉じた世界

代数的データ型は閉じた世界であり、一度定義されると、それが拡張されることはない。要素を追加または削除したい場合、代数的データ型を定義した元のソースコードを変更する必要がある。

この閉じた世界の性質は重要である。これによって通常は得られない保証を得ることができる。特に、代数的データ型を使用する際に、すべてのありうるケースを処理しているかどうかをコンパイラがチェック可能となる。これを網羅性チェックと呼ぶ。このように、関数型プログラミングは、拡張性などの特性よりも、コードに対する推論（この場合はコンパイラによる自動的な推論）を優先する傾向がある。網羅性チェックについては、この後詳しく学ぶ予定である。

2.2 Scala における代数的データ型

代数的データ型が何であるかを理解したところで、次にそれが Scala でどのように表現されるかを見ていこう。ここで重要なのは、Scala への翻訳が、データの構造によって完全に決定されるということである。特別なことを考える必要はない。そのため、取り組んでいる課題に最適なデータの構造を見つけることが主な作業となる。データ構造を考え出し、それに従ってコードを書けばよい。

代数的データ型は論理積と論理和で定義されるため、Scala で代数的データ型を表現するためには、これらふたつの概念がどのように表現されるかを知っておく必要がある。Scala3 では Scala2 に比べて代数的データ型の表現が簡素化されているため、それぞれの言語バージョンを別々に見ていく。

なお、代数的データ型を Scala で表現するために使用する言語機能についてはすでに知っているものとし、その説明は割愛する。

2.2.1 Scala3 における代数的データ型

Scala3 では、論理積（直積型）は final case class で表現される。直積型 A が B と C から成ると定義する場合、その Scala3 での表現は次のようになる。

final case class A(b: B, c: C)

こういった case class を final にしない人もいるが、するべきである。final でない case class は他のクラスによって拡張される可能性があり、これは代数的データ型の閉じた世界を壊してしまう。

論理和（直和型）は enum で表現される。直和型 A が B または C である場合、その Scala3 での表現は次のようになる。

enum A {
  case B
  case C
}

注意すべき点がいくつかある。データが積の和である場合、たとえば次のようなデータであれば、

• A は B または C
• B は D および E
• C は F および G

コード表現は次のようになる。

enum A {
  case B(d: D, e: E)
  case C(f: F, g: G)
}

つまり、enum の中には final case class とは書かない。また、enum の中に enum をネストすることもできない。ネストされた論理和は、論理積の論理和（これを選言標準形と呼ぶ）に書き換えることができるので、実用にあたってこれが制約になることはない。ただし、ネストされた論理和を表すことのできる Scala2 の表現は Scala3 でも引き続き利用可能である。

2.2.2 Scala2 における代数的データ型

論理積（直積型）は、Scala2 でも Scala3 でも同じうように表現される。直積型 A が B と C から成ると定義する場合、Scala2 での表現は以下のようになる。

final case class A(b: B, c: C)

論理和（直和型）は sealed abstract class で表現される。直和型 A が B または C である場合、Scala2 での表現は以下のとおりである。

sealed abstract class A
final case class B() extends A
final case class C() extends A

Scala2 で代数的データ型を定義するにあたっては小さなテクニックがいくつかある。

まず、sealed abstract class の代わりに sealed trait を使用することができる。このふたつの間には大きな実用的差異はない。私の場合、初心者に教える際には sealed trait を用いることが多い。そうすることで abstract class を紹介する手間を避けることができる。sealed abstract class の方が若干パフォーマンスが良く、Java との互換性が高いと思われるが、テストをして確認したわけではない。また、sealed abstract class の方が意味的に直和型に近いとも考えられる。

コードをさらに洗練させるために、sealed abstract class を Product と Serializable を継承した型として定義することもできる。このちょっとした工夫がある場合とない場合で、推論される型を比較してみてほしい。

まずは Product と Serializable を拡張しないコードを見てみよう。

sealed abstract class A
final case class B() extends A
final case class C() extends A

val list = List(B(), C())
// list: List[A extends Product with Serializable] = List(B(), C())

list 変数の型に Product と Serializable が含まれている点に注目してほしい。

そこで A に Product と Serializable を継承させる。

sealed abstract class A extends Product with Serializable
final case class B() extends A
final case class C() extends A

val list = List(B(), C())
// list: List[A] = List(B(), C())

これで推論される型がシンプルに読みやすくなる。

この問題は Scala2 でのみ確認できる。Scala3 には、型推論で報告される型には反映されない transparent トレイトという概念がある。そのため、Scala3 では Product と Serializable を追加してもしなくても同じ結果が得られる。

最後に、ある型がデータをひとつも保持しない場合、case class の代わりに case object を使用することができる。たとえば、ターミナルのようなテキストストリームからの読み込みでは EOF(end-of-file) が返されることがあるが、これは次のようにモデリングできる。

sealed abstract class Result
final case class Character(value: Char) extends Result
case object Eof extends Result

ファイルの終端を示す Eof には何のデータも紐づかないので、case object として定義されている。オブジェクトは拡張できないので、case object を final としてマークする必要はない。

2.2.3 例

いくつか例を挙げて、ここまでの議論についてもっと具体的に考えてみよう。

2.2.3.1 Role と User

ディスカッションフォーラムの例では、ロールは一般ユーザ・モデレータ・管理者のいずれかであるとした。これは論理和であり、適切なパターンに当てはめることで機械的に Scala へと翻訳できる。Scala3 であれば次のようになる。

enum Role {
  case Normal
  case Moderator
  case Administrator
}

Scala2 の場合は以下のように書ける。

sealed abstract class Role extends Product with Serializable
case object Normal extends Role
case object Moderator extends Role
case object Administrator extends Role

各ロールはデータをひとつも保持しないため、Scala2 のコードでは case class ではなく case object を使っている。

ユーザは、表示名とメールアドレスとパスワードとロールから構成されると定義した。これは Scala3 と Scala2 のどちらにおいても次のようになる。

final case class User(
  screenName: String,
  emailAddress: String,
  password: String,
  role: Role
)

User が保持するデータを主に String 型で表現しているが、実際のコードでは各フィールドに対して個別の型を定義したほうがよいかもしれない。

2.2.3.2 パス

前述のデータ例で、パスを仮想ペンの一連の動作として定義した。それによると、可能な動作には、直線、ベジエ曲線、または目に見える出力を伴わない移動がある。また、直線には終点があり（始点は自動的に決まる）、ベジエ曲線にはふたつの制御点と終点があり、移動には終点がある。

これらはストレートに Scala での表現に置き換えることができる。Scala3 と Scala2、どちらにおいてもパスは次のように表現できる。

final case class Path(actions: Seq[Action])

ペンの動作は論理和なので、Scala3 と Scala2 で表現の仕方が異なる。Scala3 では次のように記述できる。

enum Action {
  case Line(end: Point)
  case Curve(cp1: Point, cp2: Point, end: Point)
  case Move(end: Point)
}

なお、ここで用いている Point は二次元座標を表現したクラスであるとする。

Scala2 ではもっと冗長な表現方法を用いる必要がある。

sealed abstract class Action extends Product with Serializable 
final case class Line(end: Point) extends Action
final case class Curve(cp1: Point, cp2: Point, end: Point)
  extends Action
final case class Move(end: Point) extends Action

2.2.4 Scala3 における代数的データ型の表現

Scala3 の enum を使用した代数的データ型の表現が、Scala2 のそれよりもコンパクトであることを見てきたが、Scala2 の表現は依然として使用可能である。では、Scala3 であえて Scala2 の表現を使うべき場面はあるのかというと、いくつか考慮すべきケースがある。

• 現在のところ、Scala3 ではネストされた enum（enum 内の enum）をサポートしていない。これは今後変更されるかもしれないが、現時点では、これを選言標準形に変換することなく表現するために、Scala2 の方法を使用する方が便利な場合がある。

• Scala2 の表現方法では、代数的データ型に近いが完全にそうとは言えないものを表現することができる。たとえば、enum にメソッドを定義する場合、そのメソッドは enum のすべてのメンバーに対して意味をなさなくてはならないが、特定のメンバーのみにメソッドを定義したいことがある。このような場合、Scala2 の表現方法を使用する必要がある。

演習: 木構造

代数的データ型の定義に慣れるため、以下の記述を Scala のコードで表せ。なお、用いる Scala のバージョンは好きに選んでよい。両方を試してもかまわない。

A 型の要素をもつ Tree は以下のいずれかとして定義される。

• A 型の値を保持する Leaf、もしくは
• A 型の要素をもつ Tree を左右の子として保持する Node

enum Tree[A] {
  case Leaf(value: A)
  case Node(left: Tree[A], right: Tree[A])
}

sealed abstract class Tree[A] extends Product with Serializable
final case class Leaf[A](value: A) extends Tree[A]
final case class Node[A](left: Tree[A], right: Tree[A]) extends Tree[A]

2.3 構造的再帰

ふたつ目のプログラミング戦略は構造的再帰（structural recursion）である。代数的データ型は、特定の構造に基づいたデータをどのように定義するかを示してくれた。構造的再帰は代数的データ型を他の任意の型に変換する方法を教えてくれる。代数的データ型が与えられた場合、その変換は構造的再帰を使って実装することができる。

代数的データ型と同様、構造的再帰の概念と Scala における実装は区別して考える必要がある。そのことは、Scala には構造的再帰を実装する方法がふたつあることからもわかるだろう。そのふたつとは、パターンマッチングを使う方法と動的ディスパッチを使う方法である。これらを順に見ていこう。

2.3.1 パターンマッチング

Scala におけるパターンマッチングについては基本的な知識があることを前提としているので、ここではパターンマッチングを使って構造的再帰をどのように実装するかについてのみ解説する。代数的データ型には直和型（論理和）と直積型（論理積）の二種類があったことを思い出そう。構造的再帰をパターンマッチングで実装する際には、この二種類それぞれに対応するルールがある。

1. 直和型の各分岐は、パターンマッチ内で別々の case となる
2. 各 case は直積型に対応し、通常の方法でパターンが書かれる

これをコードで見てみよう。以下のような直和型と直積型の両方を組み合わせた代数的データ型の例を用いる。

• A は B または C の直和型
• B は D および E の直積型
• C は F および G の直積型

Scala3 ではこれは次のように表現される。

enum A {
  case B(d: D, e: E)
  case C(f: F, g: G)
}

先ほど示したルールに従うと、構造的再帰は以下のようになる。

anA match {
  case B(d, e) => ???
  case C(f, g) => ???
}

??? の部分をどう書くかは何をやりたいか次第であり、一般的な解決策を示すことはできないが、それらを実装するのに役立つ戦略についてはこの後に見ていく。

2.3.2 構造的再帰における再帰

この時点では、構造的再帰における「再帰」という言葉がどこから来ているのか疑問に思うかもしれない。再帰については追加のルールがある。データが再帰的である場合、メソッドも同じ箇所で再帰的になる、というものである。

これを実際のデータ型で見てみよう。

A 型の要素をもつリストは以下のように定義できる。

• リストは空であるか、もしくは
• ひとつの A 型の値と、それ自体が A のリストである残りの部分のペア

これは標準ライブラリにおける List の定義そのものである。直和型と直積型から構成された代数的データ型である点に注目してほしい。また、この構造は再帰的でもある。ペアのケースでは、末尾の部分自体がひとつのリストになっている。

すでに学んだ代数的データ型の戦略を使えば、これを直接コードに置き換えることができる。Scala3 では次のようになる。

enum MyList[A] {
  case Empty()
  case Pair(head: A, tail: MyList[A])
}

試しに MyList に map を実装してみよう。まずは名前と型のみを定めたメソッドの骨組みからスタートする。

enum MyList[A] {
  case Empty()
  case Pair(head: A, tail: MyList[A])
  
  def map[B](f: A => B): MyList[B] = 
    ???
}

最初のステップは、map が構造的再帰を使って記述可能であると認識することである。MyList は代数的データ型であり、map はこの代数的データ型を変換するものなので、構造的再帰が適用できる。実際に構造的再帰の戦略を適用すると、次のようになる。

enum MyList[A] {
  case Empty()
  case Pair(head: A, tail: MyList[A])
  
  def map[B](f: A => B): MyList[B] = 
    this match {
      case Empty() => ???
      case Pair(head, tail) => ???
    }
}

再帰のルールについても考慮しておこう。データが再帰的構造をもつ場合、それと同じ場所でメソッドも再帰呼び出しされる。このデータは Pair の tail の部分が再帰的なので、map もそこで再帰的になる。

enum MyList[A] {
  case Empty()
  case Pair(head: A, tail: MyList[A])
  
  def map[B](f: A => B): MyList[B] = 
    this match {
      case Empty() => ???
      case Pair(head, tail) => ??? tail.map(f)
    }
}

なお、??? は、その部分のコードがまだ完成していないことを示している。

骨組みが完成したら、取り組んでいる課題に固有の部分に進むことができる。ここで役に立つ三つの戦略がある。

1. 各ケースを独立に考えること
2. 再帰呼び出しの結果は正しいと仮定すること
3. 型に従うこと

最初のふたつは構造的再帰に特有のもので、最後のひとつは多くの状況で使える一般的な戦略である。それぞれについて簡単に検討し、今回の例にどのように適用するか見ていこう。

最初の戦略は比較的シンプルである。パターンマッチングにおいて、ある case の右側にある問題固有のコードを考える際、他のケースにあるコードは無視してかまわない。たとえば、上の Empty のケースを考えるとき、Pair のケースを気にする必要はないし、逆も同じことが言える。

次の戦略はやや複雑で、再帰に関係している。構造的再帰の戦略は、再帰呼び出しをどこに配置すればよいか示してくれることを思い出してほしい。このとき、再帰呼び出しの処理内容について深く考える必要はない。代わりに、再帰呼び出しが正しく計算されると仮定し、再帰の結果をどう処理するかだけを考えればよい。再帰以外の部分が正確であれば、結果が正しいことは保証される。

上の例には、tail.map(f) という再帰呼び出しがある。この再帰呼び出しがリストの tail に対する map を正しく行ってくれると仮定し、残りのデータ、つまり head と再帰呼び出しの結果をどう扱うかだけを考えればよい。

各ケースを独立して考えることができるのはこの特性による。再帰呼び出しは異なるケースをつなぐ唯一のものであり、その書き方は構造的再帰戦略によって与えられる。

最後の戦略は、型に従うことである。これは構造的再帰に限らず、多くの状況で使えるため、別の戦略として扱おうと思う。核となる考え方は、入出力の型情報を活用して、ありうる実装を限定していくというものである。

それでは、これらの戦略を使って map の実装を完成させよう。すでに実装した部分を以下に再掲し、この続きを考えていく。

enum MyList[A] {
  case Empty()
  case Pair(head: A, tail: MyList[A])
  
  def map[B](f: A => B): MyList[B] = 
    this match {
      case Empty() => ???
      case Pair(head, tail) => ??? tail.map(f)
    }
}

最初の戦略は、各ケースを独立して考えることである。まずは Empty のケースから始めよう。このケースには再帰呼び出しがないため、再帰について考える必要はない。代わりに型情報を利用しよう。Empty ケースにマッチしたということ以外に入力はないため、入力の型を使ってコードを制約することはできない。一方で、出力の型について考えてみると、map は MyList[B] を作成しようとしていることがわかる。MyList[B] を作成する方法は Empty か Pair の二通りだけである。そして、Pair を作成するには、B 型 の head が必要だが、それに相当する情報は与えられていないので、Empty を使うしかない。これが書くことのできる唯一のコードである。型が十分に制約を与えているため、このケースで誤ったコードを書くことはできない。

enum MyList[A] {
  case Empty()
  case Pair(head: A, tail: MyList[A])
  
  def map[B](f: A => B): MyList[B] = 
    this match {
      case Empty() => Empty()
      case Pair(head, tail) => ??? tail.map(f)
    }
}

次に Pair のケースに移ろう。ここでは構造的再帰の戦略と、型に従うこと、両方を適用することができる。以下に Pair のケースを再掲する。

case Pair(head, tail) => ??? tail.map(f)

他のケースとは独立に考えることができることを思い出してほしい。再帰呼び出しの結果は正しいと仮定すると、ここでは head をどう処理し、 tail.map(f) の結果とどう結合するかだけを考えればよい。あとは型に従ってコードを完成させよう。ゴールは MyList[B] 型の値を生成することで、そのために利用できる情報として以下のものがある。

• tail.map(f) の呼び出し結果（MyList[B] 型）
• A 型の値 head
• A を受けとり B を返す関数 f
• コンストラクタ Empty と Pair

すでに記述した Empty ケースと同じように、単に Empty を返すこともできる。これは型的には正しいが、再帰呼び出しの結果や head、関数 f をまったく使用していないし、正しい答えではないだろうと予想できる。

また、単に tail.map(f) を返すこともでき、これも型的には正しいが、head を使用していないので、やはり正しい答えではないだろう。

head に関数 f を適用して B 型の値を生成し、その値と再帰呼び出しの結果を Pair を使って組み合わせて MyList[B] 型の値を作成することができる。これが正しい解法である。

enum MyList[A] {
  case Empty()
  case Pair(head: A, tail: MyList[A])
  
  def map[B](f: A => B): MyList[B] = 
    this match {
      case Empty() => Empty()
      case Pair(head, tail) => Pair(f(head), tail.map(f))
    }
}

この例題についてここまで読み進めてきたなら、三つの戦略を使って体系的に正しい実装を見つける方法について理解していただけたと思う。再帰戦略と型に従う戦略を交互に用いることで、Pair ケースの解法へと導かれたことに注目してほしい。また、ただ型に従うだけでも Pair ケースの実装方法が三つに絞り込まれた点にも留意してほしい。今回のコードでは、そして大抵の場合もそうだが、利用できるすべての入力を使用する実装が正しい解決策となる。

2.3.3 網羅性チェック

代数的データ型は閉じた世界であり、一旦定義されると拡張できないということを思い出そう。Scala コンパイラは、この性質を利用し、パターンマッチングにおいてすべてのケースが処理されているかどうかをチェックすることができる。ただし、パターンマッチをコンパイラが処理できる形式で記述する必要がある。これは網羅性チェックと呼ばれている。

以下にシンプルな例を挙げる。まずは素直に代数的データ型を定義するところから始める。

// CSSにおいて用いられる可能性のある長さの単位
enum CssLength {
  case Em(value: Double)
  case Rem(value: Double)
  case Pt(value: Double)
}

構造的再帰の戦略を使ってパターンマッチを書いていれば、ケースが欠けているときにコンパイラが警告を出してくれる。

import CssLength.*

CssLength.Em(2.0) match {
  case Em(value) => value
  case Rem(value) => value
}
// -- [E029] Pattern Match Exhaustivity Warning: ----------------------------------
// 1 |CssLength.Em(2.0) match {
//   |^^^^^^^^^^^^^^^^^
//   |match may not be exhaustive.
//   |
//   |It would fail on pattern case: CssLength.Pt(_)
//   |
//   | longer explanation available when compiling with `-explain`

網羅性チェックは非常に有用である。たとえば、代数的データ型に新しいケースを追加したり、ケースを削除したりしたときに、更新する必要のあるパターンマッチはどれかをコンパイラが教えてくれる。

2.3.4 動的ディスパッチ

構造的再帰の実装として動的ディスパッチを使用する方法は、オブジェクト指向プログラミングの経験がある人にとって、より自然に感じられる実装テクニックかもしれない。

動的ディスパッチのアプローチは、以下の手順で構成される。

1. 代数的データ型のルートに抽象メソッドを定義する
2. 代数的データ型の各バリアントでその抽象メソッドを実装する

この実装テクニックは、Scala2 における代数的データ型の表現方法を用いている場合にのみ利用可能である。

これを、先ほど使った MyList の例で見ていこう。最初のステップは MyList の定義を Scala2 のスタイルに書き換えることである。

sealed abstract class MyList[A] extends Product with Serializable
final case class Empty[A]() extends MyList[A]
final case class Pair[A](head: A, tail: MyList[A]) extends MyList[A]

次に、MyList に抽象メソッド map を定義する。

sealed abstract class MyList[A] extends Product with Serializable {
  def map[B](f: A => B): MyList[B]
}
final case class Empty[A]() extends MyList[A]
final case class Pair[A](head: A, tail: MyList[A]) extends MyList[A]

続いて、MyList を具象化した部分型 Empty と Pair で map メソッドを実装する。

sealed abstract class MyList[A] extends Product with Serializable {
  def map[B](f: A => B): MyList[B]
}
final case class Empty[A]() extends MyList[A] {
  def map[B](f: A => B): MyList[B] = 
    Empty()
}
final case class Pair[A](head: A, tail: MyList[A]) extends MyList[A] {
  def map[B](f: A => B): MyList[B] =
    Pair(f(head), tail.map(f))
}

この map の実装を考える際には、パターンマッチングの場合とまったく同じ戦略を使用することができる。実装テクニックは違っても、基礎的な概念は同じである。

これらふたつの実装戦略のうち、どちらを使うべきだろうか。Scala3 で enum を使用している場合、選択肢はなく、パターンマッチングを使うしかない。他の状況では、どちらを使うか選択できる。私は、可能であればパターンマッチングを使うほうが好みである。そうすることでメソッド定義全体を一か所にまとめることができる。だが、特に Scala2 では、一部のパターンマッチで型推論に問題が生じることがあり、そのような場合には、動的ディスパッチを使用することもできる。これについては、一般化代数的データ型について見ていく際にさらに詳しく学ぶ予定である。

2.3.4.1 演習: Tree へのメソッド定義

前の演習では代数的データ型 Tree を作成した。

enum Tree[A] {
  case Leaf(value: A)
  case Node(left: Tree[A], right: Tree[A])
}

Scala2 の表現方法であれば以下のとおり。

sealed abstract class Tree[A] extends Product with Serializable
final case class Leaf[A](value: A) extends Tree[A]
final case class Node[A](left: Tree[A], right: Tree[A]) extends Tree[A]

構造的再帰の練習として、この Tree に対して以下のメソッドを実装せよ。

• size メソッド: Tree に格納されている値（Leafs）の件数を返す
• contains メソッド: Tree が指定された要素を含んでいる場合 true を返し、そうでなければ false を返す
• map メソッド: A を B に変換する関数を受け取って、Tree[B] を返す

実装にはパターンマッチングと動的ディスパッチどちらでも好きな方を使ってかまわない。

enum Tree[A] {
  case Leaf(value: A)
  case Node(left: Tree[A], right: Tree[A])
  
  def size: Int = 
    ???

  def contains(element: A): Boolean =
    ???
    
  def map[B](f: A => B): Tree[B] =
    ???
}

enum Tree[A] {
  case Leaf(value: A)
  case Node(left: Tree[A], right: Tree[A])
  
  def size: Int = 
    this match { 
      case Leaf(value)       => ???
      case Node(left, right) => left.size ??? right.size
    }

  def contains(element: A): Boolean =
    this match { 
      case Leaf(value)       => ???
      case Node(left, right) => left.contains(element) ??? right.contains(element)
    }
    
  def map[B](f: A => B): Tree[B] =
    this match { 
      case Leaf(value)       => ???
      case Node(left, right) => left.map(f) ??? right.map(f)
    }
}

def size: Int = 
  this match { 
    case Leaf(value)       => 1
    case Node(left, right) => left.size ??? right.size
  }

def size: Int = 
  this match { 
    case Leaf(value)       => 1
    case Node(left, right) => left.size ??? right.size
  }

def size: Int = 
  this match { 
    case Leaf(value)       => 1
    case Node(left, right) => left.size + right.size
  }

enum Tree[A] {
  case Leaf(value: A)
  case Node(left: Tree[A], right: Tree[A])
  
  def size: Int = 
    this match { 
      case Leaf(value)       => 1
      case Node(left, right) => left.size + right.size
    }

  def contains(element: A): Boolean =
    this match { 
      case Leaf(value)       => element == value
      case Node(left, right) => left.contains(element) || right.contains(element)
    }
    
  def map[B](f: A => B): Tree[B] =
    this match { 
      case Leaf(value)       => Leaf(f(value))
      case Node(left, right) => Node(left.map(f), right.map(f))
    }
}

2.3.5 構造的再帰としての畳み込み

最後に、構造的再帰を抽象化したものとして畳み込みメソッドについて見ていこう。先ほどの Tree の演習を行ったなら、同じパターンのコードを何度も書いたことに気付いたはずである。演習で作成したメソッドを以下に再掲する。パターンマッチの左側はすべて同じだし、右側も非常に似ていることに注目してほしい。

def size: Int = 
  this match { 
    case Leaf(value)       => 1
    case Node(left, right) => left.size + right.size
  }

def contains(element: A): Boolean =
  this match { 
    case Leaf(value)       => element == value
    case Node(left, right) => left.contains(element) || right.contains(element)
  }
  
def map[B](f: A => B): Tree[B] =
  this match { 
    case Leaf(value)       => Leaf(f(value))
    case Node(left, right) => Node(left.map(f), right.map(f))
  }

この類似性を認識し公式化することが構造的再帰の要点である。だが、プログラマとしては、この繰り返しを抽象化したくなるかもしれない。構造的再帰の中で変わらない部分をすべて抽出し、変わる部分については呼び出し側が引数として渡せるようなメソッドを作ることはできるだろうか。これは実は可能である。任意の代数的データ型に対して、そういうメソッドを少なくともひとつは定義できる。畳み込みと呼ばれるそのメソッドが構造的再帰の変わらない部分をすべてキャプチャし、やりたいことに応じて異なる部分を呼び出し側が指定できるようにしてくれる。

どのように定義されるのか MyList の例を使って見ていこう。MyList の定義を再掲する。

enum MyList[A] {
  case Empty()
  case Pair(head: A, tail: MyList[A])
}

MyList で使われる構造的再帰の骨組みは、すでに理解しているとおり、以下のようになる。

def doSomething[A](list: MyList[A]) =
  list match {
    case Empty()          => ???
    case Pair(head, tail) => ??? doSomething(tail)
  } 

MyList に畳み込みを実装するとは、次のような fold メソッドを定義するということである。

def fold[A, B](list: MyList[A]): B =
  list match {
    case Empty() => ???
    case Pair(head, tail) => ??? fold(tail)
  }

ここで B は、呼び出し元が生成したい値の型とする。

fold メソッドを完成させるには、個々の問題に固有の部分である ??? を埋めるために引数を加える必要がある。Empty のケースには B 型の値が必要である（型に従って考えていることに注目してほしい）。

def fold[A, B](list: MyList[A], empty: B): B =
  list match {
    case Empty() => empty
    case Pair(head, tail) => ??? fold(tail, empty)
  }

Pair のケースでは、 A 型の head と、 B 型の値を生成する再帰処理がすでにあるので、必要なのはそれらふたつを結合する関数ということになる。

def foldRight[A, B](list: MyList[A], empty: B, f: (A, B) => B): B =
  list match {
    case Empty() => empty
    case Pair(head, tail) => f(head, foldRight(tail, empty, f))
  }

これが foldRight メソッドである（この後に見せるもうひとつの解法と区別できるよう名前を変更した）。これを見て、もうひとつの有効な解があることに気付いたかもしれない。empty も再帰呼び出しも B の値を生成する。型に従って考えれば、次のような結論に至ることもできるだろう。

def foldLeft[A,B](list: MyList[A], empty: B, f: (A, B) => B): B =
  list match {
    case Empty() => empty
    case Pair(head, tail) => foldLeft(tail, f(head, empty), f)
  }

これが foldLeft メソッドで、リストに対する畳み込みの末尾再帰バージョンである。末尾再帰については後の章で解説する。

決まった手順をたどることで、任意の代数的データ型に対してその畳み込みメソッドを作成することができる。そのルールは以下のとおりである。

• 畳み込みは、代数的データ型と追加のパラメータを取り、何らかの別の型（以下では便宜上 B と呼ぶ）に変換する関数である
• 畳み込みは、直和型の各バリアントに対してひとつの追加パラメータをもつ
• 各パラメータは関数で、結果の型は B、対応するコンストラクタの引数と同じ型のパラメータを取る。ただし、再帰的な引数の型は B と見なせる
• コンストラクタに引数がない場合（たとえば Empty）、引数のない関数の代わりに、型 B の値を使用できる

MyList に当てはめると次のようになる。

• ふたつのバリアントがあるので、畳み込みにはふたつのパラメータが必要（リストそれ自体以外に）
• Empty は引数なしコンストラクタなので、B 型のパラメータをひとつ
• Pair は A 型の引数をひとつと、再帰的な引数をひとつもったコンストラクタなので、対応する関数の型は (A, B) => B となる

演習: Tree の畳み込み

以前定義した Tree に対して畳み込みを実装せよ。二分木の走査には、先行順、後行順、中間順などいくつかの方法があるが、もっとも簡単だと思うものを選んで実装してかまわない。

enum Tree[A] {
  case Leaf(value: A)
  case Node(left: Tree[A], right: Tree[A])
  
  def fold[B]: B =
    ???
}

enum Tree[A] {
  case Leaf(value: A)
  case Node(left: Tree[A], right: Tree[A])
  
  def fold[B]: B =
    this match {
      case Leaf(value)       => ???
      case Node(left, right) => left.fold ??? right.fold
    }
}

enum Tree[A] {
  case Leaf(value: A => B)
  case Node(left: Tree[A], right: Tree[A])
  
  def fold[B](leaf: A => B): B =
    this match {
      case Leaf(value)       => leaf(value)
      case Node(left, right) => left.fold ??? right.fold
    }
}

enum Tree[A] {
  case Leaf(value: A)
  case Node(left: Tree[A], right: Tree[A])
  
  def fold[B](leaf: A => B)(node: (B, B) => B): B =
    this match {
      case Leaf(value)       => leaf(value)
      case Node(left, right) => node(left.fold(leaf)(node), right.fold(leaf)(node))
    }
}

演習: 畳み込みの利用

構造的再帰が畳み込みの呼び出しに置き換えられることを確認するため、Tree の size、contains、map を、fold だけを使って再定義せよ。

enum Tree[A] {
  case Leaf(value: A)
  case Node(left: Tree[A], right: Tree[A])
  
  def fold[B](leaf: A => B)(node: (B, B) => B): B =
    this match {
      case Leaf(value)       => leaf(value)
      case Node(left, right) => node(left.fold(leaf)(node), right.fold(leaf)(node))
    }
    
  def size: Int = 
    this.fold(_ => 1)(_ + _)

  def contains(element: A): Boolean =
    this.fold(_ == element)(_ || _)
    
  def map[B](f: A => B): Tree[B] =
    this.fold(v => Leaf(f(v)))((l, r) => Node(l, r))
}

2.4 構造的余再帰

構造的余再帰（structural corecursion）は、構造的再帰の反対、より正確な用語を使うなら双対（dual）である。構造的再帰が代数的データ型をどのように分解するかを教えてくれるのに対して、構造的余再帰は代数的データ型をどのように構築するかを教えてくれる。構造的再帰は、メソッドや関数の入力が代数的データ型である場合に使用できるが、構造的余再帰はメソッドや関数の出力が代数的データ型である場合に使用できる。

構造的再帰は、考えられるすべての入力（通常はパターンマッチングのパターンとして表現される）について、それぞれの入力ケースに対して何を行うかを決定することによって機能する。一方、構造的余再帰は、考えられるすべての出力、すなわち代数的データ型のコンストラクタについて考え、それぞれのコンストラクタを呼び出す条件を決定することによって機能する。

A 型の要素を持つリストの話に戻ろう。これは次のように定義することができた。

• リストは空であるか、もしくは
• ひとつの A 型の値と、それ自体が A のリストである残りの部分のペア

Scala3 では次のように書かれる。

enum MyList[A] {
  case Empty()
  case Pair(head: A, tail: MyList[A])
}

MyList インスタンスを生成するメソッドを書きたいときに、構造的余再帰を利用することができる。そのよい例として map がある。

enum MyList[A] {
  case Empty()
  case Pair(head: A, tail: MyList[A])
  
  def map[B](f: A => B): MyList[B] = 
    ???
}

このメソッドの出力は代数的データ型である MyList である。MyList インスタンスを構築したいのだから、構造的余再帰を利用することができる。構造的余再帰の戦略では、まずすべてのコンストラクタを書き出し、それぞれのコンストラクタ呼び出しを引き起こす条件を考える。したがって、最初のステップは、ふたつのコンストラクタを書き出し、仮の条件を記述することである。

enum MyList[A] {
  case Empty()
  case Pair(head: A, tail: MyList[A])
  
  def map[B](f: A => B): MyList[B] = 
    if ??? then Empty()
    else Pair(???, ???)
}

データが再帰的である場所で再帰呼び出しを行うというルールを適用すると、メソッドは以下のようになる。

enum MyList[A] {
  case Empty()
  case Pair(head: A, tail: MyList[A])
  
  def map[B](f: A => B): MyList[B] = 
    if ??? then Empty()
    else Pair(???, ???.map(f))
}

これまでに学んだ戦略を利用することで、if 式の条件部、あるいはパターンマッチングであればその case 部分を完成させることができる。

• 構造的再帰を使って、考えうる条件がふたつあることを確認する
• 型に従って、これらの条件を既に書いたコードに合わせる

この手順に従えば、短時間で正しい解決策にたどり着くことができる。

enum MyList[A] {
  case Empty()
  case Pair(head: A, tail: MyList[A])
  
  def map[B](f: A => B): MyList[B] = 
    this match {
      case Empty() => Empty()
      case Pair(head, tail) => Pair(f(head), tail.map(f))
    }
}

ここには興味深いポイントがいくつかある。

まず、map は構造的再帰であり、同時に構造的余再帰でもあるということを認識しておく必要がある。これはいつも成り立つわけではない。たとえば、foldLeft と foldRight は、必ずしも代数的データ型を生成するとは限らないし、構造的余再帰ではない。

次に、map を構造的再帰として実装するプロセスを進めた際に、型に従う一環として、それと知らずに構造的余再帰のパターンを使用していたことに注目してほしい。我々は List を生成しようとしていることに気づき、List を生成する方法としてふたつのコンストラクタの存在を認識し、それぞれに適した条件を見出した。構造的余再帰をひとつの戦略として公式化することで、それを適用しているということを、より意識的に認識できるようになる。

最後に、map を定義していく過程で、if 式からパターンマッチ式に切り替えたことに留意してほしい。これはまったく問題ない。どちらの式でも同じ効果を得ることができる。ただし、パターンマッチングは網羅性チェックがあるのですこし安全である。また、もし if 式を使い続けるのであれば、Empty と Pair を区別するためのメソッド（たとえば isEmpty）を定義しなくてはならないが、そのメソッドの実装にあたってパターンマッチングを使用する必要があるため、パターンマッチングの直接的な利用を避けても、それを別の場所に押し込めてしまうだけである。

2.4.1 構造的余再帰としての展開（unfold）

構造的再帰を fold として抽象化できたように、任意の代数的データ型に対して、構造的余再帰を unfold として抽象化することができる。unfold は fold ほど一般的に使われるものではないが、有用なツールである。

今回も MyList を例として使いながら、unfold を導き出すプロセスを見ていこう。

enum MyList[A] {
  case Empty()
  case Pair(head: A, tail: MyList[A])
}

構造的余再帰の骨組みは以下のとおりだった。

if ??? then MyList.Empty()
else MyList.Pair(???, recursion(???))

まず unfold の骨格を書き出すことから始める。すこし変わっているのは、seed というパラメータを追加していることである。これはデータを作成するために必要なものだが、戦略から導き出せるものではないため、初期の仮定としてここに追加されている。

def unfold[A, B](seed: A): MyList[B] =
  ???

ここからは、いつもの戦略を使って足りないピースを埋めていく。以下のコードでは、余再帰の骨格を用いるとともに、導出のステップを省くため、再帰呼び出しのルールの適用まで行っている。

def unfold[A, B](seed: A): MyList[B] =
  if ??? then MyList.Empty()
  else MyList.Pair(???, unfold(seed))

条件部は A => Boolean 型の関数を使って抽象化できる。

def unfold[A, B](seed: A, stop: A => Boolean): MyList[B] =
  if stop(seed) then MyList.Empty()
  else MyList.Pair(???, unfold(seed, stop))

次に必要なのは Pair を生成するケースのハンドリングである。 A 型の値として seed がすでにあるので、Pair の head 要素を作成するには A => B 型の関数があればよいだろう。

def unfold[A, B](seed: A, stop: A => Boolean, f: A => B): MyList[B] =
  if stop(seed) then MyList.Empty()
  else MyList.Pair(f(seed), unfold(???, stop, f))

最後に、現在の seed 値から、次の再帰呼び出しで使う値を導かなくてはならない。そのために A => A 型の関数が必要となる。

def unfold[A, B](seed: A, stop: A => Boolean, f: A => B, next: A => A): MyList[B] =
  if stop(seed) then MyList.Empty()
  else MyList.Pair(f(seed), unfold(next(seed), stop, f, next))

これで unfold の定義は完成である。unfold を使って他のメソッドを定義し、その便利さを味わってみよう。すでに見たように、map は構造的余再帰なので、これを unfold で定義しなおす。さらに、リストを構築するメソッドである fill と iterate も定義することにする。これらは、Scala 標準ライブラリの List にある同名のメソッドに対応している。

以下に示すコードでは、作業を簡単にするため、unfold を MyList のコンパニオンオブジェクトのメソッドとして宣言している。また、型推論を改善するために定義にすこし調整を加えている。Scala では、あるメソッドパラメータについて推論された型を、同じパラメータリスト内にある他のパラメータの型推論で使うことはできない。だが、異なるパラメータリストにおいては、先行するパラメータリストで推論された型を後続のパラメータリストで利用することができる。関数パラメータを seed とは別のパラメータリストに分けることで、seed から推論された A の型を、関数パラメータの入力型の推論に使用できるようにしている。

さらに、代数的データ型を分解するメソッドであるデストラクタ（destructor）もいくつか宣言した。今回の MyList では、head、tail、および述語 isEmpty がデストラクタである。これらについては後ほど詳しく説明する。

以下のコードから始めよう。

enum MyList[A] {
  case Empty()
  case Pair(_head: A, _tail: MyList[A])

  def isEmpty: Boolean =
    this match {
      case Empty() => true
      case _       => false
    }
    
  def head: A =
    this match {
      case Pair(head, _) => head
    }
    
  def tail: MyList[A] =
    this match {
      case Pair(_, tail) => tail
    }
}
object MyList {
  def unfold[A, B](seed: A)(stop: A => Boolean, f: A => B, next: A => A): MyList[B] =
    if stop(seed) then MyList.Empty()
    else MyList.Pair(f(seed), unfold(next(seed))(stop, f, next))
}

まずはリストのコンストラクタである fill と iterate を、そしてその後に map を、unfold を使って定義する。コンストラクタのほうがシンプルなので、まずはそちらから取り組もうという意図である。

object MyList {
  def unfold[A, B](seed: A)(stop: A => Boolean, f: A => B, next: A => A): MyList[B] =
    if stop(seed) then MyList.Empty()
    else MyList.Pair(f(seed), unfold(next(seed))(stop, f, next))
    
  def fill[A](n: Int)(elem: => A): MyList[A] =
    ???
    
  def iterate[A](start: A, len: Int)(f: A => A): MyList[A] =
    ???
}

ここでは、List のドキュメントからそのまま取ってきたメソッドの骨格だけを追加している。これらのメソッドを実装するにあたっては、次のふたつの戦略のいずれかが利用可能である。

• 命令型言語における方法でループについて考えること
• 自然数の構造的再帰について考えること

順に見ていこう。

unfold のパラメータが、Java などの言語で for ループを作る際に必要なものとほぼ一致していることに気づいた人もいるかもしれない。典型的な for(i = 0; i < n; i++) 形式の for ループには、次の4つの要素がある。

1. ループカウンタの初期値
2. ループの停止条件
3. カウンタを進めるためのステートメント
4. カウンタを使用するループの本体

これらはそれぞれ unfold のパラメータである seed、stop、next、f に対応している。

ループの変化条件と不変条件について意識することは、命令型ループが何を行っているのかを把握するための標準的な方法である。ループの処理内容を読み解く方法についてはすでに知っているものとし（ここで使っている用語には馴染みがないかもしれないが）、ここでは詳しく説明しない。代わりに、ふたつ目の推論戦略について説明する。それは、unfold の書き方を、我々がすでに学んだ構造的再帰と関連づける方法である。

最初のステップは、自然数（ここでは0以上の整数と定義する）が概念的には代数的データ型であるという点に着目することである。もっとも、Scala においては自然数は Int を使って表現されるし、代数的データ型とは言えないが。あるひとつの自然数は次のいずれかである。

• ゼロ
• ある自然数に1を足した数

これは直和型と直積型の両方からなるもっともシンプルな代数的データ型である。

これを理解すると、構造的再帰の推論ツールを使って、unfold に渡すパラメータを作成することができる。どういうことか fill の例で説明しよう。パラメータ n は作成するリストの要素数を示している。パラメータ elem はリストの要素を生成するため、各要素に対して一度ずつ呼び出される。ここでは、これを自然数に対する構造的再帰として考える。n を seed とし、stop には x => x == 0 という関数を渡す。これらは自然数に対する構造的再帰における標準的な条件である。next はどうすればよいだろうか。自然数の定義に従い再帰的に1を引けばよいので、next は x => x - 1 となる。最後に f だが、これは fill がどのように動作すべきかという定義から導かれる。fill は elem を使って値を作成するので、f はシンプルに _ => elem となる。

object MyList {
  def unfold[A, B](seed: A)(stop: A => Boolean, f: A => B, next: A => A): MyList[B] =
    if stop(seed) then MyList.Empty()
    else MyList.Pair(f(seed), unfold(next(seed))(stop, f, next))
    
  def fill[A](n: Int)(elem: => A): MyList[A] =
    unfold(n)(_ == 0, _ => elem, _ - 1)
    
  def iterate[A](start: A, len: Int)(f: A => A): MyList[A] =
    ???
}

この実装が意図どおりに動作するか確認しておこう。確認には List.fill と比較すればよい。

List.fill(5)(1)
// res22: List[Int] = List(1, 1, 1, 1, 1)
MyList.fill(5)(1)
// res23: MyList[Int] = MyList(1, 1, 1, 1, 1)

次に示すのは、状態をもつ関数を elem として用いて昇順の数値リストを作成する、すこし複雑な確認例である。まず状態を定義し、それを使用する関数を定義する。

var counter = 0
def getAndInc(): Int = {
  val temp = counter
  counter = counter + 1
  temp 
}

これを fill メソッドに渡せば、昇順の数値リストが得られるはずである。

List.fill(5)(getAndInc())
// res24: List[Int] = List(0, 1, 2, 3, 4)
counter = 0
MyList.fill(5)(getAndInc())
// res26: MyList[Int] = MyList(0, 1, 2, 3, 4)

演習: MyList への iterate の実装

fill の時と同じ考え方を使って iterate を実装せよ。iterate は、カウンタの値と型 A の値というふたつの情報を保持する必要があるため、fill よりもすこし複雑になる。

object MyList {
  def unfold[A, B](seed: A)(stop: A => Boolean, f: A => B, next: A => A): MyList[B] =
    if stop(seed) then MyList.Empty()
    else MyList.Pair(f(seed), unfold(next(seed))(stop, f, next))
    
  def fill[A](n: Int)(elem: => A): MyList[A] =
    unfold(n)(_ == 0)(_ => elem, _ - 1)
    
  def iterate[A](start: A, len: Int)(f: A => A): MyList[A] =
    unfold((len, start)){
      (len, _) => len == 0,
      (_, start) => start,
      (len, start) => (len - 1, f(start))
    }
}

List.iterate(0, 5)(x => x - 1)
// res27: List[Int] = List(0, -1, -2, -3, -4)
MyList.iterate(0, 5)(x => x - 1)
// res28: MyList[Int] = MyList(0, -1, -2, -3, -4)

演習: MyList への map の実装

map を unfold を用いて再実装せよ。なお、これを実装するにはデストラクタを利用する必要がある。

def map[B](f: A => B): MyList[B] =
  MyList.unfold(this)(
    _.isEmpty,
    pair => f(pair.head),
    pair => pair.tail
  )

List.iterate(0, 5)(x => x + 1).map(x => x * 2)
// res29: List[Int] = List(0, 2, 4, 6, 8)
MyList.iterate(0, 5)(x => x + 1).map(x => x * 2)
// res30: MyList[Int] = MyList(0, 2, 4, 6, 8)

ここで、デストラクタについて簡単に見ておこう。デストラクタはふたつのことを行う。

1. 直和型のバリアントを区別する
2. 区別したそれぞれの直積型からプロパティを取り出す

MyList の場合、最小限のデストラクタは、Pair から Empty を区別する isEmpty と、そして head と tail である。プロパティを取り出すメソッド（extractor）は部分関数になる。これは Scala とは無関係な概念上の話である。それらは特定の直積型に対してだけ定義されており、それ以外のケースで用いると例外をスローする。先ほど fill に渡した関数が、まさに自然数に対するデストラクタであったことに気付いた人もいるかもしれない。

デストラクタは構造的再帰と構造的余再帰の間にある双対性のひとつの側面である。構造的再帰がやることは以下のとおりだが、

• コンストラクタを区別するパターンマッチングによって定義され
• 代数的データ型を小さな部分に分解する

一方、構造的余再帰は以下のことを行う。

• デストラクタを用いて記述される、入力に対する条件によって定義され
• 小さな部分から代数的データ型の値を組み立てる

unfold の話を終える前にもうひとつだけ述べておきたい。一般的な unfold の定義を見ると、おそらく以下のような定義が見つかるだろう。

def unfold[A, B](in: A)(f: A => Option[(A, B)]): List[B]

これは、我々が用いた定義と等価だが、インターフェースはややコンパクトである。我々の定義は、メソッドの構造を明確にするために、より明示的なものとなっている。

2.5 代数的データ型における代数

ときどき挙がる質問に、代数的データ型はなぜ「代数」と名付けられているのか、というものがある。この点についてすこし触れ、代数的データ型で行える代数的な操作をいくつか紹介したい。

この「代数」という用語は、数学の一分野である抽象代数学の意味で使われている。抽象代数学は、代数的構造を扱う分野である。代数的構造は、ある値の集合、その集合上の操作、およびそれらの操作が満たすべき性質から構成される。

具体例として、整数の集合と、加法や乗法という操作、そして結合律 a + (b+c) = (a+b) + c などといった操作の性質が挙げられる。抽象代数学の「抽象」とは、整数のような具体的な集合を扱うのではなく、代わりに半群、モノイド、環といった奇妙な名前のついた抽象的な概念を扱うことを意味している（具体的であれば理解するのは極めて簡単なのだが）。上述の整数の話は環の一例である。これから、そのような概念をたくさん見ていくことになるだろう。

代数的データ型も、環と呼ばれる代数的構造に対応している。環はふたつの演算をもち、通常それらは + および × と記述される。これらがそれぞれ直和型と直積型に対応していると推測したなら、まさにそのとおりである。では、環におけるこれらの演算の性質はどのようなものだろうか。それらは、基本的な代数について我々が知っているものと似ている。

• + と × は結合律を満たす。つまり a + (b+c) = (a+b) + c であり、× についても同様である
• + は交換律を満たす。つまり a + b = b + a である
• a + 0 = a となる単位元 0 が存在する
• a × 1 = a となる単位元 1 が存在する
• 分配律を満たす。つまり a × (b+c) = (a×b) + (a×c) である

かなり抽象的な話になってしまったので、ここからは Scala による実例を使って具体化してみよう。

Remember the algebraic data types work with types, so the operations + and × take types as parameters. So Int × String is equivalent to

代数的データ型は型を取り扱うものなので、演算 + と × も型を引数として受け取る。たとえば、Int × String は次のように表される。

final case class IntAndString(int: Int, string: String)

いちいち命名せずにタプルを使うという手もある。

type IntAndString = (Int, String)

+ という演算に対しても同じような表現が可能である。 Int + String は次のように表される。

enum IntOrString {
  case IsInt(int: Int)
  case IsString(string: String)
}

もしくは単に以下のように表現してもかまわない。

type IntOrString = Either[Int, String]

演習: 単位元

直積型における単位元 1 に対応する Scala の型は何か考察せよ。

また、直和型における単位元 0 に対応する Scala の型は何か考察せよ。

代数的データ型における分配律はどのようなものだろうか。この法則を使うと、代数的データ型を操作して、等価だがより使いやすい表現を作成できることがある。その例として、ユーザを表すデータ型を考えてみよう。

final case class Person(name: String, permissions: Permissions)
enum Permissions {
  case User
  case Moderator
}

これを数学的に表記すると次のようになる。

Person = String × Permissions Permissions = User + Moderator

Permissions をその定義で置き換えると次のようになり、

Person = String × (User+Moderator)

さらに分配法則を適用すると結果は次のようになる。

Person = (String×User) + (String×Moderator)

これは Scala では次のように表現される。

enum Person {
  case User(name: String)
  case Moderator(name: String)
}

これが元の定義よりも有用かどうかは、データがどういうコンテキストで使われるのかわからないかぎり何とも言えないが、このような操作が可能かつ正しいものであり、役に立ちうることは間違いないだろう。

代数的データ型について言えることは他にもたくさんあるが、やや深入りしすぎてしまったようである。最後にいくつか興味深いトピックを簡単に紹介して締めくくりたい。

• 指数型というものが存在する。それは関数である。関数 A => B は、数学的に b^a に相当する
• 商型も存在するが、すこし変わっている。興味があれば調べてみてほしい
• もうひとつの興味深い代数的操作として、代数的データ型の微分がある。これにより、その型に対するイテレータの一種である zipper が得られる

2.6 まとめ

この章では多くの内容を扱った。ここで重要なポイントを振り返っておこう。

代数的データ型を使えば、既存の型を論理積と論理和で組み合わせることによって別のデータの型を表現することができる。論理積は直積型を構築し、論理和は直和型を構築する。代数的データ型は Scala でデータを表現する主要な方法である。

構造的再帰は、与えられた代数的データ型を他の任意の型に変換するための骨組みを提供する。構造的再帰は fold メソッドとして抽象化することができる。

構造的再帰における問題固有の部分を完成させるのに役立つ考え方の原則がいくつかある。

1. 各ケースを独立して推論すること
2. 再帰呼び出しの結果は正しいと仮定すること
3. 型に従うこと

型に従うことは他の多くの状況で利用できる極めて汎用的な戦略である。

構造的余再帰は、任意の型から代数的データ型を作成するための骨組みを提供する。構造的余再帰は unfold メソッドとして抽象化できる。構造的余再帰について推論する際は、命令型のループの処理手順を考えるのと同じように進めるか、あるいは入力が代数的データ型である場合は、構造的再帰についての推論の原則を利用することができる。

関数型プログラミングのふたつの主要なテーマである合成と推論がすでにはっきり認識できる形で示されている点に注目してほしい。代数的データ型は合成的である。直和型と直積型を使って合成することができる。この章では多くの推論原則も見てきた。

代数的データ型について知っておくべきすべてのことを説明したわけではない。これを完全に網羅すれば、それだけで一冊の本になるだろう。さらに掘り下げたい場合に役立つ参考文献や、著者の経歴に関するいくつかの補足を以下に示しておく。

代数的データ型は、関数型プログラミングの入門資料では標準的に取り扱われている。構造的再帰も関数型プログラミングで非常によく使われるが、ここで私が行ったように明確に定義されることは珍しいようである。私はこれらについて How to Design Programs [Felleisen et al. 2018] から学んだ。

代数的データ型や構造的再帰について、手軽にアクセスできつつも詳細に扱った資料は私の知るかぎり存在しない。これらの概念は、プログラミング言語研究の分野ではもはや前提知識とされているようである。最近の研究は数学的で難解な表記に覆われており、私にとっては読みづらいものが多い。悪名高い Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire [Meijer et al. 1991] はその一例である。両アイデアの核となる発想は、少なくとも計算可能性理論が登場した1930年代、デジタルコンピュータが存在するはるか以前にまで遡るのではないかと思われる。

構造的再帰に関して私が見つけたもっとも古い参考文献は、Proving Properties of Programs by Structural Induction [Burstall 1969] である。代数的データ型とパターンマッチングの発展は、1977年の NPL までは十分ではなかったようだが、その後すぐに、より影響力のある言語である Hope が登場し、この概念が他のプログラミング言語にも広まった。

余再帰については現代の文献にすこし詳しく記録されている。How to Design Co-Programs [Gibbons 2021] では、ここで取り上げた主なアイデアが説明されているし、[Gibbons and Jones 1998] では unfold の使い方について議論されている。

The Derivative of a Regular Type is its Type of One-Hole Contexts [McBride 2001] は代数的データ型の微分について記述している。

3 余データとしてのオブジェクト

この章では、代数的データ型の双対である余データについて見ていく。代数的データ型はモノがどのように構築されるかに焦点を当てているのに対して、余データはモノがどのように利用されるかに焦点を当てる。余データは、型に対して実行できる操作を指定することで定義される。これはオブジェクト指向プログラミングにおけるインターフェースの使い方と非常に似ており、これが余データに注目する最初の理由である。オブジェクト指向プログラミングは、余データという概念によって、我々が今議論している戦略と整合性のある概念的枠組みの中に位置づけられる。

しかし、余データに注目するのはオブジェクト指向プログラミングを捉えるためだけではない。余データには、代数的データにはない特性がある。たとえば、余データを使うことで、無限の要素を持つ構造、終わりのないリストや永遠に実行されるサーバーループのようなものを作成することができる。また、余データは拡張性の点でも代数的データとは異なる形をもっている。代数的データ型を別の何かへと変換する関数を新しく作成するのは簡単だが、代数的データ型に新しいバリアントを追加するには既存のコードを変更する必要がある。余データはその逆で、新しい実装を簡単に作成できるが、余データを変換する関数は余データが定義するインターフェースに制約される。

前章では、代数的データ型を使用してプログラムを記述するための戦略として、構造的再帰と構造的余再帰を取り上げた。余データについても同様で、余データを消費するプログラムを書く際には構造的再帰を、生成するプログラムを書く際には構造的余再帰を使用することができる。

まず、余データをより正確に定義し、いくつかの例を見ていこうと思う。次に、Scala における余データの表現方法とオブジェクト指向プログラミングとの関係について説明する。余データの作成方法を理解した後は、無限構造の例を使って、構造的再帰や構造的余再帰を用いた余データの扱い方を学ぶ。その後、代数的データ型と余データの相互変換について考察し、最後に拡張性の違いを検証する。

進める前に用語について簡単に触れておきたい。代数的データの双対としては「代数的余データ」という用語を期待されるかもしれないが、慣例的に単に「余データ」という用語が使われる。これは、データという言葉が、一般的に代数的データに限定されず、より広い意味をもつのに対して、余データはプログラミング言語理論の外では使われないからだと考えられる。この章では、簡潔さと対称性のために、代数的データ型を指す際に「データ」という用語を使用する。

3.1 データと余データ

データはある物が何であるのかを記述し、余データはある物が何をできるのかを記述する。

これまで、データはその型の各バリアントを生成するコンストラクタによって定義されることを見てきた。非常に単純な例として、Bool は True または False のいずれかで、Scala では次のように表現できる。

enum Bool {
  case True
  case False
}

この定義は、Bool 型の値を構築する方法がふたつあることを示している。さらに、そうやって構築された値があるとき、たとえばパターンマッチを使用することで、どちらのケースであるのかを正確に判断することができる。同様に、たとえば List のようにインスタンス自体がデータを保持している場合、その中のすべてのデータを取り出すことが常に可能である。これもパターンマッチによって実現できる。

対照的に、余データは、その型の値に対して行える操作によって定義される。これらの操作は、デストラクタ（destructor）、オブザベーション（observation）、またはエリミネータ（eliminator）と呼ばれることがある。デストラクタは前章にも登場した。余データの一般的な例として、集合のようなデータ構造がある。たとえば、 A 型の要素をもつ Set の操作は次のように定義できる。

• contains: Set[A] と要素 A を受け取り、集合にその要素が含まれているかどうかを示す Boolean を返す
• insert: Set[A] と要素 A を受け取り、元の集合のすべての要素と新しい要素を含む Set[A] を返す
• union: Set[A] ともうひとつの集合 Set[A] を受け取り、両方の集合のすべての要素を含む Set[A] を返す

Scala ではこの定義を次のように記述できる。

trait Set[A] {
  
  /** 与えられた要素がこの集合に含まれていれば真 */
  def contains(elt: A): Boolean
  
  /** この集合のすべての要素と与えられた要素を含む新しい集合を構築する */
  def insert(elt: A): Set[A]
  
  /** この集合と指定された集合の和集合を構築する */
  def union(that: Set[A]): Set[A]
}

この定義は、集合内の要素が内部的にどのように表現されているかついて何も述べていない。ハッシュテーブルが使われるかもしれないし、木構造やあるいはもっと特殊な何かが使われるかもしれない。だが、集合に対してどういう操作が可能であるかをこの定義は教えてくれる。たとえば、和集合をとることはできても積集合をとることはできない、ということはわかるのである。

オブジェクト指向の世界から来た人であれば、前述の余データの説明をインターフェースを利用したプログラミングと認識するかもしれない。ある意味、余データとはオブジェクト指向の世界から概念を取り入れ、それを関数型プログラミングのパラダイムと一貫した形で提示するものと言える。しかし、これはオブジェクト指向プログラミングのすべての機能を採用するという意味ではない。関数型プログラミングでは可変状態を使用しない。推論が難しくなるからである。同じ理由で実装の継承も使わない。関数型の世界で使われるオブジェクト指向プログラミングのサブセットでは、インターフェースを定義し（いくつかのメソッドにデフォルト実装をもたせてもよい）、そのインターフェースを実装する final クラスを定義する。興味深いことに、このようなオブジェクト指向プログラミングのサブセットは、オブジェクト指向プログラミングの支持者によってもしばしば勧められている。

それでは、余データをもうすこし正確に定義していこう。そうすることで、データと余データの双対性がより明確になるはずである。データの定義を思い出してほしい。データは直和型と直積型を使って定義される。どのようなデータでも「積の和」の形に変換することができる。この和の中の各積がコンストラクタであり、積を構成する各プロパティがコンストラクタの受け取るパラメータとなる。コンストラクタは任意の入力を受け取りデータの値を生成する関数と考えることができ、最終的な形は、任意の入力からデータを生成する関数の直和となる。

あるデータ型 A の値を構築するときは、複数あるコンストラクタのうちのひとつを呼び出す。

• A1: (B, C, ...) => A または
• A2: (D, E, ...) => A または
• A3: (F, G, ...) => A など

一方、余データは関数の積として定義される。これらの関数はデストラクタである。デストラクタへの入力には常に余データ型が含まれ、場合によって他のパラメータも存在する。出力は通常、余データ型ではない何かになる。したがって、余データ型 A の要素を構築するということは、以下のような定義を行うことを意味する。

• A1: (A, B, ...) => C および
• A2: (A, D, ...) => E および
• A3: (A, F, ...) => G など

これで、両者の双対性がより明確になることを期待したい。余データが何であるかは理解できたので、次に Scala における余データの表現に移ろう。

3.2 Scala における余データ

前節で見た余データの例を以下に再掲する。

trait Set[A] {
  
  def contains(elt: A): Boolean
  
  def insert(elt: A): Set[A]
  
  def union(that: Set[A]): Set[A]
}

関数の積として表されるこの抽象的な定義は、A 型の要素をもつ Set を次のような操作をもつものであると定義している。

• Set[A] と A 型の要素を受け取り、Boolean を返す関数 contains
• Set[A] と A 型の要素を受け取り、Set[A] を返す関数 insert
• Set[A] ともうひとつの Set[A] を受け取り、Set[A] を返す関数 union

どの関数も最初のパラメータの型は Set[A] である点に注目してほしい。

Scala に翻訳する方法は以下のとおり。

• 全体の型を trait とする
• 各関数をそのトレイトのメソッドとして、最初のパラメータの代わりに this を用い、残りをそのメソッドの普通のパラメータとする

これにより、本節の最初に見せた Scala の表現が得られる。

Scala における余データの表現についての話はまだ終わりではない。続いて、先ほど定義したインターフェースを実際に実装する必要がある。実装のアプローチは三つある。

1. final サブクラス。これは実装に名前を付けたい場合に用いる
2. 匿名のサブクラス
3. 稀なケースだが、object

final なサブクラスも匿名サブクラスもそれ以上拡張できないため、深い継承階層を作成することはできない。これにより、深い継承階層をもったコードを理解する際に生じる困難を回避できる。また、case class ではなく class を使用することで、コンストラクタ引数などの実装の詳細を公開せずにすむ。

いくつか例を挙げよう。ここでは、List を使って集合の要素を保持する Set 実装の単純な例を示す。

final class ListSet[A](elements: List[A]) extends Set[A] {

  def contains(elt: A): Boolean =
    elements.contains(elt)

  def insert(elt: A): Set[A] =
    ListSet(elt :: elements)

  def union(that: Set[A]): Set[A] =
    elements.foldLeft(that) { (set, elt) => set.insert(elt) }
}
object ListSet {
  def empty[A]: Set[A] = ListSet(List.empty)
}

この例ではひとつ目の実装アプローチとして紹介した final サブクラスを用いている。匿名サブクラスは、余データ型を返すメソッドを実装するときにもっとも便利である。union メソッドを例に考えてみよう。このメソッドは余データ自体の型である Set を返す。これは以下のように実装することができる。

trait Set[A] {
  
  def contains(elt: A): Boolean
  
  def insert(elt: A): Set[A]
  
  def union(that: Set[A]): Set[A] = {
    val self = this
    new Set[A] {
      def contains(elt: A): Boolean =
        self.contains(elt) || that.contains(elt)
        
      def insert(elt: A): Set[A] =
        // self と that どちらに insert してもよい
        self.insert(elt).union(that)
    }
  }
}

この例では、匿名サブクラスを使用して Set トレイトの union を実装している。この定義はすべてのサブクラスから利用できる。メソッドを final にしていないのは、サブクラスがもっと効率的な実装でそれをオーバーライドできるようにするためである。これにより、実装継承に伴う危険性が生じる。これは、実践がいつも原則どおりに行われるわけではないことを示す例である。原則的には実装継承は好まれないが、実際には最適化として有用である場合がある。

デストラクタのみを用いて定義されたユーティリティメソッドを実装することも有用である。たとえば、Iterable コレクション内のすべての要素を contains しているか確認する containsAll メソッドを Set に実装したいとする。

def containsAll(elements: Iterable[A]): Boolean

このメソッドは Set の containts と Iterable の forall だけを使って実装できる。

trait Set[A] {
  
  def contains(elt: A): Boolean
  
  def insert(elt: A): Set[A]
  
  def union(that: Set[A]): Set[A]
  
  def containsAll(elements: Iterable[A]): Boolean =
    elements.forall(elt => this.contains(elt))
}

ここでも、メソッドを final にするという選択肢がある。このケースでは、より効率的な実装を想像するのは難しいため、final にすることは先ほどの例より正当であると言えるだろう。

データと余データは、Scala においては、クラスとオブジェクトというひとつの言語機能の別の側面として実現されている。これは、データと余データ両方の特性をもつ型を定義できることを意味する。実際、我々はすでにこれを行っている。データを定義する際には、データ内のフィールドの名前を定義しなければならず、それによってデストラクタが定義される。これは、データと余データの間に明確な区別を設けていないほとんどの言語と同じである。

クラスとオブジェクトの魅力の一端は、ひとつの言語構造を用いて非常に多くの概念的に異なる抽象を表現できる点にあると考えている。このことは、クラスやオブジェクトを表面的には単純に見せ、ひとつの抽象さえ学べば多くのコーディングに関する問題を解決できるかのように感じさせる。だが、この見かけ上の単純さは実際の複雑さを隠している。同じ言語構造がさまざまな用途に使われるせいで、コードから概念的な意図を逆解析する必要が生じるのである。

3.3 余データの構造的再帰と余再帰

この節では、遅延リストとしても知られているストリームを扱うライブラリを作成する。ストリームはリストの余データに相当する。リストの長さが有限でなくてはならないのに対して、ストリームは無限の長さをもっている。この例を用いて、余データに適用される構造的再帰と構造的余再帰について考察する。

まずは構造的再帰と構造的余再帰について復習しておこう。構造的再帰では入力の型を、構造的余再帰では出力の型をそれぞれ用いてメソッドの記述プロセスを進めるというのが、その基本となるアイデアである。これらがデータに対してどのように動作するのかはすでに見たとおりで、そこでは構造的再帰のほうがより重要であった。余データにおいては構造的余再帰のほうが頻繁に使用される。構造的余再帰を使用するためのステップは以下のとおりである。

1. メソッドや関数の出力が余データであることを認識する
2. 余データ型のインスタンスを構築する骨組みを記述する。通常は匿名サブクラスを使用する
3. 構造的再帰などの戦略を用いるか、型に従いながら、メソッドの本体を完成させる

計算はすべてメソッド内で行われ、メソッド呼び出し時にのみ実行されることが重要である。ストリームを作成し始めると、この重要性が明確になるだろう。

構造的再帰の手順は以下のとおりである。

1. メソッドや関数の入力が余データであることを認識する
2. メソッドを書くにあたり、余データのデストラクタが値の供給源であることに留意する
3. 型追従や構造的余再帰といった戦略を用いたり、上記で特定したデストラクタを使ったりして、メソッドを完成させる

最初のステップはストリーム型を定義することである。ストリームは余データなので、デストラクタの集まりとして定義される。A 型の要素をもつ Stream を定義するデストラクタは以下のとおりである。

• A 型の head
• Stream[A] 型の tail

これらが List のデストラクタとほぼ同じである点に注目しよう。デストラクタとして isEmpty を定義していないのは、ここで作成しようとしているストリームに終わりがなく、isEmpty があったとしてもそれは常に false を返すことになるからである。なお、Scala 標準ライブラリの LazyList など多くの実例においては isEmpty のようなメソッドが定義されており、有限と無限両方のリストを同じ構造で表現することが可能となっている。ここでは、余データをもっとも端的な形で定義したいので、シンプルさを優先し、そのようなことはしない。

上記の定義を Scala に翻訳すると、これまでにも見てきたように、次のようになる。

trait Stream[A] {
  def head: A
  def tail: Stream[A]
}

これで、Stream インスタンスを作成できる。ここでは、永遠に 1 という数を返し続けるストリームを作成してみよう。以下の骨組みから始め、戦略をいくつか適用してコードを完成させる。

val ones: Stream[Int] = ???

最初の戦略は構造的余再帰である。余データのインスタンスを返したいのだから、 Stream インスタンス構築の骨組みを挿入すればよい。

val ones: Stream[Int] =
  new Stream[Int] {
    def head: Int = ???
    def tail: Stream[Int] = ???
  }

ここでは、匿名サブクラスのアプローチを使い、すべてのコードを一か所にまとめて書けるようにしている。

次のステップはメソッド本体を埋めることである。最初のメソッドである head は簡単で、定義により答えは 1 である。

val ones: Stream[Int] =
  new Stream[Int] {
    def head: Int = 1
    def tail: Stream[Int] = ???
  }

tail をどのように実装すればよいかは自明とは言えない。Stream[Int] 型の値を返したいのだから、もう一度構造的余再帰の戦略を適用することが考えられる。

val ones: Stream[Int] =
  new Stream[Int] {
    def head: Int = 1
    def tail: Stream[Int] =
      new Stream[Int] {
        def head: Int = 1
        def tail: Stream[Int] = ???
      }
  }

だが、このアプローチがうまく行くとは思えない。この方法でメソッドを正しく実装するには同じことを無限に書き続けなくてはならない。

代わりに、型に従って考えてみよう。Stream[Int] 型を返す必要があるが、スコープ内にはその型の変数である ones がすでに存在する。これこそがまさに、返すべき無限の 1 のストリームである。

val ones: Stream[Int] =
  new Stream[Int] {
    def head: Int = 1
    def tail: Stream[Int] = ones
  }

tail で ones への循環参照を見て驚くかもしれないが、これは問題ない。この参照はメソッド内にあり、メソッドが呼び出されたときにのみ評価される。原理上は無限でも、実際にはその限られた部分しか評価されない。この評価の遅延こそが、無限の要素を表現できる理由である。これは、データのように構築時にすべてが評価されるものとは根本的に異なる点である。

この ones の定義が確かに動作することを確認しておこう。無限のストリームからすべての要素を取り出すことはできない（少なくとも有限の時間内では）。したがって、現実的には有限の要素列を確認することに頼らざるを得ない。

ones.head
// res26: Int = 1
ones.tail.head
// res27: Int = 1
ones.tail.tail.head
// res28: Int = 1

これらはすべて正しいようである。動作確認にはこの方法を使うことが多いので、これをもっと簡単にしてくれるメソッド take を実装しよう。

trait Stream[A] {
  def head: A
  def tail: Stream[A]
  
  def take(count: Int): List[A] =
    count match {
      case 0 => Nil
      case n => head :: tail.take(n - 1)
    }
}

take の実装には、データに対する構造的再帰か構造的余再帰いずれかの戦略を利用できる。その手順については既に詳しく説明しているので、ここでは触れない。重要なのは、take がデストラクタのみを通じて Stream とやり取りしているということである。

これで、実装が正しいことをもっと簡単に確認できるようになる。

ones.take(5)
// res30: List[Int] = List(1, 1, 1, 1, 1)

次の課題として map を実装する。Stream にメソッドを実装することで、余データにおける構造的再帰と構造的余再帰の両方を実際に確認することができる。いつものようにメソッドの骨組みを書き出すところから始める。

trait Stream[A] {
  def head: A
  def tail: Stream[A]
  
  def map[B](f: A => B): Stream[B] = 
    ???
}

利用する戦略を決めなくてはならない。まだ構造的再帰を使っていないので、まずはそれを試してみよう。入力は余データ Stream である。構造的再帰戦略ではデストラクタを用いることを検討すべきとされているので、リマインドの意味でデストラクタ呼び出しを書き出しておこう。

trait Stream[A] {
  def head: A
  def tail: Stream[A]
  
  def map[B](f: A => B): Stream[B] = {
    this.head ???
    this.tail ???
  }
}

さらに実装を進めるのに、型に従う手法か構造的余再帰を利用できる。構造的余再帰の使用例をもうひとつ見てみたいので、そちらを選択することにしよう。

trait Stream[A] {
  def head: A
  def tail: Stream[A]
  
  def map[B](f: A => B): Stream[B] = {
    this.head ???
    this.tail ???
    
    new Stream[B] {
      def head: B = ???
      def tail: Stream[B] = ???
    }
  }
}

これで構造的再帰と構造的余再帰の戦略を使ったので、次は型に従う方法をすこし試してみよう。すぐに正しい解答にたどり着くことができる。

trait Stream[A] {
  def head: A
  def tail: Stream[A]
  
  def map[B](f: A => B): Stream[B] = {
    val self = this 
    new Stream[B] {
      def head: B = f(self.head)
      def tail: Stream[B] = self.tail.map(f)
    }
  }
}

重要な点がふたつある。まず見てほしいのは、this に self という名前を与えたことである。作成しようとしている新しい Stream オブジェクトの中では this はその新しいストリーム自体を指すので、その中で元の Stream オブジェクトを参照するにはこれが必要となる。次に、self.head と self.tail へのアクセスが、新しい Stream に定義されたメソッドの中で行われている点に注目してほしい。これによって、必要とされたときにのみ計算を行うという正しいセマンティクスが維持される。メソッド外で計算を行うと、必要以上に早く評価されてしまい、場合によっては無限ループにつながることもある。

フォーカスを Stream の構築に戻そう。最後の例として、汎用的なコンストラクタである unfold を実装する。seed パラメータについても考慮しつつ、まずは unfold の骨組みから始める。

trait Stream[A] {
  def head: A
  def tail: Stream[A]
}
object Stream {
  def unfold[A, B](seed: A): Stream[B] =
    ???
}

構造的余再帰を適用して実装を進めるのが自然だろう。

trait Stream[A] {
  def head: A
  def tail: Stream[A]
}
object Stream {
  def unfold[A, B](seed: A): Stream[B] =
    new Stream[B]{
      def head: B = ???
      def tail: Stream[B] = ???
    }
}

次に、型に従って、必要に応じたパラメータを追加する。これにより、メソッドは以下のとおり完成する。

trait Stream[A] {
  def head: A
  def tail: Stream[A]
}
object Stream {
  def unfold[A, B](seed: A, f: A => B, next: A => A): Stream[B] =
    new Stream[B]{
      def head: B = 
        f(seed)
      def tail: Stream[B] = 
        unfold(next(seed), f, next)
    }
}

これを使って、おもしろいストリームを実装できる。以下に示すのは 1 と -1 が交互に現れるストリームである。

val alternating = Stream.unfold(
  true, 
  x => if x then 1 else -1, 
  x => !x
)

動作を確認しておこう。

alternating.take(5)
// res37: List[Int] = List(1, -1, 1, -1, 1)

演習: Stream のコンビネータ実装

このあたりで、余データを用いた構造的再帰と構造的余再帰について練習をしておこう。Stream に filter、zip、および scanLeft メソッドを実装せよ。いずれも List における同名のメソッドと同じセマンティクスをもっているものとし、シグネチャは以下のとおりとする。

trait Stream[A] {
  def head: A
  def tail: Stream[A]

  def filter(pred: A => Boolean): Stream[A]
  def zip[B](that: Stream[B]): Stream[(A, B)]
  def scanLeft[B](zero: B)(f: (B, A) => B): Stream[B]
}

trait Stream[A] {
  def head: A
  def tail: Stream[A]

  def filter(pred: A => Boolean): Stream[A] = {
    val self = this
    new Stream[A] {
      def head: A = {
        def loop(stream: Stream[A]): A =
          if pred(stream.head) then stream.head
          else loop(stream.tail)
          
        loop(self)
      }
      
      def tail: Stream[A] = {
        def loop(stream: Stream[A]): Stream[A] =
          if pred(stream.head) then stream.tail.filter(pred)
          else loop(stream.tail)
          
        loop(self)
      }
    }
  }

  def zip[B](that: Stream[B]): Stream[(A, B)] = {
    val self = this 
    new Stream[(A, B)] {
      def head: (A, B) = (self.head, that.head)
      
      def tail: Stream[(A, B)] =
        self.tail.zip(that.tail)
    }
  }

  def scanLeft[B](zero: B)(f: (B, A) => B): Stream[B] = {
    val self = this
    new Stream[B] {
      def head: B = zero
      
      def tail: Stream[B] =
        self.tail.scanLeft(f(zero, self.head))(f)
    }
  }
}

上記で定義したメソッドを使うと、クールなことができる。たとえば、次に示すのは自然数のストリームである。

val naturals = Stream.ones.scanLeft(0)((b, a) => b + a)

いつもどおり、動作確認をしておこう。

naturals.take(5)
// res41: List[Int] = List(0, 1, 2, 3, 4)

unfold を用いて naturals を定義することもできる。もっと興味深いのは、naturals 自身を使って naturals を定義できることである。

val naturals: Stream[Int] =
  new Stream {
    def head = 1
    def tail = naturals.map(_ + 1)
  }

これはややこしいかもしれないが、もしそう思ったらすこし時間をとって考えてみてほしい。この実装はちゃんと動作するのである。

naturals.take(5)
// res43: List[Int] = List(1, 2, 3, 4, 5)

3.3.1 効率と副作用

上記の実装において、値を場合によっては何度も繰り返し再計算していることに気付いたかもしれない。filter の実装がそのよい例である。head と tail は呼び出すたびに再計算を行うため、非常にコストの高い操作になる可能性がある。

def filter(pred: A => Boolean): Stream[A] = {
  val self = this
  new Stream[A] {
    def head: A = {
      def loop(stream: Stream[A]): A =
        if pred(stream.head) then stream.head
        else loop(stream.tail)
        
      loop(self)
    }
    
    def tail: Stream[A] = {
      def loop(stream: Stream[A]): Stream[A] =
        if pred(stream.head) then stream.tail.filter(pred)
        else loop(stream.tail)
        
      loop(self)
    }
  }
}

メソッドが呼び出されるまで計算を遅延することの重要性はすでに述べた。それによって無限の、そして自己参照的なデータを扱うことができるからである。だが、そのメソッドが連続して呼び出されるときに計算をやり直す必要はない。最初の呼び出し時に結果をキャッシュしておけば、次回からはそれを使用できる。Scala では lazy val を使うことでこれを簡単に実現できる。lazy val は、最初に呼び出されるまで評価されない val である。さらに、Scala は統一形式アクセスの原則を採用しており、引数をもたないメソッドは lazy val を使って実装することができる。以下はその使用方法を示す簡単な例である。

def always[A](elt: => A): Stream[A] =
  new Stream[A] {
    lazy val head: A = elt
    lazy val tail: Stream[A] = always(head)
  }
  
val twos = always(2)

いつもどおり動作確認をしておこう。

twos.take(5)
// res44: List[Int] = List(2, 2, 2, 2, 2)

メソッドと lazy val どちらを使っても同じ結果が得られる。可変状態に依存しない純粋な計算のみを扱っている想定だからである。そのような場合において、lazy val はメモリを追加で消費する代わりに時間を節約する役割を果たす。

必要になるたびに結果を再計算する方式は名前渡し（call by name）と呼ばれ、最初に計算された結果をキャッシュしておく方式は必要渡し（call by need）と呼ばれる。このふたつの異なる評価戦略は、今回のように個々の値に適用されることもあるし、プログラム全体にわたって適用されることもある。例として、Haskell では必要渡しが用いられており、すべての値はそれが必要となる最初のタイミングでのみ計算される。このアプローチは遅延評価と呼ばれることもある。値渡し（call by value）と呼ばれる別の方式では、結果が必要とされるのを待たず、定義された時点で計算される。Scala はデフォルトでこの方式をとる。

純粋でない計算を使って、名前渡しと必要渡しの違いを示すことができる。たとえば、乱数のストリームを定義してみよう。乱数生成器は内部状態に依存している。

以下は、名前渡しを用いた実装である。実装には本書でこれまでに定義したメソッドを用いている。

import scala.util.Random

val randoms: Stream[Double] = 
  Stream.unfold(Random, r => r.nextDouble(), r => r)

Stream の一部を take するたびに、異なる結果が得られることに注目してほしい。これらの結果は本来同じであることが期待される。

randoms.take(5)
// res45: List[Double] = List(
//   2.2924799822798825E-5,
//   0.03381951041268916,
//   0.2005697625333388,
//   0.6090609303314423,
//   0.8407442035068102
// )
randoms.take(5)
// res46: List[Double] = List(
//   0.44854748878414485,
//   0.6259186751000002,
//   0.8593839485682416,
//   0.980693092386352,
//   0.6800212819857074
// )

次に、lazy val を使い、必要渡しスタイルで同じストリームを定義してみよう。

val randomsByNeed: Stream[Double] =
  new Stream[Double] {
    lazy val head: Double = Random.nextDouble()
    lazy val tail: Stream[Double] = randomsByNeed
  }

今回は、ストリームの一部を take したときに得られる結果は同じになる。ただし、どの数もすべて同じになってしまう。

randomsByNeed.take(5)
// res47: List[Double] = List(
//   0.4960531325200994,
//   0.4960531325200994,
//   0.4960531325200994,
//   0.4960531325200994,
//   0.4960531325200994
// )
randomsByNeed.take(5)
// res48: List[Double] = List(
//   0.4960531325200994,
//   0.4960531325200994,
//   0.4960531325200994,
//   0.4960531325200994,
//   0.4960531325200994
// )

要素ごとに異なる乱数をもちつつ、それぞれの値は固定値であるようなストリームを作りたい場合、遅延評価を用いるように unfold を再定義する必要がある。

def unfoldByNeed[A, B](seed: A, f: A => B, next: A => A): Stream[B] =
  new Stream[B]{
    lazy val head: B = 
      f(seed)
    lazy val tail: Stream[B] = 
      unfoldByNeed(next(seed), f, next)
  }

unfoldByNeed を使って randomsByNeed を再定義することで、求めている結果を得ることができる。下記のとおり再定義を行い、動作を確認しよう。

val randomsByNeed2 =
  unfoldByNeed(Random, r => r.nextDouble(), r => r)

randomsByNeed2.take(5)
// res49: List[Double] = List(
//   0.37666168899861174,
//   0.9405825156798319,
//   0.5628726849362917,
//   0.0924808960507496,
//   0.6846216853892201
// )
randomsByNeed2.take(5)
// res50: List[Double] = List(
//   0.37666168899861174,
//   0.9405825156798319,
//   0.5628726849362917,
//   0.0924808960507496,
//   0.6846216853892201
// )

これらの微妙な問題は、関数型プログラマが可能なかぎり状態を使用しないよう努める理由のひとつである。

3.4 データと余データの関係

この節では、データと余データの関係、特にそれらの間の相互変換について探求する。まずは両者の表面的な関係を確認し、その後、fold を通じた深い結びつきを見ていく。

データは積の和で構成されており、その積の部分がコンストラクタとなることを思い出してほしい。コンストラクタは関数として見ることができるので、データは関数の和として捉えることができる。一方、余データは関数の積である。コンストラクタとしての関数と余データにおける関数の間には、直接的な対応関係を簡単に見出すことができる。では、和と積の違いはどうだろうか。関数の積があるとき、コードのある場所において呼び出すことのできる関数はどれかひとつだけである。つまり、論理和はどの関数を呼び出すかという選択のなかに存在する。

そのことを、データの代表例である List を使って見てみよう。List は代数的データ型として次のように定義できる。

enum List[A] {
  case Pair(head: A, tail: List[A])
  case Empty()
}

余データに相当するものは以下のとおりである。

trait List[A] {
  def pair(head: A, tail: List[A]): List[A]
  def empty: List[A]
}

この余データの定義では、コンストラクタを明示的にメソッドとして表現し、コンストラクタの選択を呼び出し側に委ねている。この関係性が役に立つ場面をすこし先の章で見ることになるが、今はその話題から離れ、次に進むことにする。

両者の関係を見るもうひとつの方法は fold を通じたつながりである。任意の代数的データ型に対して fold を導出する方法はすでに学んだ。たとえば、次のように定義される Bool について考えてみよう。

enum Bool {
  case True
  case False
}

fold メソッドは以下のように実装される。

enum Bool {
  case True
  case False
  
  def fold[A](t: A)(f: A): A =
    this match {
      case True => t
      case False => f
    }
}

知ってのとおり、fold には、どんなメソッドでもこれを用いて記述できるという汎用性がある。それゆえ fold は汎用デストラクタでもあり、データを余データとして扱うための鍵でもある。Bool において fold は、我々が普段は if 式と呼び、頻繁に使っているものである。

以下は、Bool の余データバージョンである。fold は if にリネームした（ Scala では、if のようなキーワードと同名のメソッドを定義できるが、キーワードを識別子として利用する際にはバッククォートで囲む必要がある）。

trait Bool {
  def `if`[A](t: A)(f: A): A
}

次に、Bool のふたつのインスタンスを純粋に余データとして定義する。

val True = new Bool {
  def `if`[A](t: A)(f: A): A = t
}

val False = new Bool {
  def `if`[A](t: A)(f: A): A = f
}

この if メソッドを実際に使ってみよう。if を用いて and を定義し、その使用例をいくつか示す。

def and(l: Bool, r: Bool): Bool =
  new Bool {
    def `if`[A](t: A)(f: A): A =
      l.`if`(r)(False).`if`(t)(f)
  }

以下がその例である。and は単純なので、真理値表のすべての組み合わせを試すことができる。

and(True, True).`if`("yes")("no")
// res15: String = "yes"
and(True, False).`if`("yes")("no")
// res16: String = "no"
and(False, True).`if`("yes")("no")
// res17: String = "no"
and(False, False).`if`("yes")("no")
// res18: String = "no"

演習: Bool 余データへの or と not の実装

Bool 余データについての理解度を確認するため、上記の and を実装したのと同じ方法で or と not を実装せよ。

def or(l: Bool, r: Bool): Bool =
  new Bool {
    def `if`[A](t: A)(f: A): A =
      l.`if`(True)(r).`if`(t)(f)
  }

def not(b: Bool): Bool =
  new Bool {
    def `if`[A](t: A)(f: A): A =
      b.`if`(False)(True).`if`(t)(f)
  }