Scalaで再帰1

今日はScalaで再帰関数を書いてみます。

@bleis氏の以下の記事の流れに沿ってやっていきます。

* [再帰で考える](http://bleis-tift.hatenablog.com/entry/20120119/1326944722)

まずは、列の要素の総和を返すsum関数。

```scala
def sum(xs: List[Int]): Int = xs match {
    case Nil => 0
    case x :: xs => x + sum(xs)
}
```

簡単です。

使用例。

```scala
scala> sum(Nil)
res0: Int = 0

scala> sum(1 :: Nil)
res1: Int = 1

scala> sum(2 :: 1 :: Nil)
res2: Int = 3

scala> sum(3 :: 2 :: 1 :: Nil)
res3: Int = 6

scala> sum(4 :: 3 :: 2 :: 1 :: Nil)
res4: Int = 10
```

ちなみに、Scalaには列の要素の総和を返す関数が最初から用意されています。名称も同一でsum関数です。

```scala
scala> (Nil: List[Int]).sum
res5: Int = 0

scala> (1 :: Nil).sum
res6: Int = 1

scala> (2 :: 1 :: Nil).sum
res7: Int = 3

scala> (3 :: 2 :: 1 :: Nil).sum
res8: Int = 6

scala> (4 :: 3 :: 2 :: 1 :: Nil).sum
res9: Int = 10
```

次は、列の要素の数を返すlength関数。

```scala
def length[T](xs: List[T]): Int = xs match {
    case Nil => 0
    case x :: xs => 1 + length(xs)
}
```

簡単です。

使用例。

```scala
scala> length(Nil)
res10: Int = 0

scala> length(1 :: Nil)
res11: Int = 1

scala> length(2 :: 1 :: Nil)
res12: Int = 2

scala> length(3 :: 2 :: 1 :: Nil)
res13: Int = 3

scala> length(4 :: 3 :: 2 :: 1 :: Nil)
res14: Int = 4
```

ちなみに、Scalaには列の要素の数を返す関数が最初から用意されています。名称も同一でlength関数です。size関数も全く同一の動作をします。

```scala
scala> (Nil: List[Int]).length
res15: Int = 0

scala> (Nil: List[Int]).size
res16: Int = 0

scala> (1 :: Nil).length
res17: Int = 1

scala> (1 :: Nil).size
res18: Int = 1

scala> (2 :: 1 :: Nil).length
res19: Int = 2

scala> (2 :: 1 :: Nil).size
res20: Int = 2

scala> (3 :: 2 :: 1 :: Nil).length
res21: Int = 3

scala> (3 :: 2 :: 1 :: Nil).size
res22: Int = 3

scala> (4 :: 3 :: 2 :: 1 :: Nil).length
res23: Int = 4

scala> (4 :: 3 :: 2 :: 1 :: Nil).size
res24: Int = 4
```

次は、列の最大の要素を返すmax関数。

```scala
def max(xs: List[Int]): Int = xs match {
    case List(x) => x
    case x :: xs => { val m = max(xs); if (m > x) m else x }
}
```

簡単です。

使用例。

```scala
scala> max(1 :: Nil)
res25: Int = 1

scala> max(2 :: 1 :: Nil)
res26: Int = 2

scala> max(3 :: 2 :: 1 :: Nil)
res27: Int = 3

scala> max(4 :: 3 :: 2 :: 1 :: Nil)
res28: Int = 4
```

この関数をNilに対して使用するとどうなるでしょうか？

```scala
scala> max(Nil)
scala.MatchError: List() (of class scala.collection.immutable.Nil$)
  at .max(<console>:10)
  ... 33 elided
```

MatchErrorが発生します。空の列が与えられた場合の動作を規定していないからです。空の列に対応するには返り値の型をOption[Int]にすべきでしょうか。

```scala
def max(xs: List[Int]): Option[Int] = xs match {
    case Nil => None
    case List(x) => Some(x)
    case x :: xs => { val m = max(xs); if (m.get > x) m else Some(x) }
}
```

簡単です。

```scala
scala> max(Nil)
res29: Option[Int] = None

scala> max(1 :: Nil)
res30: Option[Int] = Some(1)

scala> max(2 :: 1 :: Nil)
res31: Option[Int] = Some(2)

scala> max(3 :: 2 :: 1 :: Nil)
res32: Option[Int] = Some(3)

scala> max(4 :: 3 :: 2 :: 1 :: Nil)
res33: Option[Int] = Some(4)
```

同様に列の最小の要素を返すmin関数も実装できます。

```scala
def min(xs: List[Int]): Option[Int] = xs match {
    case Nil => None
    case List(x) => Some(x)
    case x :: xs => { val m = min(xs); if (m.get < x) m else Some(x) }
}
```

簡単です。

使用例。

```scala
scala> min(Nil)
res34: Option[Int] = None

scala> min(1 :: Nil)
res35: Option[Int] = Some(1)

scala> min(2 :: 1 :: Nil)
res36: Option[Int] = Some(1)

scala> min(3 :: 2 :: 1 :: Nil)
res37: Option[Int] = Some(1)

scala> min(4 :: 3 :: 2 :: 1 :: Nil)
res38: Option[Int] = Some(1)
```

ちなみに、Scalaには列の最大の要素を返す関数と最小の要素を返す関数が最初から用意されています。名称も同一でそれぞれmax関数とmin関数です。

```scala
scala> (Nil: List[Int]).max
java.lang.UnsupportedOperationException: empty.max
  at scala.collection.TraversableOnce$class.max(TraversableOnce.scala:227)
  at scala.collection.AbstractTraversable.max(Traversable.scala:104)
  ... 33 elided

scala> (Nil: List[Int]).min
java.lang.UnsupportedOperationException: empty.min
  at scala.collection.TraversableOnce$class.min(TraversableOnce.scala:220)
  at scala.collection.AbstractTraversable.min(Traversable.scala:104)
  ... 33 elided

scala> (1 :: Nil).max
res39: Int = 1

scala> (1 :: Nil).min
res40: Int = 1

scala> (2 :: 1 :: Nil).max
res41: Int = 2

scala> (2 :: 1 :: Nil).min
res42: Int = 1

scala> (3 :: 2 :: 1 :: Nil).max
res43: Int = 3

scala> (3 :: 2 :: 1 :: Nil).min
res44: Int = 1

scala> (4 :: 3 :: 2 :: 1 :: Nil).max
res45: Int = 4

scala> (4 :: 3 :: 2 :: 1 :: Nil).min
res46: Int = 1
```

しかし、これらの関数をNilに対して使用するとUnsupportedOperationExceptionが発生します。

次は、列の全ての要素が述語を充足するかを返すforall関数。

```scala
def forall[T](pred: Function[T, Boolean])(xs: List[T]): Boolean = xs match {
    case Nil => true
    case x :: xs => pred(x) && forall(pred)(xs)
}
```

簡単です。しかし、これだと必ず列の全ての要素をなめなめすることになるのが無駄に思えるので、ちょっと改良しましょう。

```scala
def forall[T](pred: Function[T, Boolean])(xs: List[T]): Boolean = xs match {
    case Nil => true
    case x :: xs => if (!pred(x)) false else forall(pred)(xs)
}
```

使用例。

```scala
scala> val isOdd = forall((x: Int) => x % 2 == 1)(_)
isOdd: List[Int] => Boolean = <function1>

scala> isOdd(Nil)
res47: Boolean = true

scala> isOdd(1 :: Nil)
res48: Boolean = true

scala> isOdd(2 :: 1 :: Nil)
res49: Boolean = false

scala> isOdd(3 :: 2 :: 1 :: Nil)
res50: Boolean = false

scala> isOdd(4 :: 3 :: 2 :: 1 :: Nil)
res51: Boolean = false
```

同様に列のある要素が述語を充足するかを返すexists関数も実装できます。

```scala
def exists[T](pred: Function[T, Boolean])(xs: List[T]): Boolean = xs match {
    case Nil => false
    case x :: xs => pred(x) || exists(pred)(xs)
}
```

簡単です。しかし、これだと必ず列の全ての要素をなめなめすることになるのが無駄に思えるので、ちょっと改良しましょう。

```scala
def exists[T](pred: Function[T, Boolean])(xs: List[T]): Boolean = xs match {
    case Nil => false
    case x :: xs => if (pred(x)) true else exists(pred)(xs)
}
```

使用例。

```scala
scala> val isEven = exists((x: Int) => x % 2 == 0)(_)
isEven: List[Int] => Boolean = <function1>

scala> isEven(Nil)
res52: Boolean = false

scala> isEven(1 :: Nil)
res53: Boolean = false

scala> isEven(2 :: 1 :: Nil)
res54: Boolean = true

scala> isEven(3 :: 2 :: 1 :: Nil)
res55: Boolean = true

scala> isEven(4 :: 3 :: 2 :: 1 :: Nil)
res56: Boolean = true
```

ちなみに、Scalaには列の全ての要素が述語を充足するかを返す関数とある要素が述語を充足するかを返す関数が最初から用意されています。名称も同一でそれぞれforall関数とexists関数です。

```scala
scala> (Nil: List[Int]).forall((x) => x % 2 == 1)
res57: Boolean = true

scala> (1 :: Nil).forall((x) => x % 2 == 1)
res58: Boolean = true

scala> (2 :: 1 :: Nil).forall((x) => x % 2 == 1)
res59: Boolean = false

scala> (3 :: 2 :: 1 :: Nil).forall((x) => x % 2 == 1)
res60: Boolean = false

scala> (4 :: 3 :: 2 :: 1 :: Nil).forall((x) => x % 2 == 1)
res61: Boolean = false

scala> (Nil: List[Int]).exists((x) => x % 2 == 0)
res62: Boolean = false

scala> (1 :: Nil).exists((x) => x % 2 == 0)
res63: Boolean = false

scala> (2 :: 1 :: Nil).exists((x) => x % 2 == 0)
res64: Boolean = true

scala> (3 :: 2 :: 1 :: Nil).exists((x) => x % 2 == 0)
res65: Boolean = true

scala> (4 :: 3 :: 2 :: 1 :: Nil).exists((x) => x % 2 == 0)
res66: Boolean = true
```

次は、列の中で述語を充足する最初の要素を返すfind関数。

```scala
def find[T](pred: Function[T, Boolean])(xs: List[T]): Option[T] = xs match {
    case Nil => None
    case x :: xs => if (pred(x)) Some(x) else find(pred)(xs)
}
```

簡単です。

使用例。

```scala
scala> val isOdd = find((x: Int) => x % 2 == 1)(_)
isOdd: List[Int] => Option[Int] = <function1>

scala> isOdd(Nil)
res67: Option[Int] = None

scala> isOdd(1 :: Nil)
res68: Option[Int] = Some(1)

scala> isOdd(2 :: 1 :: Nil)
res69: Option[Int] = Some(1)

scala> isOdd(3 :: 2 :: 1 :: Nil)
res70: Option[Int] = Some(3)

scala> isOdd(4 :: 3 :: 2 :: 1 :: Nil)
res71: Option[Int] = Some(3)
```

ちなみに、Scalaには列の中で述語を充足する最初の要素を返す関数が最初から用意されています。名称も同一でfind関数です。

```scala
scala> (Nil: List[Int]).find((x) => x % 2 == 1)
res72: Option[Int] = None

scala> (1 :: Nil).find((x) => x % 2 == 1)
res73: Option[Int] = Some(1)

scala> (2 :: 1 :: Nil).find((x) => x % 2 == 1)
res74: Option[Int] = Some(1)

scala> (3 :: 2 :: 1 :: Nil).find((x) => x % 2 == 1)
res75: Option[Int] = Some(3)

scala> (4 :: 3 :: 2 :: 1 :: Nil).find((x) => x % 2 == 1)
res76: Option[Int] = Some(3)
```