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:produc... [4] http://haskell.org/ghc/docs/latest/html/libraries/base/src/Data-List.html#pr...