用高阶函数替换显式递归

Question

我有以下代码,它被设计为获取a's 的列表,以及's的列表b,并返回所有配对[(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