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

我有以下代码，它被设计为采用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)]]

下面是一些（有点抽象）代码，没有工作具有明确递归，但我想用折叠或类似的东西替换它。有小费吗？

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

来源

2013-10-10 user1604015

'[（a，b）]'是成对的列表，所以你的函数返回一串成对列表而不是成对列表。 – duplode

“每个a和每个b只在每次配对中出现一次” - 嗯，这可能是因为英语不是我的第一语言，但这不是平凡的对于任何对（元组）（a，b）都是真的吗？ a最多发生一次，b最多发生一次。 – Ingo

目标不明确。你想用折叠取代这个，还是你想问如何使'someFn'更高的顺序？如果后者，更高的顺序是什么？ 'cond'谓词？ – asm

从我的理解你的解释是你想根据两个列表的产品上的某些条件进行过滤。这是很容易使用列表解析[根据编辑更新]

这将产生清单像你拿名单的产品，然后过滤功能会降低产品只对满足一定条件

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

来源

2013-10-10 16:05:13 Satvik

我已经对原始问题进行了一些编辑，我希望更清楚。原始输出类型[[（a，b）]]是正确的，并且是处理重复问题所必需的。 – user1604015

您可以使用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')]]

希望有所帮助。

来源

2013-10-10 18:26:02

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

回答

相关问题