3

動作する次の末尾再帰フィボナッチジェネレーターを思いつきました：

let {
  fibo :: Integral x => [x]->x->x->x->[x]
  fibo l x y 0 = l
  fibo l x y n = fibo (l ++ [y+x] ++ [y+x+y]) (x+y) (y+x+y) (n-1)
}

私はGHCiを使用しており、これをファイルに入れて実行する方法をまだ学んでいないため、実装全体を1行にまとめて申し訳ありません(私はまだそこに到達していません)。私が知りたいのは、この呼び出し方法です:

fibo [0, 1] 0 1 5

改善することができます。最初のリストに 0 と 1 を渡してから、制限付きで 0 と 1 をもう一度渡したくありません。実装は変更できると思います。どのような変更を行うことができますか?

4

3 に答える 3

7

あなたのアルゴリズムは末尾再帰的ですが、他にも欠点があるようです。つまり、1) 末尾に追加して結果リストを作成していること、および 2) 遅延していないことです。

a ++ b1) については、2 つのリストを追加する場合、基本的に再割り当てする必要があることに注意してくださいa。あなたの場合a、フィボナッチ数の増加するリストでありb、次の2つの項です。したがって、反復ごとに、既に計算されたフィボナッチ数が再割り当てされ、さらに 2 つの要素が追加され、2 次実行時間になります。bの先頭に追加する方が効率的ですa。逆にフィボナッチ数を生成しますが、実行時間は線形になります。reverse昇順でシーケンスが必要な場合は、最後にリストを作成できます。

逆の順序でリストを作成すると、Code-Guru のパターン マッチングのアイデアを使用して、シーケンスの最後の 2 つの用語を簡単に取得できることに注意してください。

2) については、計算全体が完了するまでリストの最初の要素を取得できないことに注意してください。次のシーケンスの遅延生成と比較してください。

fibs = 0 : (go 0 1)
  where go a b = b : go b (a+b)

再帰が止まらないように見えますが、fibs必要な分だけ評価されます。たとえば、fibs !! 3電話goは数回だけです。

于 2012-07-25T19:28:36.173 に答える
4

アルゴリズム自体には触れませんが、再帰関数を構築する方法についてのアドバイスを以下に示します。

まず、コードを別のファイルにフォーマットする方法を次に示します

fibo :: Integral x => [x]->x->x->x->[x]
fibo l x y 0 = l
fibo l x y n = fibo (l ++ [y+x] ++ [y+x+y]) (x+y) (y+x+y) (n-1)

これを fibo.hs として保存すると、次のコマンドで GHCi を起動できます。

ghci fibo.hs

開始時にファイルをロードします。コマンドでGHCiを起動した後にファイルをロードすることもできます

:l fibo.hs

(fibo.hsを保存したのと同じディレクトリでGHCiを起動すると仮定します)

もう 1 つの優れた機能は、ファイルを編集するときに、次のように入力するだけですべての変更をリロードできることです。

:r

GHCiプロンプトで。

さて、余分なパラメータを取り除くために、Haskell の通常のパターンは、再帰部分を独自のヘルパー関数にリファクタリングし、メイン関数を必要なパラメータのみを取るエントリ ポイントとして持つことです。例えば、

fibo :: Integral x => x -> [x]
fibo n = fiboHelper [0,1] 0 1 n

fiboHelper :: Integral x => [x]->x->x->x->[x]
fiboHelper l x y 0 = l
fiboHelper l x y n = fiboHelper (l ++ [y+x] ++ [y+x+y]) (x+y) (y+x+y) (n-1)

fiboこれで、次のように簡単に呼び出すことができます

> fibo 3
[0,1,1,2,3,5,8,13]

letまた、このような単独では役に立たないヘルパー関数は、通常、またはを使用して内部関数としてメイン関数内に隠されますwhere。

fibo :: Integral x => x -> [x]
fibo n = fiboHelper [0,1] 0 1 n where
    fiboHelper l x y 0 = l
    fiboHelper l x y n = fiboHelper (l ++ [y+x] ++ [y+x+y]) (x+y) (y+x+y) (n-1)

このような内部関数には通常、短い名前が付けられます。これは、コンテキストがその目的を明確にするためです。そのため、名前を eg に変更できますfibo'。

goは、再帰ヘルパー関数の別の一般的な名前です。

于 2012-07-25T19:37:40.233 に答える
3

記録のために: フィボナッチ数のリストの「通常の」定義は次のとおりです。

fibo = 0 : scanl (+) 1 fibo
于 2012-07-26T13:01:30.167 に答える