Haskell生成偶数及对应前缀和元组列表的代码问题咨询

原代码问题点 #

• 缺失核心过滤逻辑：既没有实现n mod 2 = 0的偶数筛选，n的取值从1开始，漏掉了要求的初始元组(0,0)
• 列表推导逻辑错误：推导式中写s <- sumUntilN x会对每个n遍历整个求和列表生成笛卡尔积，无法实现n和对应求和值的一一绑定
• 求和实现效率极差：递归中每次都用++拼接列表，还重复调用sum[1..n]做全量区间求和，完全没有复用之前的计算结果
• 取值逻辑错误：用take x截取前x个元素，既不符合0到x闭区间的取值范围要求，也和偶数步长下的元素总数不匹配

符合Haskell惯用写法的实现 #

最简洁的实现直接利用等差数列求和公式（1到n的和为n*(n+1)/2），配合步长为2的列表生成式直接输出结果：

genEvenSumTuples :: Int -> [(Int, Int)]
genEvenSumTuples maxN = [(n, n * (n + 1) `div` 2) | n <- [0, 2 .. maxN]]

调用genEvenSumTuples 100即可直接得到预期输出：[(0,0),(2,3),(4,10),...,(100,5050)]。

如果想体现Haskell惰性求值的特性，不依赖数学公式，通过递推生成所有求和值，可以用递归惰性列表的写法：

genEvenSumTuplesLazy :: Int -> [(Int, Int)]
genEvenSumTuplesLazy maxN = filter (\(n, _) -> even n) $ zip [0..maxN] sumSeries
  where
    -- 惰性生成从n=0开始的sum(1..n)序列，每个值仅在前一个值基础上做一次加法
    sumSeries = 0 : zipWith (+) sumSeries [1..]

运行时复杂度说明 #

• 原代码复杂度：sumUntilN递归过程中每次列表拼接需要O(k)时间（k为当前列表长度），同时每次递归都执行O(n)的全区间求和，单生成求和列表的时间复杂度就达到O(n²)；再加上列表推导生成笛卡尔积的开销，整体时间复杂度达到O(n³)，存在大量冗余计算。
• 公式实现版本复杂度：每个元组的求和值通过O(1)算术运算得到，配合步长为2的列表遍历，整体时间复杂度为O(n)；在惰性求值场景下如果只消费列表前k个元素，仅需要计算k个元素的值，不需要生成整个列表，空间开销可以低至O(1)。
• 惰性递推版本复杂度：求和序列每个值仅在前一个结果基础上做一次加法，单次遍历即可完成元组组装和偶数过滤，整体时间复杂度为O(n)；完全符合惰性求值的特性，不会提前计算未被消费的元素，即使传入非常大的maxN值，仅取前几个元素时也不会产生额外计算开销。

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