99 questions/31 to 41

These are Haskell translations of Ninety Nine Lisp Problems.

If you want to work on one of these, put your name in the block so we know someone's working on it. Then, change n in your block to the appropriate problem number, and fill in the <Problem description>,<example in lisp>,<example in Haskell>,<solution in haskell> and <description of implementation> fields.

Problem 31

Determine whether a given integer number is prime.

Example:
* (is-prime 7)
T

P31> isPrime 7
True

Solution:

isPrime :: Integral a => a -> Bool
isPrime p = all (\n -> p `mod` n /= 0 ) \$ takeWhile (\n -> n*n <= x) [2..]

Well, a natural number p is a prime number iff no natural number n with n >= 2 and n^2 <= p is a divisor of p. That's exactly what is implemented: we take the list of all integral numbers starting with 2 as long as their square is at most p and check that for all these n there is a remainder concerning the division of p by n.

Problem 32

(**) Determine the greatest common divisor of two positive integer numbers.

Use Euclid's algorithm.
Example:
* (gcd 36 63)
9

[myGCD 36 63, myGCD (-3) (-6), myGCD (-3) 6]
[9,3,3]

Solution:

gcd' 0 y = y
gcd' x y = gcd' (y `mod` x) x
myGCD x y | x < 0     = myGCD (-x) y
| y < 0     = myGCD x (-y)
| y < x     = gcd' y x
| otherwise = gcd' x y

The Prelude includes a gcd function, so we have to choose another name for ours. The function gcd' is a straightforward implementation of Euler's algorithm, and myGCD is just a wrapper that makes sure the arguments are positive and in increasing order.

Problem 33

(*) Determine whether two positive integer numbers are coprime. Two numbers are coprime if their greatest common divisor equals 1.

Example:

* (coprime 35 64)
T

* coprime 35 64
True

Solution:

coprime a b = gcd a b == 1

Here we use the prelude function for computing gcd's along with a test of the result's equality to one.

Problem 34

(**) Calculate Euler's totient function phi(m). Euler's so-called totient function phi(m) is defined as the number of positive integers r (1 <= r < m) that are coprime to m. Example: m = 10: r = 1,3,7,9; thus phi(m) = 4. Note the special case: phi(1) = 1.

Example:
* (totient-phi 10)
4
* totient 10
4

Solution:

totient 1 = 1
totient a = length \$ filter (coprime a) [1..a-1]
where coprime a b = gcd a b == 1

We take coprime from the previous exercise and give it to filter, which applies it to each element of a list from 1 to one less than the number, returning only those that are true. lenght tells us how many elements are in the resulting list, and thus how many elements are coprime to n

Problem 35

(**) Determine the prime factors of a given positive integer. Construct a flat list containing the prime factors in ascending order.

Example:
* (prime-factors 315)
(3 3 5 7)

* primeFactors 315
[3, 3, 5, 7]

Solution:

primeFactors :: Integer -> [Integer]
primeFactors a = let (f, f1) = twoFactorsOf a
f' = if prime f then [f] else primeFactors f
f1' = if prime f1 then [f1] else primeFactors f1
in f' ++ f1'
where
twoFactorsOf a = let f = head \$ factors a
in (f, div a f)
factors a = filter (isFactor a) [2..a-1]
isFactor a b = rem a b == 0
prime a = (length \$ factors a) == 0

Kind of ugly, but it works though it may have bugs in corner cases. This uses the factor tree method of finding prime factors of a number. twoFactorsOf picks a factor and takes it and the factor you multiply it by and gives them to primeFactors. primeFactors checks to make sure the factors are prime. If not it prime factorizes them. In the end a list of prime factors is returned.

Problem 36

(**) Determine the prime factors of a given positive integer.

Construct a list containing the prime factors and their multiplicity.

Example:
* (prime-factors-mult 315)
((3 2) (5 1) (7 1))

*Main> prime_factors_mult 315
[(2 3), (1 5), (1 7)]

Solution:

prime_factors_mult n = encode \$ prime_factors_mult 2 n []
prime_factors i n xs = if i*i > n then n:xs else if i `divides` n then prime_factors i (n `div` i) (i:xs) else prime_factors (i+1) n xs
divides a b = (b `div` a)*a == b

We iterate through all numbers up to the square-root of n, and add them to our list, if they divide n. The function 'encode' is the solution to problem 10. It takes a list of numbers, and compresses it to a list of numbers paired with their multiplicity.

Problem 37

<Problem description>

Example:
<example in lisp>

Solution:

<description of implementation>

Problem 38

<Problem description>

Example:
<example in lisp>

Solution:

<description of implementation>

Problem 39

A list of prime numbers.

Given a range of integers by its lower and upper limit, construct a list of all prime numbers in that range.

P29> primesR 10 20
[11,13,17,19]

Solution 1:

primesR :: Integral a => a -> a -> [a]
primesR a b = filter isPrime [a..b]

If we are challenged to give all primes in the range between a and b we simply take all number from a up to b and filter the primes out.

Solution 2:

primes :: Integral a => [a]
primes = let sieve (n:ns) = n:sieve [ m | m <- ns, m `mod` n /= 0 ] in sieve [2..]

primesR :: Integral a => a -> a -> [a]
primesR a b = takeWhile (<= b) \$ dropWhile (< a) primes

Another way to compute the claimed list is done by using the Sieve of Eratosthenes. The primes function generates a list of all (!) prime numbers using this algorithm and primesR filter the relevant range out. [But this way is very slow and I only presented it because I wanted to show how nice the Sieve of Eratosthenes can be implemented in Haskell :)]

Problem 40

<Problem description>

Example:
<example in lisp>

Solution:

<description of implementation>

Problem 41

<Problem description>

Example:
<example in lisp>