使用高阶函数替换显式递归

Question

我有以下代码，旨在接受一个a的列表和一个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)]]

这里有一些（有点抽象）的代码，使用显式递归实现了功能，但我想用fold或类似的东西来替换它。有什么建议吗？

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

- user1604015

---

每个a和每个b在每个配对中只出现一次 - 嗯，也许是因为英语不是我的母语，但这不是对于任何一对（元组）（a，b）总是显而易见的吗？a最多出现一次，b最多出现一次。 - Ingo

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

我看到你在处理第二个列表中的重复项，但第一个列表呢？ - n. m.

只有一次，但可以是零次，或至少且仅一次？ - JB.

抱歉 - 我添加了一个例子，应该能够澄清事情。 - user1604015

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

- Satvik

---

我对原问题进行了一些编辑，希望能使其更清晰明了。原始输出类型[[(a,b)]]是正确的，并且处理重复问题是必要的。 - user1604015

Answer 2

你可以使用 foldr 来重构你的代码，如下所示：

delete :: Int -> [a] -> [a]
delete index xs = let (ys, _:zs) = splitAt index xs in ys ++ zs

ifoldr :: (Int -> a -> b -> b) -> b -> [a] -> b
ifoldr f acc xs = foldr (\(a, b) c -> f a b c) acc $ zip [0..] xs

someFn :: (a -> b -> Bool) -> [a] -> [b] -> [[(a,b)]]
someFn _ [] _ = [[]]
someFn cond (a:as) bs = ifoldr (\index b acc -> if cond a b
    then concat [map ((a,b):) . someFn cond as $ delete index bs, acc]
    else acc) [] bs

请注意边缘情况是someFn _ [] _ = [[]]，这符合函数someFn :: (a -> b -> Bool) -> [a] -> [b] -> [[(a,b)]]的类型定义。

您可以按以下方式使用someFn:

someFn (\a b -> True) [1,2] "xyz"

-- [[(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 -> case (a,b) of (1,'x') -> False
                              (2,'y') -> False
                              otherwise -> True) [1,2] "xyz"

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

希望这能帮助到你。

- Aadit M Shah