Find any possible bondings of a list and predicate

user_17406158 0
Viewed 444

My task is that I want to create a function that finds any possible "bondings" of a given list and a predicate but I can't find the right solution.

a bonding for ls for binary predicate p is a list of pairs bs :: [ (a,a) ] such that the following conditions hold

  1. Every element in ls appears exactly once in map fst bs and exactly once in map snd bs
  2. If a pair (x,y) appears in bs then both x and y must appear in ls.
  3. If a pair (x,y) appears in bs then (y,x) also appears in bs.
  4. If a pair (x,y) appears in bs then x does not equal y.
  5. If a pair (x,y) appears in bs then p x y is True.

Furthermore, the function that I thought it will be useful for this problem is the following findBonding :: Eq a => (a -> a -> Bool) -> [a] -> Maybe [(a,a)] such that findBonding p ls takes p as predicate and ls as a list of integers.

For example, findBonding (\x -> \y -> odd(x+y)) [2,3,4,5,6,7] should return Just [(2,3),(3,2),(4,5),(5,4),(6,7),(7,6)]

Is it a good idea to declare findBonding with foldr of the ls (the list) and then p (the predicate) to be the function that should declare which pairs to find and then to loop over every two items to find the correct pairs and to return them as a list of lists.

predicate list functional-programming haskell
1 Answers

With your final definition of a "bonding", this should do what you want:

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]

I created the helper function removeEach to, for each element in a list, provide that element plus the list without it.

The findBonding function takes the head of the list x, then finds an element y in the list such that f x y and f y x both hold, yields those pairs, and then recurses on the remainder of the list. It uses the outer list as a nondeterminism monad to ensure that if any possible combination of pairings work, it will find one.

user_75090650
Related