[Haskell-cafe] Efficiency question

[Bertram Felgenhauer]

Evil Bro wrote:
> 
> > Counting can be done elegantly by 'filter' and 'length':
> I figured out the following code after posting:
> 
> solve d = length [(y,x) | x <- [2..d], y <- [1..(x-1)], gcd x y == 1]
> main = print (solve 1000000)
> 
> However when running it, it gave an answer of -1255316543. How on earth can
> a length be negative?

Yu got an integer overflow - length returns an Int. You can use
Data.List.genericLength  instead, however, which can return its
result in any Num instance. (In particular, Integer works)

> import Data.List
> 
> solve :: Integer -> Integer
> solve d = genericLength [(y,x) | x <- [2..d], y <- [1..(x-1)], gcd x y == 1]
> 
> main = print (solve 1000000)

(Note: untested.)

HTH,

Bertram