1

次のようなhaskell式を考えてみましょう:(重要な例、明白な方法が何であるかを教えてはいけません！;）

toBits :: Integral a => a -> [Bool]
toBits 0 = []
toBits n = x : toBits m where
 (m,y) = n `divMod` 2
  x    = y /= 0

この関数は末尾再帰ではないため、次のように書くこともできます。

toBits :: Integral a => a -> [Bool]
toBits = toBits' [] where
  toBits' l 0 = l
  toBits' l n = toBits (x : l) m where
    (m,y) = n `divMod` 2
     x    = y /= 0

（この表現には何も問題がないことを願っています）

私が聞きたいのは、これらの解決策のどれが優れているかということです。最初のソリューションの利点は、部分的に非常に簡単に評価できることです（Haskellは最初のソリューションで停止する:必要がないため）が、2番目のソリューションは（明らかに）末尾再帰ですが、私の意見では完全に評価する必要がありますあなたが何かを出すことができるまで。

これの背景は私のBrainfuckパーサー（私の最適化の質問を参照）です。これは非常に醜い（さまざまなreverse命令... ooh）実装されていますが、最初の方法で簡単に実装できます-これを「セミテール再帰」の方法と呼びましょう。

4

3 に答える 3

2

Haskellでは、通常、最初の選択肢が好まれます（私は「常に」と言いますが、その単語を使用するときは常に間違っています）。アキュムレータパターンは、出力を増分的に消費できない場合（たとえば、カウンタの増分）に適しています。

于 2010-09-09T15:33:40.953 に答える
2

私はあなたがそれをすべて正しく持っていると思います。最初の形式は、計算が完了する前に有用な出力を取得できるため、一般的に優れています。つまり、「toBits」が別の計算で使用される場合、コンパイラはそれらを組み合わせる可能性があり、「toBits」の出力であるリストはまったく存在しないか、一度に1つのconsセルのみが存在する可能性があります。最初のバージョンも読みやすくなっているのは嬉しいです！

于 2010-09-09T13:52:27.493 に答える
1

2番目のバージョンの名前を変更し、いくつかのタイプミスを修正して、機能をテストできるようにします。

toBits :: Integral a => a -> [Bool]
toBits 0 = []
toBits n = x : toBits m where
 (m,y) = n `divMod` 2
 x     = y /= 0

toBits2 :: Integral a => a -> [Bool]
toBits2 = toBits' [] where
  toBits' l 0 = l
  toBits' l n = toBits' (x : l) m where
    (m,y) = n `divMod` 2
    x     = y /= 0

これらの関数は実際には同じものを計算しません。最初のものは最下位ビットで始まるリストを生成し、2番目のものは最上位ビットで始まります。言い換えるtoBits2 = reverse . toBitsと、実際にreverseは、で使用するのとまったく同じ種類のアキュムレータを使用して実装できますtoBits2。

最下位ビットから始まるリストが必要な場合は、toBitsHaskellスタイルが適しています。再帰呼び出しはレイジーな（:)コンストラクター内に含まれているため、スタックオーバーフローは発生しません。（また、リストが空かどうかを判断するためtoBitsに最初のケースで引数を評価する必要があるため、結果リストの遅い要素の値を早期に強制することによって、引数にサンクの蓄積を引き起こすことはできません。）toBits 0 = []

最上位ビットから始まるリストが必要な場合は、toBits2直接書き込むか、定義toBitsして使用することreverse . toBitsができます。reverse私の意見では理解しやすく、の再実装によってスタックオーバーフローが発生するかどうかを心配する必要がないため、おそらく後者の方が望ましいでしょう。

于 2010-09-11T17:05:43.203 に答える