Forcing Strict Evaluation - What am I doing wrong?

Question

I want an intermediate result computed before generating the new one to get the benefit of memoization.

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)

But, then if I do

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

It still completes instantaneously.

(Can using an Array instead of a Map help?)

Answer 1

Short answer:

If you need to calculate the entire list/array/map/... at once, you can use deepseq as @JoshuaRahm suggests, or the ($!!) operator.

The answer below how you can enforce strictness, but only on level-1 (it evaluates until it reaches a datastructure that may contain (remainders) of expression trees).

Furthermore the answer argues why laziness and memoization are not (necessarily) opposites of each other.

More advanced:

Haskell is a lazy language, it means it only calculates something, if it is absolutely necessary. An expression like:

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

is not evaluated immediately: Haskell simply stores that this has to be calculated later. Later if you really need the first, second, i-th, or the length of the list, it will evaluate it, and even then in a lazy fashion: if you need the first element, from the moment it has found the way to calculate that element, it will represent it as:

element : take 1999 (<some-expression>)

You can however force Haskell to evaluate something strictly with the exclamation mark (!), this is called strictness. For instance:

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

Or in case it is an argument, you can use it like:

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

Here you force Haskell to evaluate y and z before "increasing the expression tree" as:

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

EDIT: if you use it in a let pattern, you can use the bang as well:

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

---

Note that you only collapse the structure to the first level. Thus let !foo will more or less only evaluate up to (_:_).

---

Note: note that memoization and lazyness are not necessary opposites of each other. Consider the list:

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

As you can see, calculating a number requires a large amount of computational effort. Numbers is represented like:

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

if however, I evaluate numbers!!1, it will have to calculate the first element, it returns 1; but the internal structure of numbers is evaluated as well. Now it looks like:

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

The computation numbers!!1 thus will "help" future computations, because you will never have to recalcuate the second element in the list.

If you for instance calculate numbers!!4000, it will take a few seconds. Later if you calculate numbers!!4001, it will be calculated almost instantly. Simply because the work already done by numbers!!4000 is reused.