Geek Answers Handbook

Can recursive definitions be done using decompressed vectors?

I would like to generate an unboxed vector recursively. As a simple example:

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

the function correctly generates a fibonacci sequence. However, if I use Data.Vector.Unboxedinstead, the code will hang. I understand the reason why this is so, but I would still like to be able to make a recursive definition and get the speed of the decompressed vector. Are there any possibilities for this?

+4
source share
3 answers

One possibility is to use an unboxed mutable vector and freeze it after execution with construction:

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)
+5
source

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))
+4

The only way I can do this is to create a lazy recursive list and then convert it to an unboxed vector.

Standard puzzling spell

fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

will give you an endless list of Fibonacci numbers. Then you can create a list from a list that will have a quick index after that.

Of course, in fact, he does not use the vector to calculate Fibonacci numbers. But it does not index O (n) by linked list, so it should be fast enough.

+3
source

More articles:


All Articles