末尾最適化の練習メモ
@pizyumiさんの以下の記事で実装している再帰処理を末尾最適化に書き直しながら練習した記事です。
列の要素の総和を返すsum
メソッド。
- ふつうの再帰
def sum(xs: List[Int]): Int = xs match {
case Nil => 0
case x :: xs1 => x + sum(xs1)
}
- 末尾最適化
def sum(xs: List[Int]): Int = {
def sum(xs: List[Int], z: Int): Int = xs match {
case Nil => z
case x :: xs1 => sum(xs1, z + x)
}
sum(xs, 0)
}
列の要素の数を返すlength
メソッド。
- ふつうの再帰
def length[T](xs: List[T]): Int = xs match {
case Nil => 0
case x :: xs => 1 + length(xs)
}
- 末尾最適化
def length[T](xs: List[T]): Int = {
def length[T](xs: List[T], z: Int): Int = xs match {
case Nil => z
case _ :: xs1 => length(xs1, z + 1)
}
length(xs, 0)
}
列の最大の要素を返すmax
メソッド。
- ふつうの再帰
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 }
}
- 末尾最適化
def max(xs: List[Int]): Int = {
def max(xs: List[Int], z: Int): Int = xs match {
case Nil => z
case x :: xs1 if x > z => max(xs1, x)
case x :: xs1 => max(xs1, z)
}
max(xs, xs.head)
}
列の全ての要素が述語を充足するかを返すforall
メソッド。
- 末尾最適化
def forall[T](f: T => Boolean)(xs: List[T]): Boolean = xs match {
case Nil => true
case x :: xs1 if !f(x) => false
case x :: xs1 => forall1(f)(xs1)
}
列のある要素が述語を充足するかを返すexists
メソッド
- 末尾最適化
def exists[T](f: T => Boolean)(xs: List[T]): Boolean = xs match {
case Nil => false
case x :: _ if f(x) => true
case _ :: xs1 => exists(f)(xs1)
}
列の中で述語を充足する最初の要素を返すfind
メソッド。
- 末尾最適化
def find[T](f: T => Boolean)(xs: List[T]): Option[T] = xs match {
case Nil => None
case x :: _ if f(x) => Some(x)
case _ :: xs1 => find(f)(xs1)
}