如果我正确理解这里的讨论,seq不应该两次评估一个值,因为x `seq` x应该评估x一次.
那为什么我有这种行为？
?> :set +s
?> let fib x = if x <= 1 then x else fib (x - 1) + fib (x - 2)
(0.01 secs, 102,600 bytes)
?> fib 30
832040
(2.49 secs, 638,088,448 bytes)
?> let x = fib 30 in x
832040
(2.47 secs, 638,088,792 bytes)
?> let x = fib 30 in x `seq` x
832040
(4.95 secs, 1,276,067,128 bytes)
这显然是双重评估？我误会了什么吗？
编辑:正如下面的@danidiaz所问,我也评估过
? …所以我的问题的简短版本是,我们如何在Haskell 中编码循环呢？在Haskell中没有尾部优化保证,爆炸模式甚至不是标准的一部分(对吗？),并且折叠/展开范例不能保证在所有情况下都能工作.在这种情况下,只有爆炸模式才能让我在恒定的空间中运行(甚至没有使用$!帮助......虽然测试是在使用ghc-6.8.2的Ideone.com上完成的).
它基本上是一个嵌套循环,在列表范例中可以表示为
prod (sum,concat) . unzip $
[ (c, [r | t]) | k<-[0..kmax], j<-[0..jmax], let (c,r,t)=...]
prod (f,g) x = (f.fst $ x, g.snd $ x)
或者在伪代码中:
let list_store = [] in
for k from 0 to kmax
for j from 0 to jmax
if test(k,j)
list_store += [entry(k,j)]
count += local_count(k,j)
result = (count, list_store)
直到我添加了爆炸模式,我得到了内存爆炸甚至堆栈溢出.但爆炸模式不是标准的一部分,对吧？所以问题是,如何在标准的Haskell中对上面的代码进行编码,以便在恒定的空间中运行？
这是测试代码.计算是假的,但问题是一样的.编辑:该foldr-formulated代码是:
testR m n …以下程序打击堆栈:
__find_first_occurrence :: (Eq b) => b -> [b] -> Int -> Int
__find_first_occurrence e [] i = -1
__find_first_occurrence e (x:xs) i
| e == x = i
| otherwise = __find_first_occurrence e xs (i + 1)
find_first_occurrence :: (Eq a) => a -> [a] -> Int
find_first_occurrence elem list =
__find_first_occurrence elem list 0
main = do
let n = 1000000
let idx = find_first_occurrence n [1..n]
putStrLn (show idx)
失败了
堆栈空间溢出:当前大小为8388608字节.使用`+ RTS -Ksize -RTS'来增加它.
但是,据我所知,可能的递归调用__find_first_occurrence是最后评估的事情 …