🐯

map を使いこなせるあなたに traverse

に公開
Scala
関数型プログラミング
cats
tech

はじめに

この記事は ScalaMatsuri 2023 で発表されるセッション「traverseを制する者はコードを制す」の補完記事です。セッション時間の都合上カットした traverse の実装面を焦点に解説します。

traverse がどういったシーンで役に立つのか等は本セッションをご参照ください。

使用する言語・ライブラリのバージョンは以下の通りです。

  • Scala 3.2.2
  • cats 2.7.0

構造を保ったまま要素に関数を適用する

さて traverse とはどんな関数なのかと言うと、構造を保ったまま要素に関数を適用する関数です。

そう聞くと最近のメジャーな言語にはおおよそ存在している map の事を思い浮かべる方も居る事でしょう。

その通り map も構造を保ったまま要素に関数を適用する関数と言えます。

val list = List(1, 2, 3, 4, 5)
list.map(_ * 2) // List(2, 4, 6, 8, 10)

上記のコードは、元のリストの構造を保ったまま各要素を2倍するという関数を適用した例ですね。

もう少し具体例を通じて構造を保つという所を注目するために map の実装を見てみましょう。

enum MyList[+A] {
  case Nil
  case Cons(head: A, tail: MyList[A])
}

例のために独自でリストを定義してみました。標準APIにある List と似たような感じで Nil と Cons で構成されています。

この MyList に map を定義すると以下のようになります。

enum MyList[+A] {
  case Nil
  case Cons(head: A, tail: MyList[A])

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

自身が Nil であればそのまま Nil を保ちます。

Cons であれば保持している要素 head と tail に対して引数で渡された関数を適用します。tail は再帰的構造のため map を再帰呼び出しすることで適用しています。 そしてそれぞれの結果を元の構造である Cons として構築しなおすことで元の構造を保ちます。

実際に動かしてみると以下のようになります。

import MyList._
val list = Cons(1, Cons(2, Cons(3, Nil)))
list.map(_ * 2) // Cons(2, Cons(4, Cons(6, Nil)))

1例だけじゃ何なので Tree の例も見てみましょう。

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

単純な二分木ですね。Leaf が要素を保持し、Branch が left, right それぞれに Tree を再帰的に保持しています。

この map の実装も次の通りです。

enum Tree[+A] {
  case Leaf(value: A)
  case Branch(left: Tree[A], right: Tree[A])

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

自身が Leaf であればその要素に引数で渡された関数を適用し、その結果を Leaf に構築しなおしています。

Branch であれば、left, right それぞれに map を再帰呼び出しを行い、その結果を Branch として構築しなおして元の構造を保っています。

使ってみましょう。

import Tree._
val tree = Branch(Leaf(1), Branch(Leaf(2), Leaf(3)))
tree.map(_ * 2) // Branch(Leaf(2), Branch(Leaf(4), Leaf(6)))

この様に map は構造を保ったまま要素に関数を適用する関数と言えます。

文脈を伴う関数

さて map が構造を保ったまま要素に関数を適用する関数だと言えることについて解説しましたが、では本題の traverse は何なのでしょうか？

実は traverse も構造を保ったまま要素に関数を適用する関数です。そして map との違いは各要素に適用する関数が文脈を伴う関数であるという点です。

日本語が難しいですね。文脈を伴う関数とはいったいどんな関数なのでしょうか？

まずは traverse のシグネチャを見てみましょう。先に例で定義した MyList に traverse を生やしてみます。

enum MyList[+A] {
  case Nil
  case Cons(head: A, tail: MyList[A])
  ...

  def traverse[G[_]: Applicative, B](f: A => G[B]): G[MyList[B]] = ???
}

これまたちょっと複雑な定義ですが、一旦 : Applicative を無視して見てください。そうすると以下のようになります。

  def traverse[G[_], B](f: A => G[B]): G[MyList[B]] = ???

型引数として G[_] が追加されています。 この [_] は G もまた何かしら型引数を一つとる事を表しています。つまり List や Option といった型を G[_] に指定することができるという事ですね。

また引数の型が A => G[B] になっています。これは引数として Int => Option[String] だったり String => List[Int] といった何らかに包まれた値を返す関数を渡すことができる、という訳です。

要するにこの G[_] の事を文脈と称していた訳ですね。

そして戻り値の型が G[MyList[B]] になっています。例えば引数に Int => Option[String] が渡された場合は Option[MyList[String]] になります。この場合 Optionという文脈(計算が失敗する可能性がある文脈)の中で元の構造を保った値を返している、という訳です。

次に G[_] にはどんな型が当て嵌められるのかという話になりますが、ここで先ほど忘れてもらった : Applicative を思い出して頂く必要があります。

  def traverse[G[_]: Applicative, B](f: A => G[B]): G[MyList[B]] = ???

これは G[_] に当てはめる型が Applicative という型クラスのインスタンスを持っている必要があるという事を表します。

例えば G[_] に対して Option を当て嵌めたい場合、スコープ中に Applicative[Option] 型の implicit value が存在する必要がある、という事ですね。 Option をはじめここで使いたくなるような一般的な型は cats を使っていれば標準で提供してくれているのであまり深く気にする必要はありません。

この Applicative がどんな型クラスなのか、という説明は世にいっぱい解説記事が在るので詳しくはそちらに譲ります。自分が判りやすいと思う記事をご確認ください。

ここでは以下の二つのメソッドを持った型クラスとだけ認識していただければ大丈夫です。

  • A 型の値から G[A] 型の値を生成するメソッド pure
  • G[_] に包まれた二つの値、G[A] と G[B] から G[C] という値を生成できるメソッド mapN

この pure と mapN を使って MyList の traverse を実装してみると以下のようになります。

enum MyList[+A] {
  case Nil
  case Cons(head: A, tail: MyList[A])
  ...

  def traverse[G[_]: Applicative, B](f: A => G[B]): G[MyList[B]] = this match {
    case Nil              => Nil.pure
    case Cons(head, tail) => (f(head), tail.traverse(f)).mapN(Cons.apply)
  }
}

自身が Nil であれば、そのまま Nil を保ち pure で G[_] に包みます。

自身が Cons であれば、保持する要素 head と tail に対し引数で渡された関数を適用します。結果がそれぞれ G[_] に包まれた値となるので、mapN を使って元の Cons という構造を保ちます。

単純ですね。

少し使ってみましょう。文字列を持つ MyList の各要素に対し toIntOption 呼び出しを引数として与えてみます。

// 全て数値に変換可能な文字列
val list1 = Cons("1", Cons("2", Cons("3", MyList.Nil)))
list1.traverse(_.toIntOption) // Some(Cons(1, Cons(2, Cons(3, Nil))))

// 数値に変換できない文字列 a を持つ
val list2 = Cons("1", Cons("a", Cons("3", MyList.Nil)))
list2.traverse(_.toIntOption) // None

文脈に応じて結果が変わっていることが見て取れますね。

map と traverse の比較

ここで改めて MyList の map と traverse の実装を比較してみましょう。そっくりな事がお判りいただけると思います。

enum MyList[+A] {
  case Nil
  case Cons(head: A, tail: MyList[A])

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

  def traverse[G[_]: Applicative, B](f: A => G[B]): G[MyList[B]] = this match {
    case Nil              => Nil.pure
    case Cons(head, tail) => (f(head), tail.traverse(f)).mapN(Cons.apply)
  }
}

さらに普通はこんな迂遠な書き方はしないですがより比較を際立たせるために scala.util.chaining を使って map を少し変形してみましょう。

enum MyList[+A] {
  case Nil
  case Cons(head: A, tail: MyList[A])

  def map[B](f: A => B): MyList[B] = this match {
    case Nil              => Nil
    case Cons(head, tail) => (f(head), tail.map(f)).pipe(Cons.apply)
  }

  def traverse[G[_]: Applicative, B](f: A => G[B]): G[MyList[B]] = this match {
    case Nil              => Nil.pure
    case Cons(head, tail) => (f(head), tail.traverse(f)).mapN(Cons.apply)
  }
}

差が .pure が有るか無いか、pipe か mapN か、の二つだけになりました。本当にそっくりですね。

同じように Tree にも traverse を実装して比較してみましょう。こちらも scala.util.chaining を使って map を変形してあります。

enum Tree[+A] {
  case Leaf(value: A)
  case Branch(left: Tree[A], right: Tree[A])

  def map[B](f: A => B): Tree[B] = this match {
    case Leaf(value   => f(value).pipe(Leaf.apply)
    case Branch(l, r) => (l.map(f), r.map(f)).pipe(Branch.apply)
  }

  def traverse[G[_]: Applicative, B](f: A => G[B]): G[Tree[B]] = this match {
    case Leaf(value)  => f(value).map(Leaf.apply)
    case Branch(l, r) => (l.traverse(f), r.traverse(f)).mapN(Branch.apply)
  }
}

こちらもそっくりな事がお判り頂けるかと思います。 pipe が map か mapN に変わっただけですね。

使用してみると以下のようになります。

// 全て数値に変換可能な文字列
val tree1 = Branch(Leaf("1"), Branch(Leaf("2"), Leaf("3")))
tree1.traverse(_.toIntOption) // Some(Branch(Leaf(1), Branch(Leaf(2), Leaf(3))))

// 数値に変換できない文字列 a を持つ
val tree2 = Branch(Leaf("1"), Branch(Leaf("a"), Leaf("3")))
tree2.traverse(_.toIntOption) // None

この様に traverse は構造を保ったまま要素に文脈を伴う関数を適用する関数だと言うことができます。

おまけ：何もしない文脈

さて map と traverse がそっくりなのであれば、これらを共通化することはできないのでしょうか？ 実は map は traverse を使って実装することもできます。

そこで登場するのが何もしない文脈を表す Id という型です。 Id の型定義は以下のようになっています。

type Id[A] = A

凄いですね。要は Id は型引数を取る型だけれど、実態としてはその型引数で指定された型と同じ型であるという事を示しています。

すなわち Id[String] は String ですし、 Id[Int] は Int です。

この Id を traverse の G[_] に当てはめるとまさに map になります。順を追ってみてみましょう。

まず MyList の traverse の定義は以下の通りです。

  def traverse[G[_]: Applicative, B](f: A => G[B]): G[MyList[B]]

これの G[_] に Id を当て嵌めます。すると以下のようなイメージになります。

  def traverse[/*Id: Applicative,*/ B](f: A => Id[B]): Id[MyList[B]]

Id[A] と A は等しい訳ですから、このシグネチャの意味合いは以下のようになります。

  def traverse[/*Id: Applicative,*/ B](f: A => B): MyList[B]

map のシグネチャは以下の通りです。

  def map[B](f: A => B): MyList[B]

まったく同じになりました。

従って map の実装は以下の様に traverse を使って書くことができます。

  def map[B](f: A => B): MyList[B] = traverse[Id, B](f)

全体を載せると以下のようになります。

enum MyList[+A] {
  case Nil
  case Cons(head: A, tail: MyList[A])

  def map[B](f: A => B): MyList[B] = traverse[Id, B](f)

  def traverse[G[_]: Applicative, B](f: A => G[B]): G[MyList[B]] = this match {
    case Nil              => Nil.pure
    case Cons(head, tail) => (f(head), tail.traverse(f)).mapN(Cons.apply)
  }
}

traverse が map を抽象化した関数であることが伝わったでしょうか？

参考になれば幸いです。

Discussion