[Haskell-cafe] CPS and the product function
rendel at cs.au.dk
Mon Apr 20 11:07:29 EDT 2009
michael rice wrote:
> I've been looking at CPS in Haskell and wondering how many multiplications the product function performs if it encounters a zero somewhere in the input list. Zero?
> Does anyone know the definition of the product function?
You can use Hoogle  to search for product . The documentation page
 has a link to the source code .
Depending on some flag, it is either
product = foldl (*) 1
or an explicit loop with an accumulator. That means that even for a
non-strict (*), the whole input list would be processed before a result
could be returned.
> Does anyone know how to define it to avoid that?
You have to define a multiplication function which is non-strict in the
second argument if the first is 0.
mult 0 b = 0
mult a b = a * b
Now we can foldr this multiplication function over a list, and
evaluation will stop at the first 0.
foldr mult 1 ([1..100] ++ [0 ..])
However, this solution seems not to run in constant space. We can write
it with a strict accumulator to avoid this problem:
product = product' 1 where
product' acc  = acc
product' acc (0 : xs) = 0
product' acc (x : xs) = (product' $! acc * x) xs
More information about the Haskell-Cafe