(**) 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.
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. length tells us how many elements are in the resulting list, and thus how many elements are coprime to n
Or slightly more concise, using list comprehension:
totient n = length [x | x <- [1..n], coprime x n]