[Haskell-cafe] Re: computing lists of pairs

[Christian Maeder]

Daniel Fischer schrieb:
> Am Mittwoch 02 Dezember 2009 18:54:51 schrieb Christian Maeder:
>> Daniel Fischer schrieb:
>>> However, according to a couple of tests, the "funkyName" version is
>>> somewhat faster and allocates less.
>> My timing tests showed that your fpairs version is fastest.

Interesting. Using a faster version of "sequence":

http://www.haskell.org/pipermail/haskell-cafe/2009-November/069491.html

\begin{code}
allPossibilities :: [[a]] -> [[a]]
allPossibilities [] = [[]]
allPossibilities (l:ls) = [ x : xs | x <- l, xs <- allPossibilities ls]

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]
  [] -> [[]]

fpairs :: (a -> b -> Bool) -> [a] -> [b] -> [[(a, b)]]
fpairs p s l =
  allPossibilities [[(a, b) | b <- filter (p a) l] | a <- s]
\end{code}

fpairs and funkyName are about equally fast.

Cheers Christian