可以使用未装箱的向量进行递归定义吗？

Question

我想以递归方式生成一个未装箱的矢量.举个简单的例子:

import qualified Data.Vector as V

fib :: V.Vector Int
fib = V.generate 10 f
  where
    f 0 = 0
    f 1 = 1
    f x = (fib V.! (x - 1)) + (fib V.! (x - 2))

该函数正确地生成斐波那契序列.但是,如果我使用Data.Vector.Unboxed,代码将挂起.我理解为什么会这样,但我仍然希望能够做一个递归定义并获得一个未装箱的矢量的速度.这样做有可能吗？

Answer 1

一种可能性是使用未装箱的可变矢量并在构造完成后将其冻结:

import Control.Monad.ST (runST)
import Control.Monad (forM_, ap)
import qualified Data.Vector.Unboxed as U
import qualified Data.Vector.Unboxed.Mutable as M

fib :: Int -> U.Vector Int
fib s = runST $ M.new s >>= ap ((>>) . forM_ [0..s - 1] . f) U.unsafeFreeze
    where
    f v 0 = M.write v 0 0
    f v 1 = M.write v 1 1
    f v i = do
        a <- M.read v (i - 1)
        b <- M.read v (i - 2)
        M.write v i (a + b)

Answer 2

constructN做你想要的,即使在未装箱的情况下.下面v是到目前为止构建的向量前缀,并f v返回下一个元素.

最佳O(N)复杂度.

import qualified Data.Vector.Unboxed as V

fib :: V.Vector Int
fib = V.constructN 10 f
  where
    f v = case V.length v of
            0 -> 0
            1 -> 1
            n -> (v V.! (n - 1)) + (v V.! (n - 2))