CODEWITHSUNDEEP
arrayshaskell
Xychic
Xychic

Reputation: 23

Creating an array with a function using index and array?

I am wanting to create an array of the Fibonacci numbers using haskell, but using a this more efficient algorithm

F(2K) = F(K)[2F(K-1)-F(K)]
F(2K+1) = F(K+1)^2 + F(K)^2

I know the function works and I can pass through the index or the array but not both and I can't figure out why

fastFibo :: Array Int Int -> Int -> Int
fastFibo a 0 = 0
fastFibo a 1 = 1
fastFibo a 2 = 1
fastFibo a x = do
    if ((mod x 2) == 0) 
        then do
            let y = div x 2
            (a!y) * (2 * (a!(y+1)) - (a!y))
        else do
            let y = div (x-1) 2
            (a!y)^2 + (a!(y+1))^2

fibos n = a where a = array (0,n) ([(0, 0), (1, 1), (2,1)] ++ [(i, fastFibo(a i)) | i <- [2..n]])

The error I get is 

    • Couldn't match expected type ‘i1 -> Array Int Int’
                  with actual type ‘Array i1 (Int -> Int)’
    • Possible cause: ‘array’ is applied to too many arguments
      In the expression:
        array
          (0, n)
          ([(0, 0), (1, 1), (2, 1)] ++ [(i, fastFibo (a i)) | i <- [2 .. n]])
      In an equation for ‘a’:
          a = array
                (0, n)
                ([(0, 0), (1, 1), (2, 1)] ++ [(i, fastFibo (a i)) | i <- [2 .. n]])
      In an equation for ‘fibos’:
          fibos n
            = a
            where
                a = array
                      (0, n) ([(0, 0), ....] ++ [(i, fastFibo (a i)) | i <- [2 .. n]])
    • Relevant bindings include
        a :: i1 -> Array Int Int
          (bound at /mnt/data/Documents/Programming/Haskell/Arrays/Arrays.hs:20:19)
   |
20 | fibos n = a where a = array (0,n) ([(0, 0), (1, 1), (2,1)] ++ [(i, fastFibo(a i)) | i <- [2..n]])
   |                       ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Upvotes: 2

Views: 84

Answers (1)

sshine
sshine

Reputation: 16145

Using a less fast algorithm that still operates on an array, you could do:

import Data.Array

fib :: Int -> Int
fib n = arr ! n
  where
    arr :: Array Int Int
    arr = listArray (1, n) $
      0 : 1 : [ (arr ! (i-1)) + (arr ! (i-2)) | i <- [3..n] ]

If you were to transform this to use your faster algorithm, it'd be something like:

import Data.Array

fib :: Int -> Int
fib n = arr ! n
  where
    arr :: Array Int Int
    arr = listArray (1, n) $
      0 : 1 : 1 : map fib' [4..n]

    fib' :: Int -> Int
    fib' k
      | even k    = ...
      | otherwise = ...

I figured listArray was sufficient here. It's pretty close to array which you use.

See the documentation on array construction for the difference.

Upvotes: 2

Related Questions