# [Haskell-cafe] CPS and the product function

michael rice nowgate at yahoo.com
Mon Apr 20 11:28:08 EDT 2009

```This also seems to work:

myprod l = prod l id
where
prod [] k = k 1
prod (x:xs) k = if x == 0 then 0 else prod xs (\ z -> k (x * z))

[1 of 1] Compiling Main             ( prod.hs, interpreted )
*Main Data.List> myprod [1,2,3,4,5,0,6,7,8,9]
0
*Main Data.List> myprod [1,2,3,4,5]
120
*Main Data.List> myprod [0..]
0
*Main Data.List>

Michael

--- On Mon, 4/20/09, Tillmann Rendel <rendel at cs.au.dk> wrote:

From: Tillmann Rendel <rendel at cs.au.dk>
Subject: Re: [Haskell-cafe] CPS and the product function
Date: Monday, April 20, 2009, 11:07 AM

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

_______________________________________________