CODEWITHSUNDEEP
haskell
ceth
ceth

Reputation: 45295

Int -> Integer: type conversation misunderstanding

Here is my code for the calculating fibonacci numbers:

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

It works fine while 'n' is small. To resolve the problem with big numbers I would like convert Int-type to 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

With this code I get the error:

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

Well, I have understood correctly the index of element in the list can not be Integer-type. 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

But now I get the error:

Couldn't match expected type Integer' with actual typeInt' 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')'

Why? And how can I fix it?

Upvotes: 1

Views: 307

Answers (3)

nist
nist

Reputation: 1721

Integer is the infinite type of Int, (Int is only guaranteed to cover the range from -2^29 to 2^29-1, but in most implementations it's the full 32 or 64-bit type). That's why you get the first error. The second error you get because (!!) is a function that takes an list and an Int

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

There are a lot of other (and maybe easier) ways to calculate the Fibonacci numbers. Here is one example that returns a list of all Fibonacci numbers to the specified. The first call is done by 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 []

If you just want the nth Fibonacci number, change [Integer] to Integer and (a:l) to a.

Upvotes: 2

Landei
Landei

Reputation: 54574

The easiest way is to make your arguments Int (as they are indexes of Fibonacci numbers, not the numbers themselve), and use Integer just for the output:

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

Of course now you can't address Fibonacci numbers with an index outside the Int range, but practically you'll run out of space and time much, much, much sooner.

By the way, if you need a list of fibs, the "usual" implementation is

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

If you need just certain values, there is a fast calculation method similar to fast exponentiation using these formulas:

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

Upvotes: 8

Daniel Wagner
Daniel Wagner

Reputation: 152707

Why?

Because f' expects an Integer -> Integer function, but you're sending it faster_f', which is an Int -> Integer function.

And how can I fix it?

Probably the easiest way is to use genericIndex (from Data.List) instead of (!!).

Upvotes: 7

Related Questions