haskell - 强制严格评估——我做错了什么？

Question

我想要在生成新结果之前计算出一个中间结果，以获得内存的好处。

import qualified Data.Map.Strict as M
import Data.List
parts' m = newmap
    where
    n = M.size m + 1 
    lists =  nub $ map sort $ 
        [n] : (concat $ map (\i -> map (i:) (M.findWithDefault [] (n-i) m)) [1..n])
    newmap = seq lists (M.insert n lists m)

但是，如果我这样做

take 2000 (iterate parts' (M.fromList [(1,[[1]])]))

它仍然会立即完成。

(使用数组代替 Map 有帮助吗？)

Answer 1

简短回答:

如果您需要立即计算整个列表/数组/ map /...，您可以按照@JoshuaRahm的建议使用deepseq，或者 ($!!) 运算符。

下面的答案是如何强制执行严格性的，但仅在级别 1(它会进行评估，直到到达可能包含表达式树(其余部分)的数据结构)。

此外，答案还论证了为什么懒惰和内存并不(必然)是对立的。

更高级:

Haskell 是一种惰性语言，这意味着它仅在绝对必要时才计算某些内容。表达式如下:

take 2000 (iterate parts' (M.fromList [(1,[[1]])]))

不会立即计算:Haskell 只是存储这必须稍后计算。稍后，如果您确实需要第一个、第二个、i-th 或列表的长度，它将对其进行评估，甚至以一种懒惰的方式:如果您需要第一个元素，则从当它找到计算该元素的方法时，它将把它表示为:

element : take 1999 (<some-expression>)

但是，您可以强制 Haskell 使用 exclamation mark (!) 严格评估某些内容，这称为严格性。例如:

main = do
    return $! take 2000 (iterate parts' (M.fromList [(1,[[1]])]))

或者如果它是一个参数，您可以像这样使用它:

f x !y !z = x+y+z

在这里，您强制 Haskell 在“增加表达式树”之前计算 y 和 z:

expression-for-x+expression-for-y+expression-for-z.

编辑:如果您在 let 模式中使用它，则可以 use the bang as well :

let !foo = take 2000 (iterate parts' (M.fromList [(1,[[1]])])) in ...

<小时/>

请注意，您仅将结构折叠到第一层。因此 let !foo 或多或少只会计算到 (_:_)。

<小时/>

注意:请注意，内存和懒惰不一定是彼此对立的。考虑一下列表:

numbers :: [Integer]
numbers = 0:[i+(sum (genericTake i numbers))|i<-[1..]]

如您所见，计算一个数字需要大量的计算工作。数字表示如下:

numbers ---> (0:[i+(sum (genericTake i numbers))|i<-[1..]])

但是，如果我计算 numbers!!1，它将必须计算第一个元素，它返回 1；但 numbers 的内部结构也会被评估。现在看起来像:

numbers (0:1:[i+(sum (genericTake i numbers))|i<-[2..]])

计算 numbers!!1 因此将“帮助” future 的计算，因为您永远不必重新计算列表中的第二个元素。

例如，如果您计算numbers!!4000，则需要几秒钟的时间。稍后如果你计算numbers!!4001，几乎会立即计算出来。仅仅是因为 numbers!!4000 已经完成的工作被重用。