0

フィボナッチ数のリストを返す関数を作成しています。しかし、私はエラーが発生しています

7.25-7.37: mismatch on application: expression type
    int list
does not match function's argument type
    int list list
because type
    int
does not unify with
    int list

これが私のコードです：

fun fibl []  = [0]
  | fibl [0] = [0]
  | fibl [1] = [1]
  | fibl  n  = fibl[n]
  | fibl [n] = 
    let
      val f = fn () => fibl [n - 1] + fibl [n - 2]
    in
      (f ())::[n]
    end;

インタープリターは、ラムダでエラーが発生すると言いますが、私が理解した方法です。書き込みfibl [n]とは、リストをチェックすることを意味し、後で使用するときにn、それに含まれる値を使用しているため、int リストのリストではなく、int のリストだけで呼び出す必要があるため、fibl実際には何がわからないここでうまくいかなかった、誰か手がかりを得た？

4

2 に答える 2

3

コードには複数の問題があります。

この行から始まる

| fibl n = fibl [n]

前の 2 行で、整数のリストを照合しています。したがって、関数はそのようなリストを入力として受け取る必要があります。ただし、上記の行では、この整数のリストを取得し、別のリスト内にパックされたn関数を再帰的に呼び出しています。ただし、このマッチを修正すると無限ループが発生することに注意してください。nfibl [n]

別の問題は、上記の一致がすべての入力をキャッチするため、最後の一致が冗長であることです。その結果、最後の一致が新しく一致します。

また、最後の試合でいくつかのエラーが発生しました。関数はその結果をシングルトン リストとして返すことに注意してください。functionで、関数の結果 (つまり、int リスト)fを追加しようとしますが、これは可能です。fiblここでは、リストから番号を「引き出す」か、まったく別のことを行う必要があります。

フィボナッチ数のリストを生成しようとしているので、現在のアプローチでは 2 つのフィボナッチ数のリストしか生成されないため、まったく別のことを行うことをお勧めします。素朴な解決策から始めることをお勧めします。n 番目のフィボナッチ数を生成する関数を持ち、この関数を何度も適用してリストを生成します。

いくつかの例

リクエストに応じて、素朴にそれを行う方法の例をいくつか示します。

まず、n 番目のフィボナッチ数を生成する関数を定義します。

fun fib 0 = 0                                                                                                                                          
  | fib 1 = 1
  | fib n = fib (n-1) + fib (n-2)

この関数は、数値のリストを介して簡単にマッピングでき、特定のフィボナッチ数のリストを生成します

- val fibLst = map fib [0,1,2,3,4,5,6,7,8];
val fibLst = [0,1,1,2,3,5,8,13,21] : int list

ただし、リスト 0...n を生成し、そのリストに fib 関数を適用する関数を作成することもできます。

fun genFib n = List.tabulate (n, fib);

または List.tabulate 関数なし

fun genFib1 n =
    let
      fun loop 0 acc = fib 0 :: acc
        | loop m acc = loop (m-1) (fib m :: acc)
    in
      loop (n-1) []
    end

明らかに、fib 関数はより適切に実装でき、リスト生成関数は次のフィボナッチ数がどのように作成されるかを利用できます。最初の 40 個のフィボナッチ数を含むリストを生成する際、以下の関数の方がはるかに高速であることがわかります。

fun genFib2 n =
    let
      fun loop 0 _ _ acc = rev acc
        | loop m f_1 f_2 acc = loop (m-1) f_2 (f_1 + f_2) (f_2 :: acc)
    in
      loop (n-1) 0 1 [0]
    end

上記には、SML の整数のサイズに関するいくつかの問題があります (44 番目のフィボナッチ数は生成できますが、45 番目は生成できません)。上記のアイデアと一緒に、任意精度の整数 IntInf を使用するように fib 関数を拡張できます。

fun fibInf n : IntInf.int  =
    let
      fun loop 0 f_1 _ = f_1
        | loop m f_1 f_2 = loop (m-1) f_2 (f_1 + f_2)
    in
      loop n 0 1
    end

今では「高速」であり、最初の 100 個以上のフィボナッチ数を生成することが可能です。

fun genFibInf n = List.tabulate (n, fibInf);

- genFibInf 1000;
val it = [0,1,1,2,3,5,8,13,21,34,55,89,...] : IntInf.int list
- List.nth(it, 700);
val it =
  8747081495575284620397841301757132734236724096769738107423043259252750#
  : IntInf.int
于 2013-09-18T11:57:13.847 に答える
1

n番目までのフィボナッチ数のリストを生成する別の関数:

fun fibs 0 = [0]
  | fibs 1 = [1, 0]
  | fibs n =
    case fibs (n - 1) of
        (n1::n2::ns) => (n1+n2::n1::n2::ns)
      | _ => raise Fail "Not possible"

((1, 1, ...) または (1, 2, ...) から始まるフィボナッチ数の定義の基本ケースを修正します)。

于 2013-09-20T15:59:22.720 に答える