CODEWITHSUNDEEP
haskellrecursion
user1604015
user1604015

Reputation: 415

Replacing explicit recursion with higher-order functions

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

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]

Upvotes: 5

Views: 800

Answers (2)

Aadit M Shah
Aadit M Shah

Reputation: 74234

You can use a foldr to refactor your code as follows:

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

Note that the edge case is someFn _ [] _ = [[]] which is in accordance with the type definition of the function someFn :: (a -> b -> Bool) -> [a] -> [b] -> [[(a,b)]].

You may use someFn as follows:

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

Hope that helps.

Upvotes: 0

Satvik
Satvik

Reputation: 11218

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

Upvotes: 5

Related Questions