如何在Haskell递归函数中仅单次调用外部列表生成函数

你原有代码存在两个基础问题：

• 语法逻辑错误：递归分支中变量n重复定义（既作为入参又存储生成的列表），且函数声明的返回类型[Integer]和实际返回的数值类型不匹配
• 性能缺陷：列表生成逻辑放在递归分支的where子句中时，每一次递归调用都会重新执行列表生成逻辑，造成不必要的性能损耗

正确实现方式 #

核心思路是使用外层包装+内部递归辅助函数的结构，仅在外层调用一次列表生成函数，整个递归过程复用同一个预生成的列表：

makeList :: Int -> [Integer]
makeList n = map (^2) [0..n]

recFunc :: Int -> Integer
recFunc n = go n
  where
    -- 列表仅在调用recFunc时生成一次，所有递归调用共享该列表
    lst = makeList n
    -- 内部辅助函数实现递归逻辑，仅传递变化的计数参数
    go 0 = 1
    go k = go (k - 1) + 2 * (lst !! k)

可选优化提示 #

列表的!!索引访问复杂度为O(k)，如果你的使用场景中列表长度大、递归深度高，可以替换为Data.Array或Data.Vector等支持O(1)随机访问的容器，进一步提升运行效率。

内容的提问来源于stack exchange，提问作者Niek van de Wouw