[解決済み] Haskellには末尾再帰的最適化があるか？

質問

今日、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の末尾再帰的最適化に関して聞いていた話と逆です。この理由は何でしょうか？

どのように解決するのですか？

Haskellは再帰を実装するためにlazy-evaluationを使うので、何でも必要なときに値を提供する約束として扱います（これをthunkと呼びます）。サンクは処理を進めるために必要な分だけ削減され、それ以上は削減されません。これは数学で式を簡略化するのに似ているので、そのように考えると便利です。評価順序が ではなく が指定されていないため、コンパイラは通常のテールコール除去よりもさらに巧妙な最適化を行うことができます。 でコンパイルします。 -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 関数呼び出しが終了するのを待っているようなことはありません。 スタック フレーム を残して去っていきます（これは (*) は厳密であるため、その第二引数の評価をトリガーするからです）。

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' はその第二引数において厳格であることを強制します。(の定義を決定するために評価されなければならないので、最初の引数では既に厳密です）。 facS' を適用するために評価されなければならないからです)。

厳密さが非常に助けになることもあれば、怠惰の方が効率的なので大きな間違いであることもあります。ここでは良いアイデアです。

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

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

概要

• コードを最適化したい場合、ステップ1では、コンパイル時に -O2
• 末尾再帰はサンクの蓄積がない場合にのみ有効であり、厳密性を追加することは、適切な場合、適切な場所で、それを防ぐのに通常役立ちます。これは、後で必要とされる結果を一度に構築しているときに起こります。
• 末尾再帰が悪い計画で、ガード付き再帰がより適しているとき、つまり、構築している結果が部分的に少しずつ必要とされるときです。参照 この質問 について foldr と foldl のように、それぞれを比較テストしてみましょう。

この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 はガード付き再帰を行い、最初の項目がすぐに次の処理/アクセスのために提示されるようにします。 _{(最初のquot;括弧付け"は一度に左へ。 (...((s+s)+s)+...)+s で、入力リストを完全に最後まで強制し、その完全な結果が必要とされるよりもずっと早く、将来の計算の大きなサンクを構築します。 s+(s+(...+(s+s)...)) 入力リストを少しずつ消費していくので、全体は最適化されながら一定の空間で動作することができます）。}

使用しているハードウェアによって、ゼロの数を調整する必要があるかもしれません。