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

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]])]))

还是瞬间完成。

（使用 Array 代替 Map 有帮助吗？）

Answer 1

简答：

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

下面的答案是如何强制执行严格性，但 仅在 level-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在"increasing the expression tree"之前计算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 或多或少只会评估 (_:_).

注意：注意memoization和lazyness不是必然的对立面。考虑列表：

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

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

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

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

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

计算 numbers!!1 因此将 "help" 未来的计算，因为您永远不必重新计算列表中的第二个元素。

例如，如果您计算 numbers!!4000，将需要几秒钟。后面如果计算numbers!!4001，几乎是瞬间就计算出来了。仅仅因为 numbers!!4000 已经完成的工作被重用 .

Answer 2

数组可能会有所帮助，但您也可以尝试利用 deepseq 库。所以你可以这样写代码：

let x = take 2000 (iterate parts' (M.fromList [(1,[[1]])])) in do
     x `deepseq` print (x !! 5)    -- takes a *really* long time
     print (x !! 1999)             -- finishes instantly

Answer 3

您正在记忆分区函数，但您的方法存在一些缺点：

你只能记住一个你必须事先指定的特定值
你需要调用 nub 和 sort

这是一种使用 Data.Memocombinators 的方法：

import Data.Memocombinators

parts = integral go
  where
    go k | k <= 0 = []  -- for safety
    go 1 = [[1]]
    go n = [[n]] ++ [ (a : p) | a <- [n-1,n-2..1], p <- parts (n-a), a >= head p ]

例如：

ghci> parts 4
[[4],[3,1],[2,2],[2,1,1],[1,1,1,1]]

此记忆是动态的，因此只会记忆您实际访问的值。

请注意它的构造方式 - parts = integral go，并且 go 使用 parts 进行任何递归调用。我们在这里使用 integral 组合器，因为 parts 是 Int 的函数。

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

Forcing Strict Evaluation - What am I doing wrong?

haskell

functional-programming

seq