28

モナドでのHaskellWikiの再帰には、末尾再帰であると主張されている例があります。

f 0 acc = return (reverse acc)
f n acc = do
    v  <- getLine
    f (n-1) (v : acc)

命令型の表記法は、末尾再帰であると私たちに信じさせますが、それは（少なくとも私には）それほど明白ではありません。砂糖doを取り除くと

f 0 acc = return (reverse acc)
f n acc = getLine >>= \v -> f (n-1) (v : acc)

2行目を書き直すと

f n acc = (>>=) getLine (\v -> f (n-1) (v : acc))

したがって、これは末尾再帰の位置ではなく、fの2番目の引数の内側で発生することがわかります。答えを得るには、>>=を調べる必要がIOあります。>>=明らかに、ブロックの最後の行として再帰呼び出しを使用することはdo、関数が末尾再帰であるための十分な条件ではありません。

このモナドのすべての再帰関数が次のように定義されている場合、モナドは末尾再帰であるとしましょう。

f = do
    ...
    f ...

または同等に

f ...  =  (...) >>= \x -> f ...

末尾再帰です。私の質問は：

  1. 末尾再帰のモナドは何ですか？
  2. 末尾再帰モナドをすぐに区別するために使用できる一般的なルールはありますか？

更新：具体的な反例を作成しましょう：[]上記の定義によれば、モナドは末尾再帰ではありません。もしそうなら、

f 0 acc = acc
f n acc = do
    r <- acc
    f (n - 1) (map (r +) acc)

末尾再帰である必要があります。ただし、2行目の脱糖は

f n acc = acc >>= \r -> f (n - 1) (map (r +) acc)
        = (flip concatMap) acc (\r -> f (n - 1) (map (r +) acc))

明らかに、これは末尾再帰ではなく、IMHOを作成することはできません。その理由は、再帰呼び出しが計算の終わりではないためです。これは数回実行され、結果が組み合わされて最終結果が作成されます。

4

2 に答える 2

24

それ自体を参照するモナディック計算は、末尾再帰にはなりません。ただし、Haskellには怠惰とコアカーションがあり、それが重要です。この簡単な例を使用してみましょう。

forever :: (Monad m) => m a -> m b
forever c' = let c = c' >> c in c

(>>)このような計算は、2番目の引数でが厳密でない場合にのみ、一定の空間で実行されます。これは本当にリストと非常によく似ていますrepeat：

repeat :: a -> [a]
repeat x = let xs = x : xs in xs

コンストラクターは2番目の引数で非厳密であるため、(:)これは機能し、有限のウィークヘッド正規形（WHNF）があるため、リストをトラバースできます。コンシューマー（たとえばリストフォールド）がWHNFのみを要求する限り、これは一定のスペースで機能し、実行されます。

の場合のコンシューマーはforever、モナディック計算を解釈するものです。モナドが[]、(>>)の場合、最初の引数が空のリストである場合、2番目の引数は非厳密です。したがって、forever []結果は[]にforever [1]なりますが、発散します。モナドの場合IO、インタプリタはまさにランタイムシステムそのものであり、そこ(>>)では2番目の引数で常に非厳密であると考えることができます。

于 2012-11-14T17:46:10.583 に答える
5

本当に重要なのは、一定のスタックスペースです。最初の例は、怠惰のおかげで末尾再帰のモジュロ短所です。

が実行されて蒸発し、への(getLine >>=)呼び出しが再び残りfます。重要なのは、これは一定のステップ数で発生することです。サンクの蓄積はありません。

2番目の例、

f 0 acc = acc
f n acc = concat [ f (n - 1) $ map (r +) acc | r <- acc]

n結果リストは左からアクセスされるため、サンクのビルドアップでは線形（in）のみになります（これも怠惰であり、concat厳密ではありません）。ヘッドで消費される場合は、O（1）スペースで実行できます（f(0), f(1), ..., f(n-1)左端の線形スペースサンクはカウントされません）。

はるかに悪いでしょう

f n acc = concat [ f (n-1) $ map (r +) $ f (n-1) acc | r <- acc]

またはdo表記で、

f n acc = do
  r <- acc
  f (n-1) $ map (r+) $ f (n-1) acc

情報の依存関係のために余分な強制があるからです。同様に、特定のモナドのバインドが厳密な操作である場合。

于 2012-11-14T14:11:19.033 に答える