Возможны ли рекурсивные определения с незанятыми векторами?

Question

Я хотел бы сгенерировать unboxed вектор рекурсивно. В качестве простого примера:

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

Единственный способ, которым я могу это сделать, - создать ленивый рекурсивный список, а затем преобразовать его в unboxed vector.

Стандарт озадачивает колдовство

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

даст вам бесконечный список чисел Фибоначчи. Затем вы можете создать список из списка, который будет быстро индексироваться.

Несомненно, на самом деле он не использует вектор для вычисления номера Фибоначчи. Но он не делает индексацию O (n) по связанному списку, поэтому он должен быть достаточно быстрым.

Answer 3

constructN делает то, что вы хотите, даже в случае Unboxed. Ниже, 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))