Haskell对由无限列表组成的列表使用foldr求并集的问题

问题原因 #

你使用的Data.List.union默认优先遍历完第一个参数的所有元素，才会处理第二个参数的元素。当第一个列表是无限列表时，程序永远不会进入第二个列表的处理逻辑，因此只能拿到第一个元素生成的无限列表内容。

解决方案 #

根据你生成的无限列表的特性，可以选择两种适配方案：

方案1：适用于所有生成的无限列表为严格递增的场景（你的示例中pow函数生成的列表符合该要求）

这种场景用有序列表多路合并的方案效率最高，不会出现元素遗漏：

pow :: Integer -> [Integer]
pow n = map (^n) [1, 2..]

-- 对角线枚举无限列表的列表，保证公平覆盖所有子列表的元素
diagonal :: [[a]] -> [a]
diagonal = concat . takeWhile (not . null) . map (map head . reverse) . tail . scanl (flip (:)) []

-- 合并多个严格递增无限列表，返回去重后的递增无限列表
mergeSortedUnique :: [[Integer]] -> [Integer]
mergeSortedUnique = map head . group . sort . diagonal

function :: [Integer] -> [Integer]
function xs = mergeSortedUnique (map pow xs)

测试执行take 10 $ function [2,3]会输出[4,8,9,16,25,27,36,49,64,81]，符合两个列表并集的预期。

方案2：适用于生成的无限列表为无序的通用场景

可以用自定义的公平合并去重函数替换默认的union，该函数每次处理一个元素后交换两个列表的处理顺序，避免卡在单个无限列表上：

fairUnion :: Eq a => [a] -> [a] -> [a]
fairUnion [] ys = ys
fairUnion xs [] = xs
fairUnion (x:xs) ys = x : fairUnion ys (filter (/= x) xs)

function :: [Integer] -> [Integer]
function xs = foldr fairUnion [] (map pow xs)

优化提示 #

如果你的元素满足Ord约束，使用Set结构缓存已出现的元素代替filter (/=x)的遍历操作，可以大幅提升去重效率。

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