在Haskell杨辉三角的变种 - 懒惰的评价问题

Question

要解决一些问题，我需要计算其被这样定义的帕斯卡三角形的变体：

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给出我想有效地得到第n行（F（N，1）.. F（N，N））。一个进一步的限制：F（N，K）应为-1，如果这将是> = 2 ^ 32

。

我的实现：

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

问题：为非常大的数字，我得到一个堆栈溢出。有没有办法迫使哈斯克尔评估整个清单吗？很明显，每行不能含有比上限更多的元素，因为他们最终成为-1，不要让存储和每行只依赖于前一个。由于懒惰的评估只计算每行的头，直到最后一行需要它的第二个元素，所有沿途的树干存储... 我有一个在C非常有效的实现++，但我真的不知道是否有得到它在Haskell做的方式了。

Answer 1

对我的作品：什么Haskell的实现您使用？一个天真的程序在GHC 6.10.4计算这个三角形的作品对我很好。我可以打印1000个行就好了：

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

我甚至可以打印10万行的第10个号码而不溢出堆栈。我不知道发生了什么错你。全局名称tri可能是保持结果的整个三角形活着，但即使是这样，这似乎相对无害的。

如何强制评估的顺序：：您可以强制的thunk使用前奏功能seq（这是一个神奇的功能，不能在Haskell的其他方面来实现一定的顺序来进行评估基本功能）。如果你告诉哈斯克尔打印a `seq` b，它首先将评估a形实转换，然后计算并打印b。

请注意seq浅：它的只有的不足够的评估力a不再是一个thunk。如果a是一个元组类型，结果仍可能是的thunk的元组。如果它是一个列表，则结果可能是具有用于头部和尾部两者的thunk一个cons单元。

好像你不应该需要这样一个简单的问题，做到这一点;几千元的thunk不应该过多对任何合理的实施。但是，如果是这样的：

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

在seqList折叠基本上扩展到lst!!0 `seq` lst!!1 `seq` lst!!2 `seq` ... `seq` result。

这是慢得多的用于我打印只是100000行的第一个10个元素时。我认为这是因为它需要计算三角形的99,999完整行。