7

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?

Improve this question
8
  • Try combining sqrt with other functions, like fromIntegral and floor, to get a square root function of the right type. Commented Sep 22, 2011 at 18:08
  • The code given doesn't seem to work--I'm guessing it's just transcription errors formatting it for SO, since you said it worked otherwise, but (tail phi $ reverse smallprimes) doesn't seem to make sense, nor does the LT case in minus. Commented Sep 22, 2011 at 18:18
  • Sorry, I made a transcription error. Try it now. I just realied if I changed the (<=x) in the argument of takeWhile to (<= (floor x)) that it now works ok. Commented Sep 22, 2011 at 18:31
  • As it stands and assuming a $ between tailand phi this is indeed a strange thing. Even if the argumet to primes is floating point, there is no way this argument carries over to phi. So I have doubts the code is really the one you compiled? Commented Sep 22, 2011 at 18:48
  • Yep -- usually one or two well placed conversion functions are all you need -- the trick is where :-) Thanks for the link to the paper also -- looks interesting, and lazy recursive sieving type algorithms are extremely nice in Haskell. Commented Sep 22, 2011 at 20:37

2 Answers 2

Reset to default
6

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

interested in getting the link to the Haskell-Wiki in there? I think it puts value to the answer and I can delete my almost redundant answer this way ... ?
Thanks. It fromIntegral that I was missing. But I'd really like to allow an argument of primes to be a real (i.e. Floating) since that's a typical thing to do in Number Theory. I tried changing (x < 2) to ((ceiling x) < 2) thinking that that might do it, but I still get floating point answers.
It's true there's no automatic conversion between all numeric types, but in practice you can achieve the effect on a few types. You can define a multi-parameter type class, which can run all of the desired operations (+), (-), etc. on numbers of different types. (This was in some classic paper, maybe on associated types? I forget, sorry.)
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 ...

Improve this answer

6 Comments

Actually I tried floor i.e. I wrote, i.e. I wrote (floor sqrt x) instead of sqrt x but that didn't work either -- Haskell refused to compile it.
Well actually floor is right, since I meant primes x to return { p prime : p <= x}
@VictorMiller: I'm not sure if it will fit with your algorithm, but a common trick is to stick with integers and just square p instead of taking the square root of x.
@Victor Miller: If you wrote floor sqrt x literally then the error you probably got was because this parses as (floor sqrt) x. Whitespace-separated identifiers are left-associative function application with higher precedence than anything other than built-in syntax.
Oh, and note that following @hammar's suggestion about squared values instead of square roots not only avoids conversions, it avoids loss of precision--Integer is an arbitrary-sized integer type, whereas floating point types are the usual limited-precision deal. In this particular case, though, I suppose you probably won't be exceeding the range of values that Double can express exactly...
|

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.