理解Haskell seq

Question

我是一个Haskell新手,理解有问题seq,我在下面的例子中进行了总结.

以下是相同(愚蠢)函数的2个实现.该函数采用正int n并返回元组(n,n).答案是通过(0,0)使用带有元组累加器的辅助函数进行计数来产生的.为了避免构建一个庞大的thunk我使用seq来使累加器严格.

在testSeq1元组的内容是严格的,而在testSeq2元组本身是严格的.我认为这两个实现将执行相同的操作.但实际上"使用中的总内存"仅为1MB,testSeq1但是大约为187MB testSeq2(使用n = 1000000进行测试时).

怎么了testSeq2？

testSeq1 :: Int -> (Int,Int)
testSeq1 n = impl n (0,0) where
    impl 0 (a,b) = (a,b)
    impl i (a,b) = seq a $ seq b $ impl (i-1) (a+1, b+1)

testSeq2 :: Int -> (Int,Int)
testSeq2 n = impl n (0,0) where
    impl 0 acc = acc
    impl i acc = seq acc $ impl (i-1) ((fst acc)+1, (snd acc)+1)

Answer 1

seq一个元组只强制它被评估,以暴露它的元组构造函数,但不会评估它的组件​​.

那是,

let pair = id (1+1, 2+2)
in seq pair $ ...

将应用id并产生(_thunk1, _thunk2)其中_thunk的立场给的增加,这是不是在这个时间进行评估.

在你的第二个例子中,你强制累加器acc,而不是它的组件,因此仍然会积累一些大的thunk.

您可以使用所谓的评估策略,例如:

evalPair :: (a,b) -> ()
evalPair (a,b) = seq a $ seq b ()

testSeq2 :: Int -> (Int,Int)
testSeq2 n = impl n (0,0) where
impl 0 acc = acc
impl i acc = seq (evalPair acc) $ impl (i-1) ((fst acc)+1, (snd acc)+1)

但是,这testSeq1是一种更简单的方法.

作为另一种选择,使用严格的元组.这样的元组永远不会有组件的thunk,但只评估结果.强制tuple构造函数将强制组件,如您所料.

import Data.Strict.Tuple

testSeq2 :: Int -> Pair Int Int
testSeq2 n = impl n (0 :!: 0) where
impl 0 acc = acc
impl i acc = seq acc $ impl (i-1) ((fst acc + 1) :!: (snd acc + 1))

Answer 2

seq只强迫对其第一个论点的评价.你可以看到这两个例子:

errorTuple :: (Int, Int)
errorTuple = undefined

errorTupleContents :: (Int, Int)
errorTupleContents = (undefined, undefined)

case1 = errorTuple `seq` (1, 1)
case2 = errorTupleContents `seq` (1, 1)

case1将失败与undefined错误,因为seq试图力的评价errorTuple,这是undefined,但是,case2不会,因为元组构造进行评价,并返回一个元组,其内容是未评估.如果他们被评估,他们就是undefined.