haskell - 用高阶函数代替显式递归

Question

我有以下代码，旨在获取 a 的列表的，以及 b 的列表's，并返回所有配对 [(a, b)]，使得

每个a和每个 b每个配对只出现一次。

每对(a, b)满足某些条件 cond ，即 cond :: a -> b -> Bool .

例如，列表 [1, 2] [x,y,z] 的结果应该是

[[(1, x), (2, y)]
 [(1, x), (2, z)]
 [(1, y), (2, x)]
 [(1, y), (2, z)]
 [(1, z), (2, x)]
 [(1, z), (2, y)]]

这是一些(有些抽象的)代码，它们通过显式递归完成工作，但我想用折叠或类似的东西替换它。有小费吗？

someFn :: [a] -> [b] -> [ [(a, b)] ]
someFn [] _ = []
someFn (a : as) bs = [ [(a,b)] ++ rest | b <- bs, rest <- someFn as (bs \\ [b]), cond a b]

Answer 1

从您的解释中我可以理解的是，您想根据两个列表的乘积的某些条件进行过滤。使用列表理解来获取列表的乘积很容易，然后过滤器函数会将乘积减少到仅满足给定条件的对

foo :: [a] -> [b] -> (a -> b -> Bool)-> [(a,b)]
foo x y with = filter (uncurry with) [(a,b) | a <- x, b <- y] 

[根据编辑更新]

这会产生您想要的列表(希望如此)

bar :: [a] -> [b] -> [[(a,b)]]
bar xs ys = map (zip xs) $ permutations ys

根据给定条件过滤

biz :: (a -> b -> Bool) -> [[(a,b)]] -> [[(a,b)]]
biz = map . filter . uncurry