为什么Haskell中基于通用递归的memo记忆化函数未实现性能提升？

你实现的fib函数没有遵循开放递归（open recursion）的约定，没有使用传入的递归参数f，导致记忆化逻辑完全没有被触发，所有递归调用依然走的是无缓存的原生递归路径。

具体拆解分析 #

• 你的fib实现存在的问题：
  你写的fib逻辑为：

  fib f 0 = 1
  fib f 1 = 1
  fib f n = fib f (n - 1) + fib f (n - 2)
  

  这里递归步骤硬编码了对fib f的调用，完全没有用到传入的参数f。memo函数中传给f的fList !!查表逻辑，在fib的递归过程中完全没有被调用，等于记忆化的钩子完全失效，运行逻辑和直接用fix fib的无缓存版本没有任何区别，所以耗时几乎一致。
• 正确的开放递归风格fib写法：
  要让通用memo函数生效，需要把递归的控制权交给传入的f参数，修改后的fib如下：

  fib f 0 = 1
  fib f 1 = 1
  fib f n = f (n - 1) + f (n - 2) -- 递归调用传入的f，而不是直接调用fib
  

  修改后再运行memo fib 30，耗时就会和fibMemoDirect一致。
• fibMemoDirect性能正常的原因：
  该实现的递归步骤直接绑定到了记忆化列表fibList的查找逻辑，相当于手动完成了开放递归的绑定，所有子问题的结果都会被缓存复用，所以运行速度极快。

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