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;

解释器说错误发生在 lambda 中，但我理解它的方式；写作fibl [n]意味着它检查一个列表，然后当你以后使用时，n你正在使用它包含的值，所以我不应该fibl用一个 int 列表来调用，而只是一个 int 列表，所以我真的不知道是什么这里出错了，有人知道吗？

4

2 回答 2

3

您的代码存在多个问题。

从这一行开始

| fibl n = fibl [n]

在前两行中，您正在匹配整数列表。因此，您的函数必须将这样的列表作为输入。但是，在上面的行中，您正在获取这个整数列表并在另一个 list 中n以递归方式调用您的函数。但是请注意，此匹配将在修复后生成无限循环！nfibl [n]

另一个问题是你的最后一个匹配是多余的，因为上面的匹配将捕获所有输入，导致你的最后一个匹配更新被匹配。

你在上一场比赛中也有一些错误。请注意，您的函数将其结果作为单例列表返回。在您的函数f中，您尝试添加fibl函数的结果（即一个 int 列表），这是可能的。在这里，您要么必须从列表中“拉出”数字，要么做一些完全不同的事情。

由于您正在尝试生成一个斐波那契数列，我建议您做一些完全不同的事情，因为您当前的方法只生成一个包含两个斐波那契数列的列表。我建议您从一个幼稚的解决方案开始；具有将生成第 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 个）。所以我们可以扩展 fib 函数以使用任意精度整数 IntInf，以及上面的想法

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 回答