Scalaで再帰2

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

次は、列のn+1番目以降の全ての要素から成る列（順序はそのまま）を返すskip関数。

```scala
def skip[T](n: Int)(xs: List[T]): List[T] = xs match {
    case Nil => Nil
    case xs if n <= 0 => xs
    case x :: xs => skip(n - 1)(xs)
}
```

簡単です。

使用例。

```scala
scala> skip(3)(Nil)
res77: List[Nothing] = List()

scala> skip(3)(1 :: Nil)
res78: List[Int] = List()

scala> skip(3)(2 :: 1 :: Nil)
res79: List[Int] = List()

scala> skip(3)(3 :: 2 :: 1 :: Nil)
res80: List[Int] = List()

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

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

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

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

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

ちなみに、Scalaには列のn+1番目以降の全ての要素から成る列（順序はそのまま）を返すdrop関数が最初から用意されています。

```scala
scala> Nil.drop(3)
res86: List[Nothing] = List()

scala> (1 :: Nil).drop(3)
res87: List[Int] = List()

scala> (2 :: 1 :: Nil).drop(3)
res88: List[Int] = List()

scala> (3 :: 2 :: 1 :: Nil).drop(3)
res89: List[Int] = List()

scala> (4 :: 3 :: 2 :: 1 :: Nil).drop(3)
res90: List[Int] = List(1)

scala> (4 :: 3 :: 2 :: 1 :: Nil).drop(2)
res91: List[Int] = List(2, 1)

scala> (4 :: 3 :: 2 :: 1 :: Nil).drop(1)
res92: List[Int] = List(3, 2, 1)

scala> (4 :: 3 :: 2 :: 1 :: Nil).drop(0)
res93: List[Int] = List(4, 3, 2, 1)

scala> (4 :: 3 :: 2 :: 1 :: Nil).drop(-1)
res94: List[Int] = List(4, 3, 2, 1)
```

次は、列のn番目以前の全ての要素から成る列（順序はそのまま）を返すtake関数。

```scala
def take[T](n: Int)(xs: List[T]): List[T] = xs match {
    case Nil => Nil
    case xs if n <= 0 => Nil
    case x :: xs => x :: take(n - 1)(xs)
}
```

簡単です。

使用例。

```scala
scala> take(3)(Nil)
res95: List[Nothing] = List()

scala> take(3)(1 :: Nil)
res96: List[Int] = List(1)

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

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

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

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

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

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

scala> take(-1)(4 :: 3 :: 2 :: 1 :: Nil)
res103: List[Int] = List()
```

ちなみに、Scalaには列のn番目以前の全ての要素から成る列（順序はそのまま）を返す関数が最初から用意されています。名称も同一でtake関数です。

```scala
scala> Nil.take(3)
res104: List[Nothing] = List()

scala> (1 :: Nil).take(3)
res105: List[Int] = List(1)

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

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

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

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

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

scala> (4 :: 3 :: 2 :: 1 :: Nil).take(0)
res111: List[Int] = List()

scala> (4 :: 3 :: 2 :: 1 :: Nil).take(-1)
res112: List[Int] = List()
```

次は、述語を充足しない列の最初の要素以降の全ての要素から成る列（順序はそのまま）を返すskipWhile関数。

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

簡単です。

使用例。

```scala
scala> val isGreaterThan3 = skipWhile((x: Int) => x > 3)(_)
isGreaterThan3: List[Int] => List[Int] = <function1>

scala> isGreaterThan3(Nil)
res113: List[Int] = List()

scala> isGreaterThan3(1 :: Nil)
res114: List[Int] = List(1)

scala> isGreaterThan3(2 :: 1 :: Nil)
res115: List[Int] = List(2, 1)

scala> isGreaterThan3(3 :: 2 :: 1 :: Nil)
res116: List[Int] = List(3, 2, 1)

scala> isGreaterThan3(4 :: 3 :: 2 :: 1 :: Nil)
res117: List[Int] = List(3, 2, 1)
```

ちなみに、Scalaには述語を充足しない列の最初の要素以降の全ての要素から成る列（順序はそのまま）を返すdropWhile関数が最初から用意されています。

```scala
scala> (Nil: List[Int]).dropWhile(x => x > 3)
res118: List[Int] = List()

scala> (1 :: Nil).dropWhile(x => x > 3)
res119: List[Int] = List(1)

