[Haskell-cafe] CPS and the product function

[Tillmann Rendel]

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 [1] to search for product [2]. The documentation page 
[3] has a link to the source code [4].


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

Tillmann

[1] http://www.haskell.org/hoogle/
[2] http://www.haskell.org/hoogle/?hoogle=product
[3] 
http://haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html#v:product
[4] 
http://haskell.org/ghc/docs/latest/html/libraries/base/src/Data-List.html#product