Creating an array with a function using index and array?

Question

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]])
   |                       ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

The expression fastFibo(a i) doesn't mean what you think it does. Use (fastFibo a i) instead. — Bob Dalgleish
– Bob Dalgleish, Commented Nov 18, 2019 at 16:15
Suggestion: don't use do unless you are working in a monad. In the code above, you are not. Further, adding a type signatures to fibos would help GHC produce better type error messages. — chi
– chi, Commented Nov 18, 2019 at 18:53

sshine · Accepted Answer · 2019-11-18 16:31:45Z

2

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.

edited Nov 18, 2019 at 16:31

answered Nov 18, 2019 at 16:19

sshine

16.2k1 gold badge45 silver badges71 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Creating an array with a function using index and array?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related