variante del triángulo de Pascal en Haskell - problema con la evaluación perezosa

Question

Para resolver un problema que necesito para calcular una variante del triángulo de Pascal, que se define así:

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.

Para n dada quiero conseguir de manera eficiente la enésima línea (f (n, 1) .. f (n, n)). Una restricción adicional: f (n, k) debe ser -1 si sería> = 2 ^ 32

.

Mi aplicación:

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

El problema: por un número muy grande me sale un desbordamiento de pila. ¿Hay una manera de forzar a Haskell para evaluar toda la lista? Está claro que cada línea no puede contener más elementos que un límite superior, ya que eventualmente se convierten en -1 y no se almacenan y cada línea sólo depende de la anterior. Debido a la evaluación perezosa sólo la cabeza de cada línea se calcula hasta que la última línea lo necesita de segundo elemento y se almacenan todos los troncos en el camino ... Tengo una aplicación muy eficiente en C ++ pero estoy realmente preguntando si hay una manera de lograr que se haga en Haskell, también.

Answer 1

Obras para mí: ¿Qué aplicación Haskell está utilizando? Un programa ingenuo para calcular este fino obras triángulo para mí en GHC 6.10.4. Puedo imprimir la fila 1000a 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

Incluso puede imprimir los primeros 10 números en la fila 100000 sin desbordar la pila. No estoy seguro de lo que va mal para usted. El nombre tri global podría estar manteniendo todo el triángulo de los resultados con vida, pero incluso si lo es, que parece relativamente inofensivo.

Cómo forzar orden de evaluación: Puede forzar procesadores para ser evaluados en un orden determinado utilizando el seq función Preludio (que es una función de magia que no puede ser implementada en términos de Haskell de otra caracteristicas basicas). Si le dice a Haskell para imprimir a `seq` b, primero se evalúa el golpe seco de a, a continuación, evalúa y grabados b.

Tenga en cuenta que seq es poco profunda: es solamente hace lo suficiente la evaluación de la fuerza a a dejar de ser un golpe seco. Si a es de un tipo tupla, el resultado podría todavía ser una tupla de procesadores. Si se trata de una lista, el resultado podría ser una célula contras que tienen procesadores tanto para la cabeza y la cola.

Parece que no es necesario hacer esto para un problema tan sencillo; unos pocos miles de procesadores no deben ser demasiado para cualquier aplicación razonable. Sin embargo, sería algo así:

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

El pliegue en seqList básicamente se expande para lst!!0 `seq` lst!!1 `seq` lst!!2 `seq` ... `seq` result.

Esto es mucho más lento para mí cuando se imprime sólo los primeros 10 elementos de la fila 100.000. Creo que eso es debido a que requiere el cálculo de 99.999 filas completas del triángulo.