Haskell默认会Memoize所有函数吗？以length仅首次打印现象为例

Great question! Let's unpack what's happening here and clarify how Haskell handles memoization.

First, let's recap your code for context:

debug = flip Debug.Trace.trace
foo = [1,2,3]
myRandom :: [a] -> IO Int
myRandom x = let lx = Prelude.length x in System.Random.randomRIO (0, lx) `debug` show lx
test = myRandom foo

Why You See Only One Print, But Multiple Random Numbers #

When you run test multiple times:

• The randomRIO call generates a new random number every time because it's an IO action—IO actions are designed to produce side effects (like generating randomness) and are never memoized. Each execution runs the action from scratch.
• The show lx (and thus the length x calculation) only prints once because lx is a pure expression that gets shared (memoized) across calls.

Does Haskell Memoize All Functions by Default? #

No—Haskell does not memoize all functions. Instead, it memoizes shared pure expressions. Here's the key mechanism:

1. Pure vs. Impure Expressions

• Pure expressions (like length foo, 1 + 2, or [1,2,3]) have no side effects and return the same result every time they're evaluated. Haskell automatically shares (caches) the result of these expressions once they're computed.
• Impure expressions (like IO actions, ST actions, or functions using unsafe side effects) are not memoized. Their execution depends on runtime context, and re-running them can produce different results or side effects.

2. Lazy Evaluation and Sharing

Haskell uses lazy evaluation: expressions are only computed when their value is needed. When a pure expression is computed, Haskell replaces the original "unevaluated thunk" with its final result. Any subsequent references to that expression will use the cached result instead of re-computing it.

In your code:

• foo is a top-level pure binding. Once it's evaluated (when length x needs it), its value is cached for the entire program runtime.
• lx = length x refers to foo, so when lx is first needed (to print via debug), length foo computes to 3. This 3 is then cached—every future call to myRandom foo reuses this cached value instead of recalculating length foo.

3. When Memoization Doesn't Happen

Memoization only applies when the same pure expression is referenced multiple times. If you change your code to pass a new expression each time (even if it has the same value), the calculation will run again:

-- This will print 3 every time you run testNew
testNew = myRandom [1,2,3]

Here, [1,2,3] is a new expression each time testNew is called—there's no shared binding, so length x is recalculated on every call.

Summary #

Haskell's memoization is tied to shared pure values, not functions themselves:

• Pure expressions bound to names (like foo or lx) are cached once evaluated.
• Impure actions (like randomRIO) are never cached—they run from scratch each time.
• Memoization depends on whether the same expression is reused, not just whether the function is called multiple times.

内容的提问来源于stack exchange，提问作者Michiel Borkent