16
9

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 1 year has passed since last update.

Day 17

Scala Advent Calendar 2018

@taketora

withFilterを通してScalaのコレクション、データ型を勉強する

16
Last updated at Posted at 2018-12-17

はじめに

普段あまりwithFilterを意識することはないと思いますが、withFilterを切り口にScalaのソースコードを読むと、普段とは違った角度でScalaの階層構造やデータ型が見えてきます。さらに独自に作ったデータ型をfor式で使えるようにかけたり、Scalaの勉強になります。
今回はwithFilterを通して、コレクション周りの階層構造やOption,Try,Either,Futureなどデータ型をみていきたいと思います。

withFilterはfor式の糖衣構文

よくwithFilterが登場してくるタイミングとして、「for式は、map、flatMap、withFilterの糖衣構文である」という説明で登場してきます。

//Personクラスは人の名前、男性か否か、子供は誰かを示すフィールドを持っている。
  case class Person(name:String,isMale:Boolean,children:Person*)

  val ひまわり = Person("ひまわり",false)
  val しんのすけ = Person("しんのすけ",true)
  val みさえ = Person("みさえ",false,ひまわり,しんのすけ)
  val persons  =  List(ひまわり,しんのすけ,みさえ)

for式を使って、母と子全てのペアをだしています。

scala> for{
     |     p <- persons if !p.isMale
     |     c <- p.children
     |   } yield (p.name,c.name)
res0: List[(String, String)] = List((みさえ,ひまわり), (みさえ,しんのすけ))

//for式はコンパイラーによって`withFilter`、`flatMap`、`map`に変換されます。

scala> persons.withFilter( p => !p.isMale).flatMap(p => p.children.map(c => (p.name,c.name)))
res1: List[(String, String)] = List((みさえ,ひまわり), (みさえ,しんのすけ))

//for式に条件が含まれていると、`withFilter`が糖衣構文として使われています。
//※for式に条件(フィルター)がない場合は、コンパイル時に`withFilter`は登場してきません。

このようにwithFilterは直接使うというよりも、for式の糖衣構文として登場してくる程度なので、普段は**「for式で条件(フィルター)が使えるのはwithFilterのおかげなんですね。」**くらいの認識で良いのかなと思います。

しかしこのwithFilterの実装とても奥が深いです。

Scalaの階層やデータ構造の勉強になるので一度深掘っていきましょう。

List型のwithFilterはどこに定義されているのか？

TraversableLike(Traversableの実装トレイト)です。

List型はSeq型の実装のひとつで、Seq型、Map型、Set型はコレクションのデータ型になりますが、コレクションの最上位が、Traversableトレイトになります。

スクリーンショット 2018-12-17 5.38.31.png

このTraversableトレイトがwithFilterを持っており、Traversableの実装トレイトであるTraversableLikeにwithFilterが定義されています。

そのためSeqだけでなく、SetにもMapにもwithFilterが使えます。

下記はTraversableLikeのソースコードです(コメント等を省略しております。)

  • scala.collection.TraversableLike
trait TraversableLike[+A, +Repr] extends Any
//省略
{
  self =>
//省略
  def withFilter(p: A => Boolean): FilterMonadic[A, Repr] = new WithFilter(p)

  class WithFilter(p: A => Boolean) extends FilterMonadic[A, Repr] {

    def map[B, That](f: A => B)(implicit bf: CanBuildFrom[Repr, B, That]): That = {
      val b = bf(repr)
      for (x <- self)
        if (p(x)) b += f(x)
      b.result
    }

    def flatMap[B, That](f: A => GenTraversableOnce[B])(implicit bf: CanBuildFrom[Repr, B, That]): That = {
      val b = bf(repr)
      for (x <- self)
        if (p(x)) b ++= f(x).seq
      b.result
    }

    def foreach[U](f: A => U): Unit =
      for (x <- self)
        if (p(x)) f(x)

    def withFilter(q: A => Boolean): WithFilter =
      new WithFilter(x => p(x) && q(x))
  }

少し見慣れませんが注目するポイントは2つあります。

  1. withFilterメソッドを呼び出すと、引数の関数pを渡して**WithFilterクラスをインスタンス化**している点
  2. WithFilterクラスでFilterMonadicを継承している点

一個づつみていきます。

  1. withFilterメソッドを呼び出すと、引数の関数pを渡して**WithFilterクラスをインスタンス化**している

これはなぜでしょうか？

これは新しいコレクションを作らないようにしているためです。　FilterMonadicを使ってCanBuildFromを呼び出し、WithFilterクラスをインスタンス化することで、新しいコレクションを作らずにfilter後に処理を繋げています。さらに、このような作りにすることによって、WithFilterクラスの中でさらにwithFilterメソッドを呼び出すこともできます。

//WithFilterクラスの中で、さらにWithFilterをクラスを生成している。
    def withFilter(q: A => Boolean): WithFilter = new WithFilter(x => p(x) && q(x))

新たに関数pと関数qを論理積した関数をWithFilterクラスのコンストラクタ引数にすることで、withFilterとwithFilterのメソッドを連結しています。

2. WithFilterクラスでFilterMonadicを継承している点
scala> List(1,2,3,4,5,6).withFilter( _ > 4)
res0: scala.collection.generic.FilterMonadic[Int,List[Int]] = scala.collection.TraversableLike$WithFilter@31a57b83

withFilterメソッドを使うと、FilterMonadic型になります。

このFilterMonadicとは何でしょうか？

  • scala.collection.generic.FilterMonadic 
trait FilterMonadic[+A, +Repr] extends Any {
  def map[B, That](f: A => B)(implicit bf: CanBuildFrom[Repr, B, That]): That
  def flatMap[B, That](f: A => scala.collection.GenTraversableOnce[B])(implicit bf: CanBuildFrom[Repr, B, That]): That
  def foreach[U](f: A => U): Unit
  def withFilter(p: A => Boolean): FilterMonadic[A, Repr]
}

型パラメーターAは要素、型パラメーターReprはコレクションの型が入ります。

A template trait that contains just the map, flatMap, foreach and withFilter methods of trait TraversableLike.

FilterMonadicのコメントには「TraversableLikeのmap、flatMap、foreach、withFilterのみのを含むトレイトです。」となっています。名前について推測ですが注釈に個人的な解釈を記載しまいた。1

さらに、WithFilterクラスの内部のメソッドに注目すると、map、flatMapのメソッドでは、CanBuildFromが使われています。このCanBuildFromによって、フィルタリングした後の要素に直接関数fを適応してるため、フィルタリング後の中間状態のコレクションが作られません。
そのためfilterよりも性能の向上が期待できます。


    def map[B, That](f: A => B)(implicit bf: CanBuildFrom[Repr, B, That]): That = {
      val b = bf(repr)
      for (x <- self)
        if (p(x)) b += f(x)
      b.result
    }

    def flatMap[B, That](f: A => GenTraversableOnce[B])(implicit bf: CanBuildFrom[Repr, B, That]): That = {
      val b = bf(repr)
      for (x <- self)
        if (p(x)) b ++= f(x).seq
      b.result
    }

参考：ScalaのOptionやListのfilterとwithFilterの違い

以上、ListのwithFilterがどう実装されているのか。そしてfilterよりも性能が良いと言われるwithFilterは何となく理解できたでしょうか。

withFilterメソッドが備わっているのはコレクションだけでない

for式の糖衣構文としてwithFilterがあるのであれば、for式のジェネレーターに使えるOption型、Try型、Future型にもwithFilterメソッドが実装されています。
※Either型にはありません。

しかし、コレクションのwithFilterメソッドと、データ型のOption、Try、Futureの**withFilterメソッドの実装は完全に同じではないです。**

まずはOption型から見ていきましょう。

Option型のwithFilter

WithFilterクラスの中で、自分自身のインスタンスselfを、関数pでfilterした後にmap、flatMap、foreach処理を行なっています。

基本的にTraversableLikeと同様に内部でfilterと、map、flatMap、foreachのどれかを呼び出しています。ただし、TraversableLikeと違いFilterMonadicトレイトは登場しません。

  • scala.Option
sealed abstract class Option[+A] extends Product with Serializable {
  self =>

//省略
  /** Necessary to keep $option from being implicitly converted to
   *  [[scala.collection.Iterable]] in `for` comprehensions.
   */
  @inline final def withFilter(p: A => Boolean): WithFilter = new WithFilter(p)

  /** We need a whole WithFilter class to honor the "doesn't create a new
   *  collection" contract even though it seems unlikely to matter much in a
   *  collection with max size 1.
   */
  class WithFilter(p: A => Boolean) {
    def map[B](f: A => B): Option[B] = self filter p map f
    def flatMap[B](f: A => Option[B]): Option[B] = self filter p flatMap f
    def foreach[U](f: A => U): Unit = self filter p foreach f
    def withFilter(q: A => Boolean): WithFilter = new WithFilter(x => p(x) && q(x))
  }

ここでは、CanBuildFromなどは登場せずに、WithFilterの中で、Option型のfilterメソッドが呼び出されて、map、flatMap、foreach、そしてWithFilterが呼ばれています。

作りがTraversableLikeのWithFilterと異なるのがわかるかと思います。

コメントをみて見ると

Necessary to keep $option from being implicitly converted to [[scala.collection.Iterable]] in for comprehensions.

We need a whole WithFilter class to honor the "doesn't create a new collection" contract even though it seems unlikely to matter much in a collection with max size 1.

と、Optionがfor式の中で、暗黙的にIterableに変換されないようにするためにwithFilterメソッドが定義されており、要素が一つのコレクションであっても新しいコレクションを作らないことを尊重して、WithFilterクラスが用意されているということが書かれています。

さらにWithFilterでは、filterが使われています。filterがあるということは、filterが実装できるように空のデータ型を表すObjectが必要です。Optionの場合はNoneになります。

  @inline final def filter(p: A => Boolean): Option[A] =
    if (isEmpty || p(this.get)) this else None

データ型をfor式に内包するためには、map、flatMap、withFilterが必要で、withFilterを実装するためには、filterが必要です。
そしてfilterを実装するためには、そのデータ型の空を表すObject(ここではNone)が必要です。

TryのwithFilter

ちなみにTryのwithFilterメソッド

  • scala.util.Try
sealed abstract class Try[+T] extends Product with Serializable {
//省略
  @inline final def withFilter(p: T => Boolean): WithFilter = new WithFilter(p)

  @deprecatedInheritance("You were never supposed to be able to extend this class.", "2.12.0")
  class WithFilter(p: T => Boolean) {
    def map[U](f:     T => U): Try[U]           = Try.this filter p map f
    def flatMap[U](f: T => Try[U]): Try[U]      = Try.this filter p flatMap f
    def foreach[U](f: T => U): Unit             = Try.this filter p foreach f
    def withFilter(q: T => Boolean): WithFilter = new WithFilter(x => p(x) && q(x))
  }

Option型の作りとほとんど同じですね。

EitherのwithFilterはないです

Either型(厳密にはRightProjection型)にはwithFilterメソッドがないため、for式の条件フィルターは使えません。

scala> for {
     |   x <- Right(3) if x % 2 == 1
     |   y = x + 1
     | } yield y
<console>:14: error: value withFilter is not a member of scala.util.Right[Nothing,Int]
         x <- Right(3) if x % 2 == 1
                   ^

if式を使いたい場合は下記を参考にしてください。

参考：for式の中のEitherでifを使いたい

FutureのwithFilter

  • scala.concurrent.Future
trait Future[+T] extends Awaitable[T] {
//省略
  def filter(@deprecatedName('pred) p: T => Boolean)(implicit executor: ExecutionContext): Future[T] =
    map { r => if (p(r)) r else throw new NoSuchElementException("Future.filter predicate is not satisfied") }

  final def withFilter(p: T => Boolean)(implicit executor: ExecutionContext): Future[T] = filter(p)(executor)

Futureではfor式で使えるようにwithFilterが用意したけで、filterを呼び出しているだけです。

まとめ

このようwithFilterメソッドという機能は同じでも、コレクションのwithFilterとOption、Try、FutureのwithFilterは実装が違います。そしてfor式で使っているEitherにはwithFilterがありません。

そしてwithFilterを作るのに必要なメソッドは基本的に、filter、空、または失敗を表すオブジェクトになります。

for式の糖衣構文となるwithFilter奥が深く、withFilterを切り口に、各実装をみていくとコレクションとデータ型の勉強になったのではないでしょうか。

(おまけ)CatsのNonEmptyList

CatsにNonEmptyListというデータ型がありますが、これは名前の通り、Non EmptyなListです。要素が1つ以上なことが必ず保証されています。

そのため、空のNonEmptyListを表すことができません。なので、厳密には空のNonEmptyListを返すfilterメソッドが作れず、withFilterが作れないので、for式に条件(フィルター)を設定することができないのです。

しかし実はCatsのNonEmptyListには、Listを返すfilterメソッドが定義されております。ただ、そうなるとfilterを使うと別のデータ型になってしまうので、withFilterも作れないし、おかしくなってしまうなという所感です。

  1. この名前については完全に推測になりますが、flatMap、mapといったモナド由来の演算が定義されているため、FilterMonadicという名前になっていて、かつ切り出されていているのではないのかなと想像しています。 ↩

16
9
3

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
16
9

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?