『Scala関数型デザイン&プログラミング』の演習問題をScala3で解く その3

blog.magnolia.tech

前回のエントリの続き。第3章の演習問題を解きます。

関数型プログラミングのデータ構造

第3章は、代表的なデータ構造であるimmutableなListの実装を通じて、概念と操作を理解していく章になっています。

この章をいきなり始めてもよいのですが、コップ本の愛称でおなじみの『Scalaスケーラブルプログラミング 第4版』の「第22章リストの実装」という章があり、Scalaの標準ライブラリにおける実装が解説されていますので、そちらを先に読んでおくと理解が早いでしょう(なお、この章は残念ながらScala3対応版の第5版では無くなっています)。

Scalaスケーラブルプログラミング 第4版 impress top gearシリーズ

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

enum

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の実装に適用してみましょう。