[Haskell-cafe] Re: computing lists of pairs
Christian.Maeder at dfki.de
Fri Dec 4 10:48:25 EST 2009
Luke Palmer schrieb:
>> allPossibilities :: [[a]] -> [[a]]
>> allPossibilities  = []
>> allPossibilities (l:ls) = [ x : xs | x <- l, xs <- allPossibilities ls]
> I am confused. This is exactly sequence. How is this a faster
> version? Other than maybe avoiding some dictionary-passing?
I suppose, dictionary-passing is really the reason for slower code.
> Incidentally there is a "better" version of sequence for finding
> products of lists:
> allPossibilities :: [[a]] -> [[a]]
> allPossibilities  = []
> allPossibilities (l:ls) = [ x : xs | xs <- allPossibilites ls, x <- l ]
I cannot really observe a speed up, with this version, but there are
probably examples where any version is faster than the other.
> Or, the general form (I don't know of a use other than for lists, however):
"Maybe" should be another useful instance.
> sequence' :: Applicative f => [f a] -> f [a]
> sequence'  = pure 
> sequence' (x:xs) = liftA2 (flip (:)) xs x
> The difference is that it binds the tail of the list first, so the
> generated tails are shared. This means less consing, less GC strain,
> and a lot less memory usage if you store them.
This argument it too complicated for me.
> Mind, the answers come out in a different order.
More information about the Haskell-Cafe