1

为了解决一些问题，我需要计算帕斯卡三角形的变体，其定义如下：

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，则 f(n,k) 应为 -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中完成它的方法也是。

4

1 回答 1

5

对我有用：您使用的是什么 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可能使整个三角形的结果保持活力，但即使是这样，这似乎也相对无害。

如何强制求值顺序：seq您可以使用 Prelude 函数（这是一个神奇的函数，在 Haskell 的其他基本特性方面无法实现）强制以特定顺序对 thunk 进行求值。如果你告诉 Haskell 打印a `seq` b，它首先计算 thunk 的值a，然后计算并打印b。

请注意，这seq很浅：它只进行了足够的评估以强制a不再是 thunk。如果a是元组类型，则结果可能仍然是一个 thunk 元组。如果它是一个列表，则结果可能是一个 cons 单元格，其中包含头部和尾部的 thunk。

对于这样一个简单的问题，您似乎不需要这样做；对于任何合理的实现，几千个 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。

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

于 2010-03-08T17:26:14.823 回答