list - 查找列表和谓词的任何可能的键合

Question

我的任务是我想创建一个函数来查找给定列表和谓词的任何可能的“绑定(bind)”，但我找不到正确的解决方案。

ls 的绑定(bind) p 是 bs::[ (a,a) ] 对的列表，使得以下条件成立

1. ls 中的每个元素在 map fst bs 中只出现一次，在 map snd bs 中只出现一次
2. 如果 (x,y) 对出现在 bs 中，则 x 和 y 都必须出现在ls.
3. 如果一对 (x,y) 出现在 bs 中，那么 (y,x) 也出现在 bs.
4. 如果一对 (x,y) 出现在 bs 中，则 x 不等于 y。
5. 如果 (x,y) 对出现在 bs 中，则 p x y 为 True。

此外，我认为对这个问题有用的函数是下面的 findBonding::Eq a => (a -> a -> Bool) -> [a] -> Maybe [(a ,a)] 这样 findBonding p ls 将 p 作为谓词，将 ls 作为整数列表。

例如，findBonding (\x ->\y -> odd(x+y)) [2,3,4,5,6,7] 应该返回 Just [ (2,3),(3,2),(4,5),(5,4),(6,7),(7,6)]

用 ls(列表)的 foldr 声明 findBonding 是个好主意，然后是 p(谓词)是应该声明要查找哪些对的函数，然后循环遍历每两个项目以找到正确的对并将它们作为列表的列表返回。

Answer 1

根据您对“绑定(bind)”的最终定义，这应该可以满足您的要求:

import Data.Maybe

-- > removeEach [1,2,3,4] == [(1,[2,3,4]),(2,[1,3,4]),(3,[1,2,4]),(4,[1,2,3])]
removeEach :: [a] -> [(a,[a])]
removeEach [] = []
removeEach (x:xs) = (x,xs):map (fmap (x:)) (removeEach xs)

-- > findBonding (\x -> \y -> odd(x+y)) [2,3,4,5,6,7] == Just [(2,3),(3,2),(4,5),(5,4),(6,7),(7,6)]
-- > findBonding (\x -> \y -> even(x+y)) [2,3,4,5,6,7] == Nothing
findBonding :: (a -> a -> Bool) -> [a] -> Maybe [(a,a)]
findBonding f = listToMaybe . go where
  go [] = [[]]
  go (x:xs) = [(x,y):(y,x):xys | (y,ys) <- removeEach xs, f x y && f y x, xys <- go ys]

我创建了辅助函数 removeEach 来为列表中的每个元素提供该元素加上没有它的列表。

findBonding 函数获取列表 x 的头部，然后在列表中找到一个元素 y 使得 f x y 和 f y x 都成立，产生这些对，然后递归列表的其余部分。它使用外部列表作为非确定性 monad，以确保如果任何可能的配对组合有效，它都会找到一个。