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 <nowg...@yahoo.com> wrote: From: michael rice <nowg...@yahoo.com> Subject: Re: [Haskell-cafe] CPS and the product function To: haskell-cafe@haskell.org, "Tillmann Rendel" <ren...@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 <ren...@cs.au.dk> wrote: From: Tillmann Rendel <ren...@cs.au.dk> Subject: Re: [Haskell-cafe] CPS and the product function To: haskell-cafe@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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -----Inline Attachment Follows----- _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe