末尾最適化の練習メモ

@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)
  }