Haskell Lazy Evaluation and Reuse

问题:

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

回答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.

回答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.

回答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.

回答4:

Why not use ghci to test (if ghc is your compiler):

Prelude> let squares = [ x ** 2 | x <- [1 ..] ] :: [Float]
Prelude> :print squares
squares = (_t6::[Float])

So all ghci knows right now it that you have a list.

Prelude> print $ take 4 squares
[1.0,4.0,9.0,16.0]
Prelude> :print squares
squares = 1.0 : 4.0 : 9.0 : 16.0 : (_t7::[Float])

Know it knows that your list begins with stuff, because to it had to evaluate to print it.

Prelude> let z = take 5 squares
Prelude> :print z
z = (_t8::[Float])

take 5 by itself doesn't evaluate anything

Prelude> length z --Evaluate the skeleton
5
Prelude> :print z
z = [1.0,4.0,9.0,16.0,(_t9::Float)]

Taking the length causes take to run its course, and we see that you were right. You can test what's happening when its polymorphic as well, by just omitting the type definition on squares. Another good trick if you don't want to use ghci is to use undefined in your code (your program crashes exactly when it attempts to evaluate a _|_, which undefined is a type of.)