Haskell "No instance for" type error in simple code

Question

I am a really big noob to Haskell.

I have this code:

4 sieve n i = if i < n
5             then
6                 do {
7                  innerSieve n;
8                  sieve n (i + 1);
9                 }
10             else -1
11 
12 innerSieve n = return n
13 
14 --innerSieve n i j = [x | x <- [i..n], x `mod` j == 0]

and I have this error:

[1 of 1] Compiling Main             ( sieve.hs, interpreted )
Ok, modules loaded: Main.
*Main> sieve 10 2

<interactive>:1:1:
No instance for (Num (m0 b0))
  arising from a use of `sieve'
Possible fix: add an instance declaration for (Num (m0 b0))
In the expression: sieve 10 2
In an equation for `it': it = sieve 10 2
*Main> 

I've been banging my head against a wall trying to understand what it means by "No instance for (Num (m0 b0))." What in the world is a m0 b0?

I thought this might help:

*Main> :t sieve
sieve :: (Ord a, Num a, Num (m b), Monad m) => a -> a -> m b
*Main> 

EDIT: I am trying to recreate the sieve of erastothenes by making a recursive function with a list comprehension, basically. I also want to -understand- everything in the code.

Answer 1

As others have said, you almost certainly dont want to use a do block in your code where you do. do is for Monads and should be avoided when learning Haskell, and is probably inappropriate since the only Monad here is [] which would ignore any definition of innerSieve. Haskell code describes values and types in terms of other values and types. Haskell programs dont tell the computer what to do, they tell it what is. This is a radical way of thinking, but a very powerful one. do notation is a special syntax for handling monads which are a special kind of value that can be used to encode computations (including imperative computations and state transitions) cleanly and efficiently, but it requires a broad understanding of Haskell to use well.

My advice to Haskell newbies is "Avoid monads and do notation until you have mastered: recursion, higher order functions, and typeclasses. You dont need do to test your programs (use GHCi), so learn the real functional way of thinking. Try to program such that your programs dont do anything!"

So, how would you go about writing a sieve of Eratosthenes in Haskell? There are many elegant ways. Warning: spoilers ahead. If you want to do this by yourself stop reading

You have commented out:

innerSieve n i j = [x | x <- [i..n], x `mod` j == 0]

I'm not sure what the point of n and i are here. It would be more elegant to write

innerSieve j ls = [x | x <- ls, x `mod` j == 0]

which has the type

innerSieve :: Integral x => x -> [x] -> [x]

so, in other words, it takes a list a value of some type x such that that type can be treated like an integer, and returns all the integral multiples of the original value.

You could use this to write the sieve of Eratosthenes, but a better way would be to get all the values that are not multiples. The reason is that, then you can just stack a bunch of these together to produce your full prime sieve

innerSieve j ls = [x | x <- ls, x `mod` j /= 0]

Here the /= is Haskell's way of saying "not equal". Cool, so lets build a prime sieve out of this

sieve (x:xs) = x : sieve (innerSieve x xs)
sieve [] = []

What does this say? well it takes a list of numbers, and gives you back a new list consisting of the first of those numbers, and the sieve applied to the rest of those numbers except for those that are multiples of the first one. The (x:xs) is a pattern that matches any list other than the empty list, binding x with the head of the list, and xs with the tail of the list. [] is a pattern that matches any empty list.

Finally, you can define the infinite list of all primes

primes = sieve [2..]

The expression [2..] generates the list 2,3,4,5,6,7,etc going on forever. Looks scary (infinite lists), but is okay because of Haskell's famed lazy evaluation. To get the nth prime you can say:

nthPrime n = primes !! (n - 1)

which just indexes into the list of primes. Haskell will only compute the minimum needed to return the result, so this function will terminate even though primes is infinitely long

or to get all the primes up to a number

primesUpToN n = take n primes

so, your entire code base ends up being:

sieve [] = []
sieve (x:xs) = x : sieve (innerSieve x xs) where
   innerSieve j ls = [x | x <- ls, x `mod` j /= 0]

primes = sieve [2..]

nthPrime n = primes !! (n - 1)

primesUpToN n = take n primes

This isn't really the sieve of Eratosthenes, since you aren't "marking off" values. But, this sieve is actually "better" insofar as it is both faster and defines the set of all primes, rather than those up to a number. It is not how you should ever actually go about generating primes, but in 6 lines of code (most of which are unnecessary), it is hard to argue that mutation or looping makes things simpler.

Answer 2

Not only does this give a type error:

do {
   innerSieve n;
   sieve n (i + 1);
   }

But it has the exact same value as

do {
   sieve n (i + 1);
   }

You have called a function "innerSeive", but then not done anything with the value.
If you would like to compute a value and then use the value in the next operation, use the (>>=) operator (sugared as let x = innerseive n; f2 n; within a do block).
However, for these mathematical functions, stay far, far away from do, let, (>>=), etc.

Answer 3

Haskell is a functional language. This especially means, that you don't tell the compiler Do A then do B but rather calculate A – You don't tell the compiler in what order to do things, rather you tell it what you want to know. You can think of that as having only one (return) statement. Thus, you need to rewrite your code to fit to this paradigma.

The do statement is for a special construct called monad that essentially allows stateful actions (such as printing to the screen) in a consistent manners. You don't need it.

As the others already showed you, you can do something like this. The pipe (|) is called pattern guard and essentially works like an If-then-else:

sieve n i | i < n     = --result if condition is met
          | otherwise = -1

Remember that you can't change the values of variables. You may need to rewrite your innerSieve to return something.

Answer 4

Your inner do block has a monadic type. This makes the entire result of sieve have a monadic type of (Monad m) => m b. The else branch of your if statement returns -1, so we know it also has a numeric type. This makes the result of your function (Num (m b), Monad m) => m b. This is very clearly wrong.

I can't figure out what your function is trying to accomplish, so I'm not sure where exactly you went wrong. I would recommend writing explicit type annotations on your functions, to express exactly what you're expecting each function to do. That will, at a minimum, give you better error messages, because instead of saying that the inferred type doesn't make sense, it can point you to exactly what expression doesn't match the explicit type.

BTW, you might find the if statement is better expressed as

sieve n i
    | i < n     = -- contents of the then block
    | otherwise = -1