scala> (2 :: 1 :: Nil).dropWhile(x => x > 3)
res120: List[Int] = List(2, 1)

scala> (3 :: 2 :: 1 :: Nil).dropWhile(x => x > 3)
res121: List[Int] = List(3, 2, 1)

scala> (4 :: 3 :: 2 :: 1 :: Nil).dropWhile(x => x > 3)
res122: List[Int] = List(3, 2, 1)
```

次は、述語を充足しない列の最初の要素より前の全ての要素から成る列（順序はそのまま）を返すtakeWhile関数。

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

簡単です。

使用例。

```scala
scala> val isLessThan3 = takeWhile((x: Int) => x < 3)(_)
isLessThan3: List[Int] => List[Int] = <function1>

scala> isLessThan3(Nil)
res123: List[Int] = List()

scala> isLessThan3(1 :: Nil)
res124: List[Int] = List(1)

scala> isLessThan3(2 :: 1 :: Nil)
res125: List[Int] = List(2, 1)

scala> isLessThan3(3 :: 2 :: 1 :: Nil)
res126: List[Int] = List()

scala> isLessThan3(4 :: 2 :: 1 :: Nil)
res127: List[Int] = List()
```

ちなみに、Scalaには述語を充足しない列の最初の要素より前の全ての要素から成る列（順序はそのまま）を返す関数が最初から用意されています。名称も同一でtakeWhile関数です。

```scala
scala> (Nil: List[Int]).takeWhile(x => x < 3)
res128: List[Int] = List()

scala> (1 :: Nil).takeWhile(x => x < 3)
res129: List[Int] = List(1)

scala> (2 :: 1 :: Nil).takeWhile(x => x < 3)
res130: List[Int] = List(2, 1)

scala> (3 :: 2 :: 1 :: Nil).takeWhile(x => x < 3)
res131: List[Int] = List()

scala> (4 :: 3 :: 2 :: 1 :: Nil).takeWhile(x => x < 3)
res132: List[Int] = List()
```

次は、列の全ての要素を写像した要素から成る列（順序はそのまま）を返すmap関数。

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

簡単です。

使用例。

```scala
scala> val x2 = map((x: Int) => x * 2)(_)
x2: List[Int] => List[Int] = <function1>

scala> x2(Nil)
res133: List[Int] = List()

scala> x2(1 :: Nil)
res134: List[Int] = List(2)

scala> x2(2 :: 1 :: Nil)
res135: List[Int] = List(4, 2)

scala> x2(3 :: 2 :: 1 :: Nil)
res136: List[Int] = List(6, 4, 2)

scala> x2(4 :: 3 :: 2 :: 1 :: Nil)
res137: List[Int] = List(8, 6, 4, 2)
```

ちなみに、Scalaには列の全ての要素を写像した要素から成る列（順序はそのまま）を返す関数が最初から用意されています。名称も同一でmap関数です。

```scala
scala> (Nil: List[Int]).map(x => x * 2)
res138: List[Int] = List()

scala> (1 :: Nil).map(x => x * 2)
res139: List[Int] = List(2)

scala> (2 :: 1 :: Nil).map(x => x * 2)
res140: List[Int] = List(4, 2)

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

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

次は、列の中で述語を充足する全ての要素から成る列（順序はそのまま）を返すfilter関数。

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

簡単です。

使用例。

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

scala> isEven(Nil)
res143: List[Int] = List()

scala> isEven(1 :: Nil)
res144: List[Int] = List()

scala> isEven(2 :: 1 :: Nil)
res145: List[Int] = List(2)

scala> isEven(3 :: 2 :: 1 :: Nil)
res146: List[Int] = List(2)

scala> isEven(4 :: 3 :: 2 :: 1 :: Nil)
res147: List[Int] = List(4, 2)
```

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

```scala
scala> (Nil: List[Int]).filter(x => x % 2 == 0)
res148: List[Int] = List()

scala> (1 :: Nil).filter(x => x % 2 == 0)
res149: List[Int] = List()

scala> (2 :: 1 :: Nil).filter(x => x % 2 == 0)
res150: List[Int] = List(2)

scala> (3 :: 2 :: 1 :: Nil).filter(x => x % 2 == 0)
res151: List[Int] = List(2)

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

次は、列の中で述語を充足する全ての要素から成る列（順序はそのまま）と充足しない全ての要素から成る列（順序はそのまま）との組を返すpartition関数。

```scala
def partition[T](pred: Function[T, Boolean])(xs: List[T]): (List[T], List[T]) = xs match {
    case Nil => (Nil, Nil)
    case x :: xs => {
        val (ts, fs) = partition(pred)(xs)
        if (pred(x)) (x :: ts, fs) else (ts, x :: fs)
    }
}
```

簡単です。

使用例。

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

scala> isEven(Nil)
res153: (List[Int], List[Int]) = (List(),List())

scala> isEven(1 :: Nil)
res154: (List[Int], List[Int]) = (List(),List(1))

scala> isEven(2 :: 1 :: Nil)
res155: (List[Int], List[Int]) = (List(2),List(1))

scala> isEven(3 :: 2 :: 1 :: Nil)
res156: (List[Int], List[Int]) = (List(2),List(3, 1))

scala> isEven(4 :: 3 :: 2 :: 1 :: Nil)
res157: (List[Int], List[Int]) = (List(4, 2),List(3, 1))
```

ちなみに、Scalaには列の中で述語を充足する全ての要素から成る列（順序はそのまま）と充足しない全ての要素から成る列（順序はそのまま）との組を返す関数が最初から用意されています。名称も同一でpartition関数です。

```scala
scala> (Nil: List[Int]).partition(x => x % 2 == 0)
res158: (List[Int], List[Int]) = (List(),List())

scala> (1 :: Nil).partition(x => x % 2 == 0)
res159: (List[Int], List[Int]) = (List(),List(1))

scala> (2 :: 1 :: Nil).partition(x => x % 2 == 0)
res160: (List[Int], List[Int]) = (List(2),List(1))

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

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

次は、列の全ての要素を列に写像し、結果として生じる全ての列を1つの列（順序はそのまま）に平坦化するcollect関数。

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

簡単です。

使用例。

```scala
scala> val x10 = collect((x: Int) => (0 to 9).toList.map(y => x * 10 + y))(_)
x10: List[Int] => List[Int] = <function1>

scala> x10(Nil)
res163: List[Int] = List()

scala> x10(1 :: Nil)
res164: List[Int] = List(10, 11, 12, 13, 14, 15, 16, 17, 18, 19)

scala> x10(2 :: 1 :: Nil)
res165: List[Int] = List(20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19)

scala> x10(3 :: 2 :: 1 :: Nil)
res166: List[Int] = List(30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19)

scala> x10(4 :: 3 :: 2 :: 1 :: Nil)
res167: List[Int] = List(40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19)
```

ちなみに、Scalaには列の全ての要素を列に写像し、結果として生じる全ての列を1つの列（順序はそのまま）に平坦化するflatMap関数が最初から用意されています。

```scala
scala> (Nil: List[Int]).flatMap(x => (0 to 9).toList.map(y => x * 10 + y))
res168: List[Int] = List()

scala> (1 :: Nil).flatMap(x => (0 to 9).toList.map(y => x * 10 + y))
res169: List[Int] = List(10, 11, 12, 13, 14, 15, 16, 17, 18, 19)

scala> (2 :: 1 :: Nil).flatMap(x => (0 to 9).toList.map(y => x * 10 + y))
res170: List[Int] = List(20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19)

scala> (3 :: 2 :: 1 :: Nil).flatMap(x => (0 to 9).toList.map(y => x * 10 + y))
res171: List[Int] = List(30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19)

scala> (4 :: 3 :: 2 :: 1 :: Nil).flatMap(x => (0 to 9).toList.map(y => x * 10 + y))
res172: List[Int] = List(40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19)
```

次は、列の全ての要素をOptionに写像し、全てのSomeの値から成る列（順序はそのまま）を返すchoose関数。

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

簡単です。

使用例。

```scala
scala> val isEven2x = choose((x: Int) => if (x % 2 == 0) Some(x * 2) else None)(_)
isEven2x: List[Int] => List[Int] = <function1>

scala> isEven2x(Nil)
res173: List[Int] = List()

scala> isEven2x(1 :: Nil)
res174: List[Int] = List()

scala> isEven2x(2 :: 1 :: Nil)
res175: List[Int] = List(4)

scala> isEven2x(3 :: 2 :: 1 :: Nil)
res176: List[Int] = List(4)

scala> isEven2x(4 :: 3 :: 2 :: 1 :: Nil)
res177 List[Int] = List(8, 4)
```