[Haskell-cafe] computing lists of pairs
Christian Maeder
Christian.Maeder at dfki.de
Wed Dec 2 08:49:21 EST 2009
Wizards,
I've the following small piece of code
\begin{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]
\end{code}
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