Type declaration in Haskell

Question

I just started learning Haskell. I decided to set myself a goal of implementing an old algorithm of mine http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.79.7006&rep=rep1&type=pdf

As a start I wrote the following code

phi [] = [1..]
phi (p:pl) = (phi pl) `minus` (map (p*) $ phi pl)
primes x
       | x < 2 = []
       | otherwise = smallprimes ++ (takeWhile (<=x) $tail $ phi $ reverse smallprimes)
     where  smallprimes = primes $ sqrt x

minus (x:xs) (y:ys) = case (compare x y) of
         LT -> x  :    minus xs (y:ys)
         EQ ->         minus xs    ys
         GT ->         minus (x:xs) ys
minus xs        _   = xs

This functions as expected, except that the list of primes comes as floating point! A little thought told me that since the signature of sqrt is

sqrt :: (Floating a) => a -> a

the Haskell compiler has decided that primes is returning a list of floats. However, when I tried to tell it that

phi :: [Integer] -> [Integer]

which is what I want, the compiler has a problem:

No instance for (Floating Integer)
  arising from a use of `sqrt` at ...

So how do I signify the phi takes as input a list of integers and as output produces an infinite list of Integers?

Answer 1

The problem in your code is, that sqrt expects a floating point number and returns the same. You have to use a wrapper that converts the type to make it work. (That's essentially, what the error message says):

smallprimes = primes . ceiling . sqrt . fromIntegral $ x

Haskell has no automatic conversion between different numeric types, as this is not possible with the type system Haskell has.

Answer 2

take a look at that: Converting numbers

ceiling should too the trick (as FUZxxl pointed out allready)

IMHO the difficult part here is that the languages we are used to cast types by pointing to your target - Haskell switches the logic in a mind-bending way here ...