algorithm - 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) >= 2^32，则它应该是 -1。

我的实现:

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

问题:对于非常大的数字，我会出现堆栈溢出。有没有办法强制 haskell 评估整个列表？很明显，每行不能包含超过上限的元素，因为它们最终会变成 -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

我什至可以打印第 100000 行的前 10 个数字而不会溢出堆栈。我不确定你怎么了。全局名称 tri 可能会让整个三角形的结果保持活力，但即便如此，这似乎也相对无害。

如何强制求值顺序:您可以使用 Prelude 函数 seq(这是一个神奇的函数，不能根据 Haskell 的其他基本功能来实现)。如果你告诉 Haskell 打印 a `seq` b，它首先计算 a 的 thunk，然后计算并打印 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` 结果.

当只打印第 100,000 行的前 10 个元素时，这对我来说要慢得多。我认为这是因为它需要计算 99,999 行完整的三角形。