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

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)