variante du triangle de pascals en haskell - problème avec l'évaluation paresseuse

Question

Pour résoudre un problème que je dois calculer une variante du triangle de la pascals qui est défini comme suit:

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.

Pour n donné que je veux obtenir efficacement la ligne n-ième (f (n, 1) .. f (n, n)). Une restriction en outre:. F (n, k) doit être -1 s'il est> = 2 ^ 32

Ma mise en œuvre:

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

Le problème: pour un très grand nombre, je reçois un débordement de pile. Y at-il un moyen de forcer haskell d'évaluer toute la liste? Il est clair que chaque ligne ne peut pas contenir plus d'éléments que d'une limite supérieure, car ils finissent par devenir -1 et ne sont pas stockées et chaque ligne ne dépend que de la précédente. En raison de l'évaluation paresseuse que la tête de chaque ligne est calculée jusqu'à la dernière ligne a besoin de son deuxième élément et tous les troncs le long du chemin sont stockés ... J'ai une implémentation très efficace en c ++ mais je me demande vraiment s'il y a un moyen pour le faire dans haskell, aussi.

Answer 1

fonctionne pour moi: Qu'est-ce que la mise en œuvre Haskell utilisez-vous? Un programme naïf de calculer ce triangle fonctionne très bien pour moi dans GHC 6.10.4. Je peux imprimer la ligne 1000e très bien:

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

Je peux même imprimer les 10 premiers nombres dans la rangée 100000 sans déborder la pile. Je ne sais pas ce qui va mal pour vous. Le tri nom global pourrait être garder tout le triangle des résultats en vie, mais même si elle est, qui semble relativement inoffensif.

Comment forcer ordre d'évaluation: Vous pouvez forcer thunks à évaluer dans un certain ordre en utilisant la fonction Prelude seq (qui est une fonction magique qui ne peut pas être mis en œuvre en termes de Haskell de l'autre caractéristiques de base). Si vous dites Haskell d'imprimer a `seq` b, il évalue d'abord le thunk pour a, évalue ensuite et imprime b.

Notez que seq est peu profonde: il que fait une évaluation assez pour forcer a à ne plus être un thunk. Si a est d'un type de tuple, le résultat pourrait encore être un tuple de thunks. Si c'est une liste, le résultat pourrait être une cellule de contre ayant thunks pour la tête et la queue.

Il semble que vous ne devriez pas avoir besoin de faire cela pour un simple problème; quelques milliers thunks ne devraient pas être trop pour une mise en œuvre raisonnable. Mais il irait comme ceci:

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

Le pli en seqList se dilate essentiellement à lst!!0 `seq` lst!!1 `seq` lst!!2 `seq` ... `seq` result.

Ceci est beaucoup plus lent pour moi lors de l'impression seulement les 10 premiers éléments de ligne 100 000. Je pense que ce parce qu'il nécessite l'informatique 99.999 lignes complètes du triangle.