如何在Haskell中实现返回排序无限汉明序列的avalanche函数

原有代码的问题 #

• iterate的映射函数逻辑错误：你写的\x -> 3 ^ x会把前一次的输出作为指数，实际得到的序列是[1, 3^1=3, 3^3=27, 3^27,...]，完全不是3的幂序列，正确的3的幂序列应该用iterate (*3) 1生成。
• 三个单底数幂的列表拼接后只有单独的3/5/7的幂，缺少3*5=15这类不同底数相乘的组合，无法覆盖所有i/j/k的取值。
• sort无法作用于无限列表：Haskell的sort需要先完整遍历输入列表才能输出排序结果，无限列表会导致程序永久阻塞。

正确实现思路 #

这是经典的无限有序汉明序列生成问题，利用Haskell的惰性求值特性可以很优雅的实现：

1. 序列的第一个元素固定为1（对应i=j=k=0的情况）
2. 序列中所有元素分别乘3、乘5、乘7得到的三个新的有序无限列表，包含了所有符合规则的后续元素
3. 合并这三个有序列表，同时去除重复值，就能得到完整的升序无限序列

实现代码 #

首先写两个有序无限列表的合并函数，自动去重：

merge :: Ord a => [a] -> [a] -> [a]
merge xs [] = xs
merge [] ys = ys
merge (x:xs) (y:ys)
    | x < y = x : merge xs (y:ys)
    | x > y = y : merge (x:xs) ys
    | otherwise = x : merge xs ys -- 相等时只保留一个，实现去重

然后实现avalanche函数：

avalanche :: [Integer]
avalanche = 1 : merge (map (*3) avalanche) (merge (map (*5) avalanche) (map (*7) avalanche))

测试验证 #

在ghci中执行输出符合预期：

ghci> take 10 avalanche
[1,3,5,7,9,15,21,25,27,35]

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