3

I've been asking a few questions about strictness, but I think I've missed the mark before. Hopefully this is more precise.

Lets say we have:

n = 1000000
f z = foldl' (\(x1, x2) y -> (x1 + y, y - x2)) z [1..n]

Without changing f, what should I set

z = ...

So that f z does not overflow the stack? (i.e. runs in constant space regardless of the size of n)

Its okay if the answer requires GHC extensions.

My first thought is to define:

g (a1, a2) = (!a1, !a2)

and then

z = g (0, 0)

But I don't think g is valid Haskell.

Clinton
  • 22,361
  • 15
  • 67
  • 163

2 Answers2

9

So your strict foldl' is only going to evaluate the result of your lambda at each step of the fold to Weak Head Normal Form, i.e. it is only strict in the outermost constructor. Thus the tuple will be evaluated, however those additions inside the tuple may build up as thunks. This in-depth answer actually seems to address your exact situation here.

W/R/T your g: You are thinking of BangPatterns extension, which would look like 

g (!a1, !a2) = (a1, a2)

and which evaluates a1 and a2 to WHNF before returning them in the tuple.

What you want to be concerned about is not your initial accumulator, but rather your lambda expression. This would be a nice solution:

f z = foldl' (\(!x1, !x2) y -> (x1 + y, y - x2)) z [1..n]

EDIT: After noticing your other questions I see I didn't read this one very carefully. Your goal is to have "strict data" so to speak. Your other option, then, is to make a new tuple type that has strictness tags on its fields:

data Tuple a b = Tuple !a !b

Then when you pattern match on Tuple a b, a and b will be evaluated.

You'll need to change your function regardless.

Community
  • 1
  • 1
jberryman
  • 16,334
  • 5
  • 42
  • 83
3

There is nothing you can do without changing f. If f were overloaded in the type of the pair you could use strict pairs, but as it stands you're locked in to what f does. There's some small hope that the compiler (strictness analysis and transformations) can avoid the stack growth, but nothing you can count on.

augustss
  • 22,884
  • 5
  • 56
  • 93