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

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

Answer 2

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

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')]]

希望有帮助。