Haskell list condition

user_1458041 0
Viewed 167

I have started to learn Haskell yesterday, so you can consider me a complete newbie.

I wanted a list of prime numbers, so I stated:

multiples max reihe = [ x | x <- [reihe*2,reihe * 3..max], x<= max ]
notPrimes max = [ truncate x | x <- concat [ multiples max reihe | reihe <- [2..(max/2)]]]
primes max = [ x | x <- [2..max] , elem x (notPrimes max) ]

The first snippet is a function which returns all multiples of reihe not exceeding max.

The second is a function which returns all non-primes except 1 up to the specified maximum.

The last snippet does not work, and I don't understand why. If I evaluate elem x (notPrimes max) with an arbitrary value of x I get an answer, but this "filter" throws an error:

<interactive>:47:1: error:
* Ambiguous type variable `a0' arising from a use of `print'
  prevents the constraint `(Show a0)' from being solved.
  Probable fix: use a type annotation to specify what `a0' should be.
  These potential instances exist:
    instance Show Ordering -- Defined in `GHC.Show'
    instance Show a => Show (Maybe a) -- Defined in `GHC.Show'
    instance Show Integer -- Defined in `GHC.Show'
    ...plus 23 others
    ...plus 15 instances involving out-of-scope types
    (use -fprint-potential-instances to see them all)
* In a stmt of an interactive GHCi command: print it
ambiguous-type-variable sieve-of-eratosthenes primes filter haskell
1 Answers

The problem is with the use of fractional numbers, induced by the / operator.

As the function truncate converts from some RealFrac type to some Integral type, this equation:

notPrimes max = [ truncate x | x <- concat [ multiples max reihe | reihe <- [2..(max/2)]]

will force argument max to be fractional, and the result of notPrimes to be a list of integral values.

But then, this equation:

primes max = [ x | x <- [2..max] , elem x (notPrimes max) ]

will force x to be fractional like max AND integral like the elements of notPrime max. Remember, Haskell does not do implicit type conversions.

So when you try to actually evaluate something like primes 100, you force the Haskell interpreter to assign actual types to every thing, and things get ugly.

The key ideas are:

  1. do not use fractional numbers in integer problems, unless really necessary
  2. use explicit type signatures as appropriate

Besides, as mentioned in a comment, there is a missing logical negation (an additional not call).

A possible integral-only solution:

$ ghci
GHCi, version 8.8.4: https://www.haskell.org/ghc/  :? for help
 λ> 
 λ> :type (/)
 (/) :: Fractional a => a -> a -> a
 λ> 
 λ> :type div
 div :: Integral a => a -> a -> a
 λ> 
 λ> multiples max reihe = [ x | x <- [reihe*2,reihe * 3..max], x<= max ]
 λ> notPrimes max = [ x | x <- concat [ multiples max reihe | reihe <- [2..(div max 2)]]]
 λ> primes max = [ x | x <- [2..max] , not $ elem x (notPrimes max) ]
 λ> 
 λ> primes (100::Int)
 [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]
 λ>
user_112824040
Related