Variante do triângulo de Pascal em Haskell - Problema com avaliação preguiçosa

Question

Para resolver algum problema, preciso calcular uma variante do triângulo do Pascal, que é definido assim:

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, dado, quero obter com eficiência a n-ésima linha (f (n, 1) .. f (n, n)). Uma restrição adicional: f (n, k) deve ser -1 se for> = 2^32.

Minha implementação:

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

O problema: para números muito grandes, recebo um transbordamento de pilha. Existe uma maneira de forçar Haskell a avaliar toda a lista? É claro que cada linha não pode conter mais elementos do que um limite superior, porque eles acabam se tornando -1 e não são armazenados e cada linha depende apenas do anterior. Devido à avaliação preguiçosa, apenas a cabeça de cada linha é calculada até que a última linha precise de seu segundo elemento e todos os troncos ao longo do caminho sejam armazenados ... Eu tenho uma implementação muito eficiente em C ++, mas estou realmente me perguntando se há um Maneira de fazê -lo em Haskell também.

Answer 1

Funciona para mim: Qual a implementação do Haskell você está usando? Um programa ingênuo para calcular esse triângulo funciona bem para mim no GHC 6.10.4. Eu posso imprimir a 1000ª fila bem:

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

Posso até imprimir os 10 primeiros números na linha 100000 sem transbordar a pilha. Não tenho certeza do que está errado para você. O nome global tri Pode estar mantendo todo o triângulo de resultados vivos, mas mesmo que seja, isso parece relativamente inofensivo.

Como forçar a ordem de avaliação: Você pode forçar Thunks a ser avaliado em uma determinada ordem usando a função de prelúdio seq (que é uma função mágica que não pode ser implementada em termos dos outros recursos básicos de Haskell). Se você diz a Haskell para imprimir a `seq` b, primeiro avalia o Thunk para a, então avalia e impressões b.

Observe que seq é superficial: é só Avaliação suficiente para forçar a para não ser mais um Thunk. Se a é do tipo de tupla, o resultado ainda pode ser uma tupla de Thunks. Se for uma lista, o resultado pode ser uma célula contras com thunks para a cabeça e a cauda.

Parece que você não precisa fazer isso para um problema tão simples; Alguns milhares de thunks não devem ser demais para nenhuma implementação razoável. Mas seria assim:

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

A dobra entra seqList basicamente se expande para lst!!0 `seq` lst!!1 `seq` lst!!2 `seq` ... `seq` result.

Isso é muito mais lento para mim ao imprimir apenas os 10 primeiros elementos da linha 100.000. Eu acho que é porque requer computação de 99.999 linhas completas do triângulo.