Haskell实现：生成给定整数列表的升序无限倍数序列

你需要先实现一个合并两个升序无序列表的工具函数，再通过右折叠将多个无限倍数列表合并为最终的升序列表，步骤如下：

1. 实现双有序列表合并函数 #

两个都是升序的无限列表，合并时只需逐个对比头部元素，相等时仅保留一个避免公倍数重复：

merge :: Ord a => [a] -> [a] -> [a]
merge [] ys = ys
merge xs [] = xs
merge (x:xs) (y:ys)
  | x < y     = x : merge xs (y:ys)
  | x > y     = y : merge (x:xs) ys
  | otherwise = x : merge xs ys -- 相等时去重

2. 实现多列表合并的目标函数 #

先用map multiples把输入的整数列表转为多个无限升序倍数列表，再用foldr嵌套调用merge合并所有列表：

import Data.List (nub)

multiples :: Integer -> [Integer]
multiples n = map (*n) [1..]

multiplesList :: [Integer] -> [Integer]
multiplesList ns = foldr merge [] (map multiples validNs)
  where validNs = filter (>0) $ nub ns -- 先过滤非正整数、去重，提升效率

如果不需要提前去重可以去掉nub，merge本身也会处理重复值，只是效率稍低，也可以不用导入Data.List模块

效果验证 #

输入take 10 $ multiplesList [3,5]，得到的输出为：
[3,5,6,9,10,12,15,18,20,21]，和你要求的示例一致。

为什么用foldr不用foldl？ #

因为foldr是右折叠，结构为merge 列表1 (merge 列表2 (merge 列表3 ...))，每次都可以直接拿到最外层的头部元素，适合处理无限列表。如果用左折叠foldl，会一直递归到最内层的空列表，永远无法返回第一个元素，无法处理无限输入。

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