Haskell自定义多初始值Hamming序列生成问题求助

首先保留标准实现中的merge函数，它负责合并两个有序列表并自动去重：

merge :: Ord a => [a] -> [a] -> [a] 
merge [] ys = ys
merge xs [] = xs
merge (x : xs) (y : ys) 
    | x == y    = x : merge xs ys
    | x < y     = x : merge xs (y : ys)
    | otherwise = y : merge (x:xs) ys

正确的自定义实现 #

我们需要利用Haskell的惰性递归，结合输入初始列表的排序去重处理，来生成完整的迭代序列：

import Data.List (sort, nub)

modifiedHamming :: [Integer] -> [Integer]
modifiedHamming initial = hammings
  where
    -- 预处理初始列表：排序并去重，确保输入为有序无重复序列
    sortedUniqueInitial = sort $ nub initial
    -- 递归定义序列：初始列表与自身三个倍数序列的合并结果再合并
    hammings = merge sortedUniqueInitial 
                     (merge (map (*2) hammings) 
                            (merge (map (*3) hammings) 
                                   (map (*5) hammings)))

测试验证 #

调用示例：

main = print $ take 10 (modifiedHamming [10, 30, 50])

输出结果：

[10,20,30,40,50,60,80,90,100,120]

完全符合预期。

错误实现分析 #

1. 第一种实现的问题：
   仅对初始列表进行了一次倍数映射与合并，没有递归迭代生成后续元素（比如20*2=40这类初始元素倍数的倍数），因此序列只能覆盖初始元素的一次倍数范围，无法无限生成后续项。

2. 第二种实现的问题：
   直接将初始列表xs与递归调用自身得到的hammings的倍数序列合并，导致无限递归展开——计算hammings时需要先获取自身的倍数序列，而倍数序列又依赖hammings的元素，最终触发栈溢出。正确的实现是将预处理后的初始列表作为序列的前缀，再与自身的倍数序列合并，利用惰性求值逐步生成后续元素，避免无限递归展开。

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