Instance declaration in Haskell

Question

I have these two functions:

primes = sieve [2..] 
    where
        sieve (p:xs) = p : sieve [x|x <- xs, x `mod` p > 0]
isPrime number = number /= 1 && null [x | x <- takeWhile (\x -> x < (ceiling . sqrt) number) primes, mod number x == 0]

The thing is that when I'm trying to load module which contains those functions, I see following error message:

[2 of 2] Compiling Main             ( euler37.hs, interpreted )

euler37.hs:6:70:
No instance for (RealFrac Int)
  arising from a use of `ceiling'
Possible fix: add an instance declaration for (RealFrac Int)
In the first argument of `(.)', namely `ceiling'
In the expression: ceiling . sqrt
In the second argument of `(<)', namely `(ceiling . sqrt) number'

euler37.hs:6:80:
No instance for (Floating Int)
  arising from a use of `sqrt'
Possible fix: add an instance declaration for (Floating Int)
In the second argument of `(.)', namely `sqrt'
In the expression: ceiling . sqrt
In the second argument of `(<)', namely `(ceiling . sqrt) number'

I really can't understand what's the problem, because when I'm trying to make a small function from piece of code, which, as far as I understand, cause these errors, right in ghci, like let f number x = x < (ceiling . sqrt) number I don't see any error messages.

For the love of all that's holy, please don't use that algorithm to generate a list of primes. It's horribly, horribly bad. Yes, it's cute for its conciseness, but it should never be mentioned without a big fat warning Don not use this. Ever! — Daniel Fischer
– Daniel Fischer, Commented Feb 2, 2012 at 15:16
@Will For me that's slightly slower than the 'primes' package on 7.2.2 - more importantly, it eats memory on 7.2.2. The O'Neill sieve is about twice as fast in the region of 10^8 (scales a bit better than 'primes'), 'arithmoi/Heap' about 1.5 times as fast as O'Neill, the segmented Eratosthenes sieve using arrays about 16 times faster than O'Neill, scales better yet, at 10^9 the quotient is about 22. If you want speed and small memory usage, there's no way (yet) around mutable arrays. — Daniel Fischer
– Daniel Fischer, Commented Feb 2, 2012 at 23:34
@Will The point was that performance characteristics differ with OS and compiler and to provide additional data points. Since ideone's 6.8.2 is ancient (really, 6.10 is obsolete, 6.12 at the obsolescent/obsolete boundary, it's like using gcc-3.1), its characteristics are less relevant for the average user than ghc-7 characteristics. The most important thing was that the old attempts to prevent unwanted sharing now apparently fail, which is rather relevant, I'd say (and slightly disappointing, considering that getting the tree-fold to be a good memory citizen wasn't trivial). — Daniel Fischer
– Daniel Fischer, Commented Feb 3, 2012 at 13:28
@Will In the specific case you linked, if you use an unboxed array (UArray Int Bool), GHC does figure it out and it doesn't do too badly (much better than priority queue or treefold for a while) - I tried 6.12.3 and 7.2.2. It's of course much slower than a segmented sieve that fits into the L2 cache (and cache locality is why PQ and TF seemingly scale better than a monolithic sieve once you get to large ranges), and that transformation would be really hard for a compiler :) — Daniel Fischer
– Daniel Fischer, Commented Feb 3, 2012 at 14:58

ehird · Accepted Answer · 2012-02-02 15:04:04Z

The problem is that primes is a list of Integers (due to your use of mod), but sqrt operates on floating-point numbers. If you do x < (ceiling . sqrt . fromIntegral) number, then it'll work fine. fromIntegral just converts an integral number into any other numeric type:

fromIntegral :: (Integral a, Num b) => a -> b

In this case, since you don't specify any specific floating-point type to convert to, it'll default to using Double values to compute the square root. You could specify another type by changing fromIntegral to something like (fromIntegral :: Integer -> Float).

The reason you don't see this error in GHCi is because your conditional is fine; it just works on different types to the ones you're using here. Just verifying that a piece of code is correct in isolation isn't enough; for it to pass the type checker, it has to make sense in context too.

You might want to consider using an integer square root algorithm for accuracy.

Collectives™ on Stack Overflow

Instance declaration in Haskell

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related