前回のエントリの続き。第3章の演習問題を解きます。
関数型プログラミングのデータ構造
第3章は、代表的なデータ構造であるimmutableなList
の実装を通じて、概念と操作を理解していく章になっています。
この章をいきなり始めてもよいのですが、コップ本の愛称でおなじみの『Scalaスケーラブルプログラミング 第4版』の「第22章リストの実装」という章があり、Scalaの標準ライブラリにおける実装が解説されていますので、そちらを先に読んでおくと理解が早いでしょう(なお、この章は残念ながらScala3対応版の第5版では無くなっています)。
enumによるListの実装
演習問題では、Listはsealed trait
を使って実装されていますが、ここではScala3から導入されたenum
を使って実装します。
先立ってScala3の公式ドキュメントの「ALGEBRAIC DATA TYPES」を読んでおくと良いでしょう。
Algebraic Data Types | Scala 3 Language Reference | Scala Documentation
Option
クラスの例にした実装例が掲載されていますが、Listもほぼ同じ構造で実装できます。
enum List[+A]: case Nil case Cons(head: A, tail: List[A])
従来のsealed traitに比較するとextends
を使って明示的に継承を書かなくてよくなった分だけ、スッキリしました。
また、型推論の効き方がより、本来のやりたいことに近くなるように改善されています。
sealed trait
scala> sealed trait List[+A] | case class Cons[A](head: A, tail: List[A]) extends List[A] | case object Nil extends List[Nothing] // defined trait List // defined case class Cons // defined case object Nil scala> val l = Cons(42, Nil) val l: Cons[Int] = Cons(42,Nil) scala> val n = Nil val n: Nil.type = Nil
scala> enum List[+A]: | case Nil | case Cons(head: A, tail: List[A]) | // defined class List scala> import List.* scala> val l = Cons(42, Nil) val l: List[Int] = Cons(42,Nil) scala> val n = Nil val n: List[Nothing] = Nil
また、Scala3における型推論の改善により従来引数の定義にカリー化が必要だった箇所が、不要になっています。
Scala2
def dropWhile[A](as: List[A])(f: A => Boolean): List[A] = ???
Scala3
def dropWhile[A](as: List[A], f: A => Boolean): List[A] = ???
型推論のためだけに必要だった演習問題のカリー化を外してみましょう。
テストを書く
あとは実装し、テストで確認していきます。
class Chapter1ListSpec extends AirSpec: // EXERCISE 3.2 tailメソッドのテスト // 先頭を除いた残りの要素を返却する test("tail") { val list = List(1, 2, 3) List.tail(Nil: List[Int]) shouldBe Nil List.tail(list) shouldBe List(2, 3) }
実装に迷ったら、先に標準ライブラリ用のテストを書いてみて、そのテストを自分で作ったListの実装に適用してみましょう。