Reputation: 865
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.
Upvotes: 2
Views: 339
Reputation: 28539
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.
Upvotes: 3
Reputation: 8448
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.
Upvotes: 0
Reputation: 93172
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.
Upvotes: 4
Reputation: 185871
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
Upvotes: 5