Haskell Lazy Evaluation and Reuse

Question

I know that if I were to compute a list of squares in Haskell, I could do this:

squares = [ x ** 2 | x <- [1 ..] ]

Then when I call squares like this:

print $ take 4 squares

And it would print out [1.0, 4.0, 9.0, 16.0]. This gets evaluated as [ 1 ** 2, 2 ** 2, 3 ** 2, 4 ** 2 ]. Now since Haskell is functional and the result would be the same each time, if I were to call squares again somewhere else, would it re-evaluate the answers it's already computed? If I were to re-use squares after I had already called the previous line, would it re-calculate the first 4 values?

print $ take 5 squares

Would it evaluate [1.0, 4.0, 9.0, 16.0, 5 ** 2]?

Answer 1

In this case, it won't be recalculated because the list actually gets built, and the squares list continues to exist after the call. However, Haskell functions in general are not memoized. This only works for a case like this where you're not explicitly calling a function, just exploring an (in)finite list.

Answer 2

This value squares is potentially polymorphic:

Prelude> :t [ x ** 2 | x <- [1 ..] ]
[ x ** 2 | x <- [1 ..] ] :: (Floating t, Enum t) => [t]

AFAIK, whether or not it will be recalculated (in GHC) depends on whether the top-level value squares is given a polymorphic type. I believe that GHC does not do any memoization of polymorphic values involving type classes (functions from types to values), just as it does not do any memoization of ordinary functions (functions from values to values).

That means if you define squares by

squares :: [Double]
squares = [ x ** 2 | x <- [1 ..] ]

then squares will only be computed once, while if you define it by

squares :: (Floating t, Enum t) => [t]
squares = [ x ** 2 | x <- [1 ..] ]

then it will likely be computed each time it is used, even if it's used repeatedly at the same type. (I haven't tested this, though, and it's possible that GHC, if it sees several uses of squares :: [Double], could specialize the squares value to that type and share the resulting value.) Certainly if squares is used at several different types, like squares :: [Double] and squares :: [Float], it will be recalculated.

If you don't give any type signature for squares, then the monomorphism restriction will apply to it, unless you have it disabled. The result will be that squares is assigned a monomorphic type, inferred from the rest of your program (or according to the defaulting rules). The purpose of the monomorphism restriction is exactly to ensure that values that look like they will only be evaluated once, such as your squares, really will only be evaluated once.

Answer 3

To clarify an answer already given, this is a Haskell function:

thisManySquares n = map (^2) [1..n]

So, if you substituted calls of "thisManySquares 4" for your take 4 squares, then yes, it would call the function repeatedly.