scala - 末尾再帰の問題

Question

Scalaで並列コレクションを試していて、結果が注文されたかどうかを確認したかったのです。そのために、私はREPLに小さな関数を記述して、作成していた非常に大きなリストでそのチェックを実行しました。

def isOrdered(l:List[Int]):Boolean = { l match { 
  case Nil => true
  case x::Nil => true
  case x::y::Nil => x>y
  case x::y::tail => x>y & isOrdered(tail) 
  }
}

stackOverflowで失敗します（ここでの質問にどれほど適切か！）。私はそれがテール最適化されることを期待していました。どうしたの？

score 14 · Accepted Answer

isOrderedはコードの最後の呼び出しではなく、＆演算子は最後の呼び出しです。代わりにこれを試してください：

@scala.annotation.tailrec def isOrdered(l:List[Int]):Boolean = { l match { 
  case Nil => true
  case x::Nil => true
  case x::y::Nil => x>y
  case x::y::tail => if (x>y) isOrdered(tail) else false
  }
}

score 8 · Accepted Answer

アルゴリズムが正しくありません。@Kimの改善があっても、をisOrdered(List(4,3,5,4))返しますtrue。

これを試して：

def isOrdered(l:List[Int]): Boolean = l match {
  case Nil => true
  case x :: Nil => true
  case x :: y :: t => if (x <= y) isOrdered(l.tail) else false
}

（標識が正しくなるように更新されました）

編集：私の好みのレイアウトはこれになります：

def isOrdered(list: List[Int]): Boolean = list match {
  case Nil      => true
  case x :: Nil => true
  case x :: xs  => if (x > xs.head) false
                   else isOrdered(xs)
}

パフォーマンスが問題にならない場合の簡単な方法は次のとおりです。

def isOrdered(l: List[Int]) = l == l.sorted

score 2 · Accepted Answer

'x> y＆isOrdered（tail）'を返すため、テールを最適化することはできません。それはそれをスタックに保持する必要があることを意味します。

関数が末尾再帰であると予想される場合は、@tailrecアノテーションを使用してエラーを強制します。また、それができない理由についても説明します。

score 1 · Accepted Answer

問題は、最後のケースでビット単位の演算子（＆）を使用していることだと思います。ランタイムは＆を評価する前にisOrdered呼び出しの値を知る必要があるため、関数をテール最適化することはできません。（つまり、isOrderedが呼び出された後、実行するコード（ビット単位の操作）が増えます。）

&&またはifステートメントを使用すると役立つ場合があります。

scala - 末尾再帰の問題

4 に答える 4

Related

Reference