Search code examples
haskellfunctional-programming

Haskell function memoization/result caching


I have read a blog post that mentions Haskell optmization. It says:

if Haskell sees multiple copies of this expensive function called on the exact same input, it will simply evaluate one of the function calls, cache the result, and replace every future function call of F on that same input with the cached result.

It uses this as an example how Haskell is better then Python (for calling same heavy function multiple times.

And from reading it I'm asking myself. How can this be true for a function that does any kind of IO?


Solution

    1. The claim is wrong. No extant implementation of Haskell automatically memoizes.

    2. If an implementation were to do this, some parts of the construction of an IO action could be memoized, and some couldn't. It may be that there's some non-trivial computation that needs to be done to decide what IO should happen; for example:

      f :: Int -> IO ()
      f n = if existsPrimesThatAddTo (2*n)
          then putStrLn "Goldbach conjecture not yet disproven"
          else putStrLn "Wow, resolved an open math problem!"
      

      The decision about which branch to descend into could be memoized. The activity of printing to the screen could not. One of the miracles of the way Haskell does IO is that the type system can tell you which bits of an IO action computation could be memoized and which couldn't.