rewriting euler-totient function in haskell

Question

If I wanted to write the totient function, one way (assuming that we have a primeFactors function, that returns a list including multiplicity.) is the following:

totient:: Integer->Integer
totient m = product [(p - 1)  | p <- primeFactors m]

which would be fine, but there is another way to do this, by taking the product over (1-1/p) and just multiplying the product by n. However, there is a "type" problem here, since 1-1/p is never an integer, so something like

totientRevisited n =n* product  map (\x->1-1/x) (primeFactors n)

will not run in Haskell as written.

My question is whether or not there is a simple way to pass to a new type in between the function. I suspect some way of currying, but I've been unable to work it out.

Answer 1

There are two reasons why:

totientRevisited n = n * product  map (\x->1-1/x) (primeFactors n)

doesn't work.

First, product expects one argument (a (Num a, Foldable t) => t a) and you give it three (map, (\x->1-1/x) and (primeFactors n)). That's the typical use case for $. You lack parentheses around the product too. Let's write this:

totientRevisited n = n * (product $ map (\x->1-1/x) (primeFactors n))

Second, you have an issue with numeric types. You are dividing 1 by an Integer. Yet / takes two Fractionals:

Prelude> :t (/)
(/) :: Fractional a => a -> a -> a

You have to convert x to a Fractional. Use the fromIntegral function:

totientRevisited n = (fromIntegral n) * (product $ map (\x->1-1/(fromIntegral x)) (primeFactors n))

You have to use fromIntegral n because (*) takes two Nums of the same type:

Prelude> :t (*)
(*) :: Num a => a -> a -> a

Now it runs, but it returns an Fractional.

Just take the round of the result to get an Integer (again, note the $) and you are done:

totientRevisited n = round $ (fromIntegral n) * (product $ map (\x->1-1/(fromIntegral x)) (primeFactors n))

EDIT Precision: I wrote that "product expects one argument (a (Num a, Foldable t) => t a) and you give it three (map, (\x->1-1/x) and (primeFactors n))". That's technically not true: you can't give three arguments to a function, because a function in Haskell always takes one argument and might return another function that will take another argument... That's what "curryfication" means. Thus, you gave to product the argument map, yet it expects a foldable, hence the error.