[Haskell-cafe] computing lists of pairs

Christian Maeder Christian.Maeder at dfki.de
Wed Dec 2 08:49:21 EST 2009


I've the following small piece of code

pairs :: [a] -> [b] -> [[(a, b)]]
pairs l1 = map (zip l1) . takeKFromN l1

takeKFromN :: [b] -> [a] -> [[a]]
takeKFromN s l = case s of
  [] -> [[]]
  _ : r -> [ a : b | a <- l, b <- takeKFromN r l]

I have a predicate:
  p :: (a, b) -> Bool

and I want to keep only those results of pairs which fulfill
"all p".

I do so currently by "filter (all p) (pairs l1 l2)", but I want to
generate the beginning of this pair lists more efficiently, because the
result list of pairs may become very large, soon:

  length (pairs l1 l2) == length l2 ^ length l1

Any ideas (or other hints) to improve the code?

"pairs" computes all different mappings from all elements of l1 to some
elements of l2. "takeKFromN" computes all possible sequences of length
l1 with elements from l2.

I somehow want to integrate the predicate into the generation.

Cheers Christian

More information about the Haskell-Cafe mailing list