haskellprimestype-signature

Unexpected output from function in Haskell


I have this function which takes an integer n, and returns the number of integers less than n which are coprime with n. I don't know where my code might be failing as I think I check everything needed for it to work.

I expect an output like this:

eTotient 73 = 72

But I have one that looks like this:

eTotient 73 = [2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72]

Here is my code:

divisorCoPrime :: Int -> [Maybe Int]
divisorCoPrime n = divisorCoPrime2 n n

divisorCoPrime2 :: Int -> Int -> [Maybe Int]
divisorCoPrime2 n 1 = []
divisorCoPrime2 n x
    | divides n x && isPrime x = Just x:divisorCoPrime2 n (x-1)
    | otherwise = divisorCoPrime2 n (x-1)

isCoprime :: Int -> Int -> Bool
isCoprime x y = isCoprime2 (divisorCoPrime x) (divisorCoPrime y)

isCoprime2 :: [Maybe Int] -> [Maybe Int] -> Bool
isCoprime2 [] y = True
isCoprime2 x [] = True
isCoprime2 (x:xs) y
    | foldl (||) False (map (x==) y) = False
    | otherwise = isCoprime2 xs y
    
eTotient :: Int -> [Int]
eTotient n = filter (isCoprime n ) [2..(n-1)]

Solution

  • According to Wikipedia:

    Euler's totient function [which is what I'm guessing eTotient is supposed to be] counts the positive integers up to a given integer n that are relatively prime to n

    filter (isCoprime n ) [2..(n-1)] is a list of such integers, but you want the number of these integers - the length of the list. Assuming the rest of the code is correct, that would look like this:

    eTotient :: Int -> Int
    eTotient n = length $ filter (isCoprime n ) [2..(n-1)]