Int -> Integer тип разговора недоразумение

Question

Вот мой код для вычисления чисел Фибоначчи:

f' :: (Int -> Int) -> Int -> Int 
f' mf 0 = 0 
f' mf 1 = 1 
f' mf n = mf(n - 2) + mf(n - 1) 

f'_list :: [Int] 
f'_list = map (f' faster_f') [0..] 

faster_f' :: Int -> Int 
faster_f' n = f'_list !! n 

Он отлично работает в то время как «п» мала. Для того, чтобы решить проблему с большими числами я хотел бы преобразовать Int типа в Integer:

f' :: (Integer -> Integer) -> Integer -> Integer 
f' mf 0 = 0 
f' mf 1 = 1 
f' mf n = mf(n - 2) + mf(n - 1) 

f'_list :: [Integer] 
f'_list = map (f' faster_f') [0..] 

faster_f' :: Integer -> Integer 
faster_f' n = f'_list !! n 

С помощью этого кода я получаю сообщение об ошибке:

Couldn't match expected type `Int' with actual type `Integer' 
In the second argument of `(!!)', namely `n' 
In the expression: f'_list !! n 
In an equation for `faster_f'': faster_f' n = f'_list !! n 

Ну, я правильно понял индекс элемента список не может быть целым. OK:

f' :: (Integer -> Integer) -> Integer -> Integer 
f' mf 0 = 0 
f' mf 1 = 1 
f' mf n = mf(n - 2) + mf(n - 1) 

f'_list :: [Integer] 
f'_list = map (f' faster_f') [0..] 

faster_f' :: **Int** -> Integer 
faster_f' n = f'_list !! n 

Но теперь я получаю ошибку:

Couldn't match expected type Integer' with actual type Int' Expected type: Integer -> Integer

Actual type: Int -> Integer 
In the first argument of `f'', namely `faster_f'' 
In the first argument of `map', namely `(f' faster_f')' 

Почему? И как я могу это исправить?

Answer 1

Why?

Поскольку f' ожидает Integer -> Integer функцию, но вы пошлете faster_f', который является Int -> Integer функцию.

And how can I fix it?

Вероятно, самый простой способ заключается в использовании genericIndex (от Data.List) вместо (!!).

Answer 2

Integer - это бесконечный тип Int, (Int гарантирован только для покрытия диапазона от -2^29 до 2^29-1, но в большинстве реализаций это полный 32 или 64-разрядный тип). Вот почему вы получаете первую ошибку. Вторая ошибка, которую вы получаете, потому что (!!) это функция, которая принимает список и Int

(!!) :: [a] -> Int -> a 

Есть много других (и, может быть, проще) способов расчета чисел Фибоначчи. Вот один пример, который возвращает список всех чисел Фибоначчи указанному. Первый вызов осуществляется fibCall

fib :: Integer -> Integer -> Integer -> [Integer] -> [Integer] 
fib 0 _ _ l = l 
fib n a b l = fib (n-1) b (a+b) (a:l) 

fibCall :: Integer -> [Integer] 
fibCall n = n 1 1 [] 

Если вы просто хотите, чтобы п ^{й номер} Фибоначчи, изменить [Integer] к Integer и (a:l) к a.

Answer 3

Самый простой способ сделать ваши аргументы Int (так как они являются индексы чисел Фибоначчи, а не числа themselve), а также использовать Integer только для выхода:

f' :: (Int -> Integer) -> Int -> Integer 
f' mf 0 = 0 
f' mf 1 = 1 
f' mf n = mf(n - 2) + mf(n - 1) 

f'_list :: [Integer] 
f'_list = map (f' faster_f') [0..] 

faster_f' :: Int -> Integer 
faster_f' n = f'_list !! n 

Конечно, теперь вы не можете адрес Фибоначчи с индексом за пределами диапазона Int, но практически у вас не хватит места и времени много, намного, гораздо раньше.

Кстати, если вам нужен список выдумок, «обычная» реализация

fibs :: [Integer] 
fibs = 0 : scanl (+) 1 fibs 

Если вам нужны только определенных значения, есть быстрый способ вычисления, аналогичный быстрое потенцирование с помощью этих формул:

f(2n) = (2*f(n-1) + f(n)) * f(n) 
f(2n-1) = f(n)² + f(n-1)²