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

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

# `withFilter`は`for`式の糖衣構文

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

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

  val ひまわり = Person("ひまわり",false)
  val しんのすけ = Person("しんのすけ",true)
  val みさえ = Person("みさえ",false,ひまわり,しんのすけ)
  val persons  =  List(ひまわり,しんのすけ,みさえ)
```
for式を使って、母と子全てのペアをだしています。

```scala
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`トレイトになります。

<img width="311" alt="スクリーンショット 2018-12-17 5.38.31.png" src="https://qiita-image-store.s3.amazonaws.com/0/159733/da2d2d11-69df-ff04-90a3-d8d3498f1522.png">

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

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

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

* `scala.collection.TraversableLike`

```scala
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`メソッドを呼び出すこともできます。

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

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

##### 2. `WithFilter`クラスで`FilterMonadic`を継承している点

```scala
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 `

```scala
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]

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


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

```scala

    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の違い](http://takezoux2.blogspot.com/2011/06/scalaoptionlistfilterwithfilter.html)

以上、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`

```scala
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`になります。

```scala
  @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`

```scala
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
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を使いたい](http://tototoshi.hatenablog.com/entry/2017/01/05/213802)

## `Future`の`withFilter`

* `scala.concurrent.Future`

```scala
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](https://typelevel.org/cats/datatypes/nel.html)というデータ型がありますが、これは名前の通り、Non EmptyなListです。要素が1つ以上なことが必ず保証されています。

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

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