Last active
December 21, 2015 05:38
-
-
Save gelisam/6257856 to your computer and use it in GitHub Desktop.
Polymorphism and memoization interact in strange ways.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import Debug.Trace | |
noisy0 :: () -> Int | |
noisy0 () = trace "eval" 0 | |
main = do print (let x = ( noisy0 () | |
, fst x) | |
in x) -- evals noisyMempty once | |
print (( noisy0 () | |
, fst ( noisy0 () | |
, undefined))) -- evals noisyMempty twice |
further simplification: polymorphism is not needed in order to trigger the difference! I did have to turn noisyMempty
into a function, though. Presumably, polymorphism was implicitly causing noisyMempty
to behave like a function, whose argument is a type.
At last, an explanation! By repeatedly inlining and simplifying all the definitions, we see that the let-based version of fix
has one call to noisy0
and one reference to it, while the non-let-based version has infinitely-many calls to noisy0
, but only two of them need to be evaluated in order to compute the result.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Further simplification: the way in which
fix
is implemented matters. As you can see, usinglet
allows sub-expressions to be reused. But why? I didn't expectlet
to be very magic.