Тип выражения типа int не соответствует имени аргумента функции int list list в SML

Question

Я создаю функцию, которая возвращает список чисел фибоначчи; Однако я получаю ошибку

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, вы используете его значение, поэтому я не должен звонить fibl со списком списков int, но JUST список int, поэтому я не действительно знаю, что пошло не так, кто-нибудь понял?

Answer 1

С кодом возникает несколько проблем.

Начиная с этой линией

| fibl n = fibl [n] 

Вы сопрягая для списка целых чисел, в двух предыдущих строках. Таким образом, ваша функция должна иметь такой список, как вход. Однако в приведенной выше строке вы принимаете этот список целых чисел n и вызываете свою функцию рекурсивно с помощью n, упакованного внутри другого списка fibl [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); 

или без списка.табулирования функции

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 

Очевидно, что функция выдумки может быть реализована гораздо лучше, и наши производящий список функций можно просто воспользоваться, как создаются число следующего Фибоначи. Вы заметите, что функция ниже работает намного быстрее при создании списка, содержащего первые 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-е число Фибоначчи, но не сорок пятый). Таким образом, мы можем расширить функции Фибо использовать произвольной точности целое 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 

Answer 2

Другая функция, которая создает список чисел Фибоначчи вплоть до п -го:

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 базовый вариант для де (1, 1, ...) или (1, 2, ...).