Replacing explicit recursion with higher-order functions

Question

I have the following code, which is designed to take a list of a's , and list of b's, and return all pairings [(a, b)], such that

• Each a and each b only appears once in each pairing.
• Each pair (a, b) meets some condition cond, i.e. cond :: a -> b -> Bool.

For example, the result for the lists [1, 2] [x,y,z] should be

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

Here is some (somewhat abstracted) code that that does the job with explicit recursion, but I'd like to replace it with a fold or something similar. Any tips?

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

From what I can comprehend from your explanation is you want to filter based on some condition on the product of two list. It is easy to take product of lists using list comprehension and then the filter function will reduce the product to only pairs satisfying the given condition

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

[Update according to edit]

This produces the list like you want (hopefully)

bar :: [a] -> [b] -> [[(a,b)]]
bar xs ys = map (zip xs) $ permutations ys

To filter on the given condition

biz :: (a -> b -> Bool) -> [[(a,b)]] -> [[(a,b)]]
biz = map . filter . uncurry