如何编写带条件过滤的Haskell递归列表元素组合函数

首先，你的原代码只生成了两个列表对位元素的元组（比如(1,5),(2,6),(3,7)），并没有遍历所有可能的笛卡尔积组合，同时也缺少条件过滤的参数。我们可以从以下两个方向修正：

1. 修正类型签名 #

需要新增一个条件函数参数，类型签名应该改为：

combine :: [a] -> [b] -> (a -> b -> Bool) -> [(a, b)]

这个签名明确了函数接收两个列表，以及一个判断a和b是否满足条件的函数，最终返回符合条件的元组列表。

2. 递归实现逻辑 #

核心思路是：对第一个列表的每个元素，遍历第二个列表的所有元素生成配对，过滤出满足条件的元组；再递归处理第一个列表剩余的元素，将两部分结果拼接。

方式一：用列表推导式简化实现 #

列表推导式可以快速生成笛卡尔积并过滤，代码更简洁：

combine :: [a] -> [b] -> (a -> b -> Bool) -> [(a, b)]
combine [] _ _ = []
combine (x:xs) ys cond = 
    -- 生成当前x与ys中所有满足条件的配对
    [ (x, y) | y <- ys, cond x y ] 
    -- 拼接剩余元素的递归结果
    ++ combine xs ys cond

方式二：纯递归实现（不用列表推导） #

如果希望完全用递归逻辑实现过滤和遍历，可以写一个辅助函数处理单个元素与第二个列表的配对：

combine :: [a] -> [b] -> (a -> b -> Bool) -> [(a, b)]
combine [] _ _ = []
combine (x:xs) ys cond = combineWithX x ys cond ++ combine xs ys cond
  where
    -- 辅助函数：处理单个x与ys的所有配对，过滤满足条件的
    combineWithX :: a -> [b] -> (a -> b -> Bool) -> [(a, b)]
    combineWithX _ [] _ = []
    combineWithX x (y:ys) cond
        | cond x y  = (x, y) : combineWithX x ys cond
        | otherwise = combineWithX x ys cond

验证示例 #

调用combine [1,2,3] [5,6,7] (\a b -> a+b > 7)，会返回你需要的结果：

[(1,7),(2,6),(2,7),(3,5),(3,6),(3,7)]

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