arrays - 使用索引和数组创建带有函数的数组？

Question

我想使用 haskell 创建一个斐波那契数列，但使用这种更有效的算法

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

我知道该函数有效，我可以通过索引或数组，但不能同时通过，我不知道为什么

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

我得到的错误是

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

Answer 1

使用仍然在数组上运行的速度较慢的算法，您可以执行以下操作:

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

如果您要将其转换为使用更快的算法，它将类似于:

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 = ...

我想 listArray在这里就足够了。非常接近 array你使用的。

请参阅 array construction 上的文档对于差异。