Haskell中重写欧拉函数（Euler-Totient）的类型问题咨询

在Haskell里实现欧拉函数（φ函数），有两种经典思路，咱们来聊聊每种的实现方式，还有第二种思路里遇到的类型问题怎么解决：

方法一：基于素因子列表直接计算 #

如果你已经有一个能返回素因子列表的primeFactors函数，完全可以用它来快速实现欧拉函数。核心逻辑是利用欧拉函数的数学性质：对于正整数m，φ(m)等于其所有不同素因子p对应的(p-1)的乘积。

对应的Haskell代码如下：

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

这里要注意：如果你的primeFactors返回的是含重数的素因子列表（比如分解12会返回[2,2,3]），那你需要先对列表去重（比如用nub (primeFactors m)），否则重复的素因子会导致计算结果错误。原内容提到这个实现可行，推测你的primeFactors已经处理了去重逻辑~

方法二：基于(1-1/p)乘积的思路（解决类型不匹配问题） #

另一种常见思路是用欧拉函数的另一种数学定义：φ(n) = n × ∏(1 - 1/p)，其中p是n的所有不同素因子。但直接按这个公式写Haskell代码会遇到类型问题——因为1 - 1/p的结果是分数，不是整数，直接和整数n相乘会触发类型不兼容的错误。

解决这个问题有两种靠谱的方式：

• 用整数运算替代分数运算：把(1 - 1/p)转化为(p-1)/p，那么整个式子可以变形为φ(n) = ∏(p-1) × (n / ∏p)。因为n是所有素因子（去重）的倍数，所以n / ∏p的结果肯定是整数，全程用整数运算就能避免类型问题：

import Data.List (nub)

totientRevisited :: Integer -> Integer
totientRevisited n = let uniquePrimes = nub (primeFactors n)
                         productMinusOne = product (map (\p -> p - 1) uniquePrimes)
                         productPrimes = product uniquePrimes
                     in productMinusOne * (n `div` productPrimes)

• 使用有理数类型处理：借助Haskell的Rational类型来计算分数乘积，最后再提取整数结果。这种方式更贴近原始数学公式，也不会有精度丢失：

import Data.List (nub)
import Data.Ratio

totientRevisited :: Integer -> Integer
totientRevisited n = numerator $ (n % 1) * product [(p - 1) % p | p <- nub (primeFactors n)]

内容的提问来源于stack exchange，提问作者Andres Mejia