[Haskell-cafe] CPS and the product function
michael rice
nowgate at yahoo.com
Mon Apr 20 16:03:24 EDT 2009
That last definition multiplied zeros coming out of the recursion, but I believe this one is good:
myprod l = prod l id id
where
prod [] k b = k 1
prod (x:xs) k b = if x == 0 then b 0 else prod xs (\ z -> k (x * z)) b
My goal was to use CPS to do it. Did I succeed?
Also, is there another way to do the same thing without passing b through all those recursions? I'm not good enough with Haskell's syntax to see how to do it.
Michael
--- On Mon, 4/20/09, michael rice <nowgate at yahoo.com> wrote:
From: michael rice <nowgate at yahoo.com>
Subject: Re: [Haskell-cafe] CPS and the product function
To: haskell-cafe at haskell.org, "Tillmann Rendel" <rendel at cs.au.dk>
Date: Monday, April 20, 2009, 11:28 AM
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))
*Main Data.List> :load prod
[1 of 1] Compiling Main ( prod.hs, interpreted )
Ok, modules loaded: Main.
*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
To: haskell-cafe at haskell.org
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
[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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe at haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
-----Inline Attachment Follows-----
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe at haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20090420/6c2c5473/attachment.htm
More information about the Haskell-Cafe
mailing list