S-99: Ninety-Nine Scala ProblemsのP07を末尾再帰にするだけの正月だった

昨年大晦日から、少しずつS-99: Ninety-Nine Scala Problemsに取り組んでいる。取り組み方は色々あると思うが、個人的に設定したルールは以下の二つ。

Listのコンストラクタ(Nil or ::)以外は自作する
なるべく末尾再帰にこだわる(なぜ末尾再帰にこだわるか)

これで現時点(2018/01/08)ではP26まで解いていたのだが、P07・P26においては技量が足らず末尾再帰化を諦めていた。しかし私の中のリトル佐藤が、年始休暇も終わるというのにこの体たらくでは悔いが残るといっているので、せめてP07だけでも末尾再帰化することにした。

まず、問題はこいつ。

P07 (**) Flatten a nested list structure.
Example:
scala> flatten(List(List(1, 1), 2, List(3, List(5, 8))))
res0: List[Any] = List(1, 1, 2, 3, 5, 8)

注意したいのはflattenのシグニチャが def flatten(list: List[Any]): List[Any] となるところだろうか。例えばこいつが def flatten[A](list: List[List[A]]): List[A] であれば問題は簡単で、以下のように書けば良いはずだ。

def flatten[A](list: List[List[A]]): List[A] = {
  @annotation.tailrec
  def go(acc: List[A], list: List[List[A]]): List[A] = list match {
    case Nil       => acc
    case e :: rest => go(addAll(acc, e), rest)
  }

  go(Nil, list)
}

しかし、実際のシグニチャが def flatten(list: List[Any]): List[Any] であることにより、末尾再帰を諦め、以下のコードとなってしまっていた。このコードでは、縦(Listのネスト)方向にも横(Listの要素)方向にも再帰をしなければならないため、再帰(goの部分)が二回出現している。

def flatten(list: List[Any]): List[Any] = {
  // TODO 末尾再帰にできぬ...できぬのだ!!
  def go(acc: List[Any], maybeList: Any): List[Any] = maybeList match {
    // Listの場合
    case e :: rest => go(go(acc, e), rest)
    case Nil       => acc
    // それ以外
    case e         => e :: acc
  }

  P05.reverse(go(Nil, list)) // P05では末尾再帰のreverseを定義している
}

しばし、こういう場合は末尾再帰にできないものと考えていた。しかし、正月休みで休養・アルコール・気合が充分な状態で再度検討してみると、goが縦・横方向への再帰のため二回出現しているから末尾再帰ができないのだから縦横で別々の関数を使うようにすれば末尾再帰化できるのではないか、と考えた。

このアイデアを用いて書いたコードがこれ。

@annotation.tailrec
def flatten(list: List[Any]): List[Any] = {
  // もちろん、addとかaddAllは自前で末尾再帰化したコードを用意している
  @annotation.tailrec
  def go(acc: List[Any], list: List[Any]): List[Any] = list match {
    case (l: List[Any]) :: rest => go(addAll(acc, l), rest)
    case e :: rest              => go(add(acc, e), rest)
    case Nil                    => acc
  }

  // 型注釈を付けないとコンパイル通らない理由はいずれ調査されるだろう...
  if (forall(list, (e => !e.isInstanceOf[List[Any]]): Any => Boolean)) {
    list
  } else {
    flatten(go(Nil, list))
  }
}

予想通り、再帰の方向で別々の関数に分ければ末尾再帰化できた。

この解法が汎用的に使えるかどうかを考えるにはちょっと酔っ払いすぎていてよくわからないけども、とにもかくにも前に進むことができた。

少年易酔學難成

IT/技術的な話題について書きます

S-99: Ninety-Nine Scala ProblemsのP07を末尾再帰にするだけの正月だった