Scalaで再帰3

[Scalaで再帰2](http://qiita.com/pizyumi/items/89436df075b976f22a0e)の続き。

次は、「「「「初期値と列の1番目の要素」を関数に適用した結果と列の2番目の要素」を関数に適用した結果と列の3番目の要素」を・・・列の最後の要素」を関数に適用した結果を返すfold関数。すなわち、左畳み込み関数（初期値あり）です。

```scala
def fold[T, S](func: Function[T, Function[S, T]])(init: T)(xs: List[S]): T = xs match {
    case Nil => init
    case x :: xs => fold(func)(func(init)(x))(xs)
}
```

簡単です。

使用例。

fold関数を使ってsum関数とlength関数とforall関数とexists関数とfind関数を作ってみました。

```scala
scala> def sum(xs: List[Int]): Int = fold((acc: Int) => (x: Int) => acc + x)(0)(xs)
sum: (xs: List[Int])Int

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

scala> def length[T](xs: List[T]): Int = fold((acc: Int) => (x: T) => acc + 1)(0)(xs)
length: [T](xs: List[T])Int

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

scala> def forall[T](pred: Function[T, Boolean])(xs: List[T]): Boolean = fold((acc: Boolean) => (x: T) => acc && pred(x))(true)(xs)
forall: [T](pred: Function[T,Boolean])(xs: List[T])Boolean

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

scala> def exists[T](pred: Function[T, Boolean])(xs: List[T]): Boolean = fold((acc: Boolean) => (x: T) => acc || pred(x))(false)(xs)
exists: [T](pred: Function[T,Boolean])(xs: List[T])Boolean

scala> exists((x: Int) => x % 2 == 0)(4 :: 3 :: 2 :: 1 :: Nil)
res182: Boolean = true

scala> def find[T](pred: Function[T, Boolean])(xs: List[T]): Option[T] = fold((acc: Option[T]) => (x: T) => if (acc == None && pred(x)) Some(x) else acc)(None)(
xs)
find: [T](pred: Function[T,Boolean])(xs: List[T])Option[T]

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

ちなみに、Scalaには左畳み込み関数（初期値あり）が最初から用意されています。foldLeft関数です。/:関数も全く同一の動作をします。

```scala
scala> (4 :: 3 :: 2 :: 1 :: Nil).foldLeft(0)((acc, x) => acc + x)
res184: Int = 10

scala> (0 /: (4 :: 3 :: 2 :: 1 :: Nil))((acc, x) => acc + x)
res185: Int = 10

scala> (4 :: 3 :: 2 :: 1 :: Nil).foldLeft(0)((acc, x) => acc + 1)
res186: Int = 4

scala> (0 /: (4 :: 3 :: 2 :: 1 :: Nil))((acc, x) => acc + 1)
res187: Int = 4

scala> (4 :: 3 :: 2 :: 1 :: Nil).foldLeft(true)((acc, x) => acc && x % 2 == 1)
res188: Boolean = false

scala> (true /: (4 :: 3 :: 2 :: 1 :: Nil))((acc, x) => acc && x % 2 == 1)
res189: Boolean = false

scala> (4 :: 3 :: 2 :: 1 :: Nil).foldLeft(false)((acc, x) => acc || x % 2 == 0)
res190: Boolean = true

scala> (false /: (4 :: 3 :: 2 :: 1 :: Nil))((acc, x) => acc || x % 2 == 0)
res191: Boolean = true

scala> (4 :: 3 :: 2 :: 1 :: Nil).foldLeft(None: Option[Int])((acc: Option[Int], x) => if (acc == None && x % 2 == 0) Some(x) else acc)
res192: Option[Int] = Some(4)

scala> ((None: Option[Int]) /: (4 :: 3 :: 2 :: 1 :: Nil))((acc: Option[Int], x) => if (acc == None && x % 2 == 0) Some(x) else acc)
res193: Option[Int] = Some(4)
```

次は、「「「列の1番目の要素と列の2番目の要素」を関数に適用した結果と列の3番目の要素」を・・・列の最後の要素」を関数に適用した結果を返すfold関数。すなわち、左畳み込み関数（初期値なし）です。

```scala
def reduce[T](func: Function[T, Function[T, T]])(xs: List[T]): T = xs match {
    case x :: xs => fold(func)(x)(xs)
}
```

簡単です。

使用例。

fold関数を使ってmax関数とmin関数を作ってみました。

```scala
scala> def max(xs: List[Int]): Int = reduce((acc: Int) => (x: Int) => if (x > acc) x else acc)(xs)
max: (xs: List[Int])Int

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

scala> def min(xs: List[Int]): Int = reduce((acc: Int) => (x: Int) => if (x < acc) x else acc)(xs)
min: (xs: List[Int])Int

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

ちなみに、Scalaには左畳み込み関数（初期値なし）が最初から用意されています。reduceLeft関数です。

```scala
scala> (4 :: 3 :: 2 :: 1 :: Nil).reduceLeft((acc, x) => if (x > acc) x else acc)
res196: Int = 4

scala> (4 :: 3 :: 2 :: 1 :: Nil).reduceLeft((acc, x) => if (x < acc) x else acc)
res197: Int = 1
```

次は、「初期値と・・・「列の最後から3番目の要素と「列の最後から2番目の要素と「列の最後の要素と初期値」を関数に適用した結果」を関数に適用した結果」・・・」を関数に適用した結果を返すfoldBack関数。すなわち、右畳み込み関数（初期値あり）です。

```scala
def foldBack[T, S](func: Function[T, Function[S, S]])(xs: List[T])(init: S): S = xs match {
    case Nil => init
    case x :: xs => func(x)(foldBack(func)(xs)(init))
}
```

簡単です。

使用例。

foldBack関数を使ってskip関数とtake関数とskipWhile関数とtakeWhile関数とmap関数とfilter関数とpartition関数とcollect関数とchoose関数を作ってみました。

```scala
scala> def skip[T](n: Int)(xs: List[T]): List[T] = {
     | def f[T]: Function[T, Function[Function[Int, List[T]], Function[Int, List[T]]]] = (x) => (acc) => (n) => n match {
     | case 0 => x :: acc(0)
     | case n => acc(n - 1)
     | }
     | foldBack(f[T])(xs)((n) => Nil)(n)
     | }
skip: [T](n: Int)(xs: List[T])List[T]

scala> skip(2)(4 :: 3 :: 2 :: 1 :: Nil)
res198: List[Int] = List(2, 1)

scala> def take[T](n: Int)(xs: List[T]): List[T] = {
     | def f[T]: Function[T, Function[Function[Int, List[T]], Function[Int, List[T]]]] = (x) => (acc) => (n) => n match {
     | case 0 => Nil
     | case n => x :: acc(n - 1)
     | }
     | foldBack(f[T])(xs)((n) => Nil)(n)
     | }
take: [T](n: Int)(xs: List[T])List[T]

scala> take(2)(4 :: 3 :: 2 :: 1 :: Nil)
res199: List[Int] = List(4, 3)

scala> def skipWhile[T](pred: Function[T, Boolean])(xs: List[T]): List[T] = {
     | def f: Function[T, Function[Function[Boolean, List[T]], Function[Boolean, List[T]]]] = (x) => (acc) => (b) => b match {
     | case false => x :: acc(false)
     | case true => if (pred(x)) acc(true) else x :: acc(false)
     | }
     | foldBack(f)(xs)((b) => Nil)(true)
     | }
skipWhile: [T](pred: Function[T,Boolean])(xs: List[T])List[T]

scala> skipWhile((x: Int) => x < 3)(1 :: 2 :: 3 :: 4 :: 5 :: 1 :: 2 :: 3 :: Nil)
res200: List[Int] = List(3, 4, 5, 1, 2, 3)

scala> def takeWhile[T](pred: Function[T, Boolean])(xs: List[T]): List[T] = {
     | def f: Function[T, Function[Function[Boolean, List[T]], Function[Boolean, List[T]]]] = (x) => (acc) => (b) => b match {
     | case false => Nil
     | case true => if (pred(x)) x :: acc(true) else Nil
     | }
     | foldBack(f)(xs)((b) => Nil)(true)
     | }
takeWhile: [T](pred: Function[T,Boolean])(xs: List[T])List[T]

scala> takeWhile((x: Int) => x < 3)(1 :: 2 :: 3 :: 4 :: 5 :: 1 :: 2 :: 3 :: Nil)
res201: List[Int] = List(1, 2)

scala> def map[T, S](func: Function[T, S])(xs: List[T]): List[S] = foldBack((x: T) => (acc: List[S]) => func(x) :: acc)(xs)(Nil)
map: [T, S](func: Function[T,S])(xs: List[T])List[S]

scala> map((x: Int) => x * 2)(4 :: 3 :: 2 :: 1 :: Nil)
res202: List[Int] = List(8, 6, 4, 2)

scala> def filter[T](pred: Function[T, Boolean])(xs: List[T]): List[T] = foldBack((x: T) => (acc: List[T]) => if (pred(x)) x :: acc else acc)(xs)(Nil)
filter: [T](pred: Function[T,Boolean])(xs: List[T])List[T]

scala> filter((x: Int) => x % 2 == 0)(4 :: 3 :: 2 :: 1 :: Nil)
res203: List[Int] = List(4, 2)

scala> def partition[T](pred: Function[T, Boolean])(xs: List[T]): (List[T], List[T]) = foldBack((x: T) => (acc: (List[T], List[T])) => if (pred(x)) (x :: acc._1
, acc._2) else (acc._1, x :: acc._2))(xs)(Nil, Nil)
partition: [T](pred: Function[T,Boolean])(xs: List[T])(List[T], List[T])

scala> partition((x: Int) => x % 2 == 0)(4 :: 3 :: 2 :: 1 :: Nil)
res204: (List[Int], List[Int]) = (List(4, 2),List(3, 1))

scala> def collect[T, S](func: Function[T, List[S]])(xs: List[T]): List[S] = foldBack((x: T) => (acc: List[S]) => func(x) ++ acc)(xs)(Nil)
collect: [T, S](func: Function[T,List[S]])(xs: List[T])List[S]

scala> collect((x: Int) => x :: x * 2 :: Nil)(4 :: 3 :: 2 :: 1 :: Nil)
res205: List[Int] = List(4, 8, 3, 6, 2, 4, 1, 2)

scala> def choose[T, S](func: Function[T, Option[S]])(xs: List[T]): List[S] = foldBack((x: T) => (acc: List[S]) => func(x) match {
     | case Some(x) => x :: acc
     | case None => acc
     | })(xs)(Nil)
choose: [T, S](func: Function[T,Option[S]])(xs: List[T])List[S]

scala> choose((x: Int) => if (x % 2 == 0) Some(x * 2) else None)(4 :: 3 :: 2 :: 1 :: Nil)
res206: List[Int] = List(8, 4)
```

ちなみに、Scalaには右畳み込み関数（初期値あり）が最初から用意されています。foldRight関数です。:\関数も全く同一の動作をします。

次は、「列の最初の要素と・・・「列の最後から2番目の要素と列の最後の要素」を関数に適用した結果」・・・」を関数に適用した結果を返すreduceBack関数。すなわち、右畳み込み関数（初期値なし）です。

```scala
def reduceBack[T](func: Function[T, Function[T, T]])(xs: List[T]): T = xs match {
    case x :: xs => foldBack(func)(xs)(x)
}
```

簡単です。

そろそろ疲れてきたので使用例はなしで。

ちなみに、Scalaには右畳み込み関数（初期値なし）が最初から用意されています。reduceRight関数です。

次は、fold関数の途中結果も返すscan関数。

```scala
def scan[T, S](func: Function[T, Function[S, T]])(init: T)(xs: List[S]): List[T] = xs match {
    case Nil => init :: Nil
    case x :: xs => init :: scan(func)(func(init)(x))(xs)
}
```

簡単です。

使用例。

```scala
scala> scan((acc: Int) => (x: Int) => acc + x)(0)(4 :: 3 :: 2 :: 1 :: Nil)
res207: List[Int] = List(0, 4, 7, 9, 10)
```

ちなみに、Scalaにはfold関数の途中結果も返す関数が最初から用意されています。scanLeft関数です。

```scala
scala> (4 :: 3 :: 2 :: 1 :: Nil).scanLeft(0)((x, acc) => x + acc)
res208: List[Int] = List(0, 4, 7, 9, 10)
```

次は、foldBack関数の途中結果も返すscanBack関数。

```scala
scala> def scanBack[T, S](func: Function[T, Function[S, S]])(xs: List[T])(init: S): List[S] = xs match {
     | case Nil => init :: Nil
     | case x :: xs => { val r = scanBack(func)(xs)(init); func(x)(r.head) :: r }
     | }
scanBack: [T, S](func: Function[T,Function[S,S]])(xs: List[T])(init: S)List[S]
```

簡単です。

使用例。

```scala
scala> scanBack((acc: Int) => (x: Int) => acc + x)(4 :: 3 :: 2 :: 1 :: Nil)(0)
res209: List[Int] = List(10, 6, 3, 1, 0)
```

ちなみに、ScalaにはfoldBack関数の途中結果も返す関数が最初から用意されています。scanRight関数です。

```scala
scala> (4 :: 3 :: 2 :: 1 :: Nil).scanRight(0)((x, acc) => x + acc)
res210: List[Int] = List(10, 6, 3, 1, 0)
```