haskell - 在haskell中重写euler-totient函数

Question

如果我想编写 totient 函数，一种方法(假设我们有一个 primeFactors 函数，它返回一个包含多重性的列表。)如下:

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

这很好，但还有另一种方法可以做到这一点，即对 (1-1/p) 进行乘积，然后将乘积乘以 n。然而，这里存在一个“类型”问题，因为 1-1/p 从来都不是整数，所以像

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

不会按照编写的那样在 Haskell 中运行。

我的问题是是否有一种简单的方法可以在函数之间传递到新类型。我怀疑有某种柯里化(Currying)方法，但我一直无法解决。

Answer 1

有两个原因:

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

不起作用。

首先，product 需要一个参数 (a (Num a, Foldable t) => t a)，你给它三个 (map 、(\x->1-1/x) 和 (primeFactors n))。这是 $ 的典型用例。产品周围也缺少括号。我们这样写:

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

其次，您遇到数字类型问题。您正在将 1 除以一个整数。然而 / 需要两个小数:

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

您必须将 x 转换为小数。使用 fromIntegral 函数:

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

您必须使用 fromIntegral n 因为 (*) 需要两个相同类型的 Num:

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

现在它运行了，但它返回一个分数。

只需对结果进行轮即可获得整数(再次注意$)，然后就完成了:

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

编辑精度:我写道“product”需要一个参数 (a (Num a, Foldable t) => t a)，而你给它三个(map、(\x->1-1/x) 和 (primeFactors n))”。从技术上讲，这是不正确的:你不能给一个函数提供三个参数，因为 Haskell 中的函数总是接受一个参数，并且可能返回另一个接受另一个参数的函数......这就是“柯里化(Currying)”方法。因此，您向 product 提供了参数 map，但它需要一个可折叠的，因此出现错误。