[Haskell-cafe] computing lists of pairs

[Daniel Fischer]

Am Mittwoch 02 Dezember 2009 14:49:21 schrieb Christian Maeder:
> 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".

takeKFromNWithP :: (a -> b -> Bool) -> [a] -> [b] -> [[b]]
takeKFromNWithP p s l
    = case s of
        (h:t) -> [x:ys | x <- filter (p h) l, ys <- takeKFromNWithP p t l]
        [] -> [[]]

filteredPairs :: (a -> b -> Bool) -> [a] -> [b] -> [[(a,b)]]
filteredPairs p l1 = map (zip l1) . takeKFromNWithP l1

or, in one go:

funkyName :: (a -> b -> Bool) -> [a] -> [b] -> [[(a,b)]]
funkyName p s l
    = case s of
        (h:t) -> [(h,a):ys | a <- filter (p h) l, ys <- funkyName p t l]
        [] -> [[]]
>
> 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
>