variante del triangolo di pascal in haskell - problema con valutazione pigra

Question

Per risolvere alcuni problemi devo calcolare una variante del triangolo del pascal che è definito in questo modo:

f(1,1) = 1, 
f(n,k) = f(n-1,k-1) + f(n-1,k) + 1 for 1 <= k < n, 
f(n,0) = 0,
f(n,n) = 2*f(n-1,n-1) + 1.

Per n data voglio ottenere in modo efficiente il n-esima riga (f (n, 1) .. f (n, n)). Una ulteriore limitazione: f (n, k) dovrebbe essere -1 se sarebbe> = 2 ^ 32

.

La mia realizzazione:

next :: [Int64] -> [Int64]
next list@(x:_) = x+1 : takeWhile (/= -1) (nextRec list)

nextRec (a:rest@(b:_)) = boundAdd a b : nextRec rest
nextRec [a] = [boundAdd a a]

boundAdd x y
    | x < 0 || y < 0 = -1
    | x + y + 1 >= limit = -1
    | otherwise = (x+y+1)

-- start shoud be [1]
fLine d start = until ((== d) . head) next start

Il problema: per numeri molto grandi ottengo un overflow dello stack. C'è un modo per forzare Haskell per valutare l'intera lista? È chiaro che ogni riga non può contenere più elementi di un limite superiore, perché alla fine diventano -1 e non vengono memorizzati e ogni linea dipende solo quello precedente. A causa della valutazione pigra solo la testa di ogni riga è calcolato fino all'ultima riga ha bisogno del secondo elemento e tutti i tronchi lungo la strada vengono memorizzati ... Ho un'implementazione molto efficace in C ++, ma sono davvero chiedo se c'è un modo per farlo fare in Haskell, anche.

Answer 1

funziona per me: implementazione Cosa Haskell stai usando? Un programma ingenuo per calcolare questo triangolo lavori bene per me in GHC 6.10.4. Posso stampare la riga 1000i bene:

nextRow :: [Integer] -> [Integer]
nextRow row = 0 : [a + b + 1 | (a, b) <- zip row (tail row ++ [last row])]

tri = iterate nextRow [0]

main = putStrLn $ show $ tri !! 1000               -- print 1000th row

I può persino stampare i primi 10 numeri in fila 100000 senza traboccare lo stack. Io non sono sicuro di quello che sta andando male per voi. Il nome tri globale potrebbe essere mantenendo l'intero triangolo risultati vivo, ma anche se è, che sembra relativamente innocuo.

Come forzare ordine di valutazione: È possibile forzare thunk da valutare in un certo ordine utilizzando la funzione di Prelude seq (che è una funzione magica che non può essere implementato in termini di Haskell di altri caratteristiche di base). Se dite Haskell stampare a `seq` b, si valuta prima il thunk per a, quindi valuta e stampe b.

Si noti che seq è superficiale: è solo fa abbastanza valutazione per forza a non essere più un tonfo. Se a è di un tipo tupla, il risultato potrebbe essere ancora una tupla di thunk. Se si tratta di una lista, il risultato potrebbe essere una cella cons avere thunk sia per la testa e la coda.

Sembra che non dovreste aver bisogno di fare questo per un semplice problema così; poche migliaia di thunk non dovrebbe essere troppo per qualsiasi implementazione ragionevoli. Ma che sarebbe andata in questo modo:

-- Evaluate a whole list of thunks before calculating `result`.
-- This returns `result`.
seqList :: [b] -> a -> a
seqList lst result = foldr seq result lst

-- Exactly the same as `nextRow`, but compute every element of `row`
-- before calculating any element of the next row.
nextRow' :: [Integer] -> [Integer]
nextRow' row = row `seqList` nextRow row

tri = iterate nextRow' [0]

La piega in seqList espande fondamentalmente per lst!!0 `seq` lst!!1 `seq` lst!!2 `seq` ... `seq` result.

Questo è molto più lento per me quando la stampa solo i primi 10 elementi della fila 100.000. Penso che sia perché richiede di calcolo 99.999 righe complete del triangolo.