Variante des Dreiecks pascal in Haskell - Problem mit lazy evaluation

Question

Um ein Problem zu lösen Ich brauche eine Variante des Pascalschen Dreiecks zu berechnen, die wie folgt definiert ist:

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.

n gegeben Ich mag die n-te Zeile effizient erhalten (f (n, 1) .. f (n, n)). Eine weitere Einschränkung: f (n, k) sollte sein, -1, wenn es sei,> = 2 ^ 32

.

Meine Implementierung:

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

Das Problem: für sehr große Zahlen bekomme ich einen Stack-Überlauf. Gibt es eine Möglichkeit Haskell zu zwingen, die ganze Liste zu bewerten? Es ist klar, dass jede Zeile nicht mehr Elemente als eine obere Grenze enthalten kann, weil sie schließlich zu -1 und nicht gespeichert bekommen und jede Zeile hängt nur von der vorherigen. Aufgrund der verzögerten Auswertung nur der Kopf jeder Zeile berechnet wird, bis die letzte Zeile es das zweite Element und alle die Stämme auf dem Weg gespeichert werden muss ... Ich habe eine sehr effiziente Implementierung in C ++, aber ich frage mich wirklich, ob es einen Weg gibt, um es in Haskell getan, auch.

Answer 1

Arbeiten für mich: Was Haskell Implementierung verwenden Sie? Ein naiver Programm dieses Dreieck funktioniert gut für mich in GHC 6.10.4 zu berechnen. Ich kann die 1000. Zeile druckt ganz gut:

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

Ich kann sogar die ersten 10 Zahlen in Zeile 100000 drucken, ohne den Stapel überfüllt. Ich bin sicher nicht das, was Sie falsch läuft. Der globale Name tri könnte das ganze Dreieck der Ergebnisse am Leben zu halten, aber selbst wenn es ist, dass relativ harmlos scheint.

Wie Reihenfolge der Auswertung erzwingen: können Sie Thunks zwingen, in einer bestimmten Reihenfolge ausgewertet werden mit der Prelude Funktion seq (die eine magische Funktion, die nicht anderen in Bezug auf die Haskell implementiert werden kann Grundfunktionen). Wenn Sie Haskell sagen a `seq` b zu drucken, wertet sie zunächst die Thunk für a, dann auswertet und druckt b.

Beachten Sie, dass seq ist flach: es nur nicht genug Auswertung Kraft a nicht mehr ein Thunk sein. Wenn a eines Tupels Typ ist, könnte das Ergebnis noch ein Tupel von Thunks sein. Wenn es sich um eine Liste ist, könnte das Ergebnis eine cons Zelle sein Thunks mit sowohl für den Kopf und den Schwanz.

Es scheint, wie Sie nicht benötigen, sollten diese für ein solches einfaches Problem zu tun; ein paar tausend Thunks für vernünftige Umsetzung sollte nicht zu viel sein. Aber es wäre so:

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

Die Falte in seqList erweitert grundsätzlich lst!!0 `seq` lst!!1 `seq` lst!!2 `seq` ... `seq` result.

Das ist viel für mich langsamer beim Drucken nur die ersten 10 Elemente der Reihe 100.000. Ich denke, das ist, weil es die Berechnung 99.999 komplette Reihen des Dreiecks erfordert.