Expression type int list does not match function's argument type int list list in SML

Question

I'm making a function that returns a list of fibonacci numbers; however I'm getting the error

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

Here's my code:

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;

The interpreter says the error occurs in the lambda, but the way I understood it; writing fibl [n] means it checks for a list, and then when you later use n you're using the value it contains, so I shouldn't be calling fibl with a list of int lists but JUST a list of ints so I don't really know what went wrong here, anyone got a clue?

Answer 1

There are multiple issues with your code.

Starting with this line

| fibl n = fibl [n]

You are matching for a list of integers, in the two previous lines. Thus your function must take such a list as input. However in the above line, you are taking this list of integers n and calling your function recursively with n packed inside another list fibl [n]. Note however that this match will generate an infinite loop when fixed!

Another issue is that your last match is redundant, as the above match will catch all input, resulting in your last match newer being matched.

You also have some errors in the last match. Note that your function returns its result as a singleton list. In your function f, you try to add the result of your fibl function (i.e., an int list), which is possible. Here you either have to "pull out" the number from the list or do something entirely different.

Since you are trying to generate a list of fibonacci numbers, I would suggest that you do something entirely different, as your current approach only generates a list of two fibonacci numbers. I would suggest that you start off with a naive solution; having a function that will generate the n'th fibonacci number, and then generate a list by applying this function over and over.

---

Some examples

As requested, here are some examples of how one could do it naively.

First of we define a function that will generate the n'th fibonacci number.

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

This function can then easily be mapped through a list of numbers, generating a list of those specific fibonacci numbers

- 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

However we can also create a function, that will generate a list 0...n and then apply the fib function to that list.

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

or without the List.tabulate function

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

Obviously the fib function could be implemented much better, and our list generating function could just take advantage of how the next fibonacci number is created. You will notice that the below function is much faster at generating the list containing the first 40 fibonacci numbers.

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 

The above have some issues with the size of an integer in SML (you can generate the 44th fibonacci number, but not 45th). So we can extend the fib function to use the arbitrary-precision integer IntInf, together with the idea from above

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

Now it is both "fast" and possible to generate the first 100 fibonacci numbers, or more

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

Answer 2

Another function that generates a list of Fibonacci numbers up to the n-th:

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"

(Fix base case for definitions of Fibonacci numbers that start from (1, 1, ...) or (1, 2, ...).