Haskell中fib_mem与fib_mem_arg的记忆化差异及CAF疑问

Hey there! Let's unpack this Haskell memory puzzle step by step—this is a super common gotcha with lazy evaluation and memoization, so it's great you're digging into it.

First, Let's Recap the Two Functions #

Here's the properly memoized version:

fib_mem :: Int -> Integer
fib_mem = (map fib [0..] !!)
where
  fib 0 = 1
  fib 1 = 1
  fib n = fib_mem (n-2) + fib_mem (n-1)

And the non-memoized imposter that looks similar but doesn't work:

fib_mem_arg :: Int -> Integer
fib_mem_arg x = map fib [0..] !! x
where
  fib 0 = 1
  fib 1 = 1
  fib n = fib_mem_arg (n-2) + fib_mem_arg (n-1)

What Does That Bold Statement Mean? #

The line "向函数传入参数会创建新表达式，无法隐式指向之前函数应用的表达式" translates to: "Passing an argument to a function creates a new expression, which can't implicitly reference expressions from previous function applications."

Put simply:
Every time you call fib_mem_arg x, the entire expression map fib [0..] !! x gets rebuilt from scratch—including the infinite list map fib [0..]. Even if you called fib_mem_arg 5 earlier, calling fib_mem_arg 6 won't reuse any of the values you already calculated. Instead, it spins up a brand new list, so all Fibonacci values get recalculated every time they're needed.

A Visual Example with Debug.Trace #

Let's add debug logging to see this in action. First, the non-memoized version:

import Debug.Trace

fib_mem_arg :: Int -> Integer
fib_mem_arg x = trace "👉 Creating NEW map fib [0..] list" $ map fib [0..] !! x
where
  fib 0 = trace "  🧮 Calculating fib 0" 1
  fib 1 = trace "  🧮 Calculating fib 1" 1
  fib n = trace ("  🧮 Calculating fib " ++ show n) $ fib_mem_arg (n-2) + fib_mem_arg (n-1)

If you run fib_mem_arg 2, here's what you'll see (abbreviated):

👉 Creating NEW map fib [0..] list
🧮 Calculating fib 0
👉 Creating NEW map fib [0..] list
🧮 Calculating fib 1
👉 Creating NEW map fib [0..] list
🧮 Calculating fib 0
👉 Creating NEW map fib [0..] list
🧮 Calculating fib 1
👉 Creating NEW map fib [0..] list
🧮 Calculating fib 2
... (this repeats exponentially for larger n, leading to massive slowdown)

Now compare that to the memoized fib_mem with trace:

import Debug.Trace

fib_mem :: Int -> Integer
fib_mem = trace "👉 Creating map fib [0..] ONCE" $ (map fib [0..] !!)
where
  fib 0 = trace "  🧮 Calculating fib 0" 1
  fib 1 = trace "  🧮 Calculating fib 1" 1
  fib n = trace ("  🧮 Calculating fib " ++ show n) $ fib_mem (n-2) + fib_mem (n-1)

Running fib_mem 2 gives:

👉 Creating map fib [0..] ONCE
🧮 Calculating fib 0
🧮 Calculating fib 1
🧮 Calculating fib 2

And if you run fib_mem 3 right after, you'll only see:

🧮 Calculating fib 3

No new list creation—we're reusing the same cached list we created the first time!

Why is fib_mem a Constant Applicative Form (CAF)? #

A CAF (Constant Applicative Form) is essentially a "constant value" (even if it's a function) that doesn't depend on any external variables. It's defined once, and Haskell's runtime caches it for all future uses.

Look at fib_mem's definition:

fib_mem = (map fib [0..] !!)

There's no parameter here—no x or other variable that the right-hand side depends on. This means map fib [0..] is created once when fib_mem is first referenced, and every call to fib_mem n just indexes into this single, cached infinite list. That's why the memoization works!

In contrast, fib_mem_arg x ties the list creation to the parameter x. Every new x triggers a new list, so no caching happens.

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