98

今日、UNIX で「time」コマンドを発見し、それを使用して、Haskell の末尾再帰関数と通常の再帰関数の実行時間の違いを確認しようと考えました。

私は次の関数を書きました：

--tail recursive
fac :: (Integral a) => a -> a
fac x = fac' x 1 where
    fac' 1 y = y
    fac' x y = fac' (x-1) (x*y) 

--normal recursive
facSlow :: (Integral a) => a -> a
facSlow 1 = 1
facSlow x = x * facSlow (x-1)

これらは、このプロジェクトでのみ使用するためのものであることを念頭に置いて有効であるため、わざわざゼロや負の数をチェックしませんでした.

ただし、それぞれのメイン メソッドを記述し、それらをコンパイルし、「time」コマンドで実行すると、どちらも、通常の再帰関数が末尾再帰関数を縁取る同様のランタイムになりました。これは、Lisp の末尾再帰最適化に関して私が聞いたこととは反対です。これの理由は何ですか？

4

4 に答える 4

184

Haskellは遅延評価を使用して再帰を実装するため、必要なときに値を提供するという約束として何でも扱います（これはサンクと呼ばれます）。サンクは、続行するために必要なだけ減少し、それ以上は減少しません。これは、数式を数学的に単純化する方法に似ているため、そのように考えると役立ちます。評価順序がコードで指定されていないという事実により、コンパイラーは、以前の末尾呼び出しの除去よりもさらに巧妙な最適化を行うことができます。最適化が必要な場合は、コンパイルしてください。-O2

facSlow 5ケーススタディとしてどのように評価するか見てみましょう。

facSlow 5
5 * facSlow 4            -- Note that the `5-1` only got evaluated to 4
5 * (4 * facSlow 3)       -- because it has to be checked against 1 to see
5 * (4 * (3 * facSlow 2))  -- which definition of `facSlow` to apply.
5 * (4 * (3 * (2 * facSlow 1)))
5 * (4 * (3 * (2 * 1)))
5 * (4 * (3 * 2))
5 * (4 * 6)
5 * 24
120

心配しているように、計算が行われる前に数値が蓄積されますが、心配しているのとは異なりfacSlow、終了を待つ関数呼び出しのスタックはありません-各削減が適用されて消え、スタックフレームが残りますwake（これは、(*)が厳密であり、2番目の引数の評価をトリガーするためです）。

Haskellの再帰関数は、あまり再帰的に評価されません。ぶら下がっている呼び出しの唯一のスタックは、乗算自体です。(*)厳密なデータコンストラクターと見なされる場合 、これはガードされた再帰として知られています（ただし、通常は非厳密なデータコンストラクターと呼ばれ、その後のアクセスによって強制された場合にデータコンストラクターが残ります）。

次に、末尾再帰を見てみましょうfac 5。

fac 5
fac' 5 1
fac' 4 {5*1}       -- Note that the `5-1` only got evaluated to 4
fac' 3 {4*{5*1}}    -- because it has to be checked against 1 to see
fac' 2 {3*{4*{5*1}}} -- which definition of `fac'` to apply.
fac' 1 {2*{3*{4*{5*1}}}}
{2*{3*{4*{5*1}}}}        -- the thunk "{...}" 
(2*{3*{4*{5*1}}})        -- is retraced 
(2*(3*{4*{5*1}}))        -- to create
(2*(3*(4*{5*1})))        -- the computation
(2*(3*(4*(5*1))))        -- on the stack
(2*(3*(4*5)))
(2*(3*20))
(2*60)
120

したがって、末尾再帰だけでは時間やスペースを節約できなかったことがわかります。全体としてより多くのステップを実行するだけでなくfacSlow 5、ネストされたサンク（ここではとして表示）を構築します-追加のスペース{...}が必要です-将来の計算、実行されるネストされた乗算を記述します。

次に、このサンクは、スタック上で計算を再作成して、最下部までトラバースすることによって解明されます。どちらのバージョンでも、非常に長い計算でスタックオーバーフローが発生する危険性もあります。

これを手作業で最適化したい場合は、厳密にするだけです。厳密なアプリケーション演算子$!を使用して定義できます

facSlim :: (Integral a) => a -> a
facSlim x = facS' x 1 where
    facS' 1 y = y
    facS' x y = facS' (x-1) $! (x*y)

これfacS'により、2番目の引数が厳密になります。（最初の引数は、どの定義facS'を適用するかを決定するために評価する必要があるため、すでに厳密です。）

厳密さが非常に役立つ場合もあれば、怠惰の方が効率的であるため、大きな間違いである場合もあります。ここにそれは良い考えです：

facSlim 5
facS' 5 1
facS' 4 5 
facS' 3 20
facS' 2 60
facS' 1 120
120

それがあなたが達成したかったことだと思います。

概要

  • コードを最適化する場合、ステップ1は次のコマンドでコンパイルすることです。-O2
  • 末尾再帰は、サンクの蓄積がない場合にのみ有効であり、必要に応じて、厳密さを追加すると、通常、それを防ぐのに役立ちます。これは、後で必要になる結果を一度に作成するときに発生します。
  • 末尾再帰は不適切な計画であり、ガード再帰の方が適している場合があります。つまり、構築している結果が少しずつ必要になる場合です。たとえば、についてのこの質問を参照して、それらを相互にテストしてください。foldrfoldl

次の2つを試してください。

length $ foldl1 (++) $ replicate 1000 
    "The size of intermediate expressions is more important than tail recursion."
length $ foldr1 (++) $ replicate 1000 
    "The number of reductions performed is more important than tail recursion!!!"

foldl1は末尾再帰ですが、foldr1ガードされた再帰を実行するため、最初のアイテムはすぐに提示され、さらに処理/アクセスできます。（最初の括弧は一度に左に「括弧で囲まれ」(...((s+s)+s)+...)+s、入力リストを完全に最後まで強制し、完全な結果が必要になるよりもはるかに早く将来の計算の大きなサンクを構築します。2番目の括弧は徐々に右に括弧s+(s+(...+(s+s)...))で囲み、入力を消費します。少しずつリストするので、すべてが最適化されて一定の空間で動作することができます）。

使用しているハードウェアによっては、ゼロの数を調整する必要がある場合があります。

于 2012-10-24T15:37:59.787 に答える
17

fac関数は保護された再帰の良い候補ではないことに注意してください。末尾再帰はここに行く方法です。fac'アキュムレータ引数が大きなサンクを構築し続け、評価されると巨大なスタックが必要になるため、怠惰のために関数で TCO の効果が得られません。これを防ぎ、TCO の望ましい効果を得るには、これらのアキュムレータ引数を厳密にする必要があります。

{-# LANGUAGE BangPatterns #-}

fac :: (Integral a) => a -> a
fac x = fac' x 1 where
  fac' 1  y = y
  fac' x !y = fac' (x-1) (x*y)

-O2を使用して(または単に)コンパイルする場合、 GHC はおそらく厳密性分析フェーズ-Oで独自にこれを行います。

于 2012-10-24T12:02:17.157 に答える
9

Haskellの末尾再帰に関するwikiの記事をチェックする必要があります。特に、式の評価のために、必要な種類の再帰はガードされた再帰です。（Haskellの抽象マシンで）内部で何が起こっているのかを詳細に理解すると、厳密な言語での末尾再帰の場合と同じようなことがわかります。これに加えて、遅延関数の構文が統一されています（末尾再帰は厳密な評価に結び付けられますが、保護された再帰はより自然に機能します）。

（そしてHaskellを学ぶ上で、それらのwikiページの残りも素晴らしいです！）

于 2012-10-24T03:01:22.360 に答える
0

私の記憶が正しければ、GHC は単純な再帰関数を最適化された末尾再帰関数に自動的に最適化します。

于 2012-10-24T02:59:26.327 に答える