Haskell 幂函数

发布于 2024-11-04 19:08:05 字数 497 浏览 3 评论 0原文

如何编写利用以下事实的幂函数：要将 x 计算到 n 次方（其中 n 是正整数），如果 n 是偶数，则可以通过对该次方的一半进行平方来找到 x 的 n 次方。例如，x^12 是 x^6 * x^6。对于奇数幂，只需从幂中减一，然后将较小幂的结果乘以 x。例如，x^13 为 x * x^12，即 x * x^6 * x^6。递归地，与将 x 乘以指定的次数相比，可以用更少的工作找到任何幂。我想出了这个

power x n
    | n == 0  =  1
    | x == 0  =  0
    | even n = ( power x (n / 2) ) * ( power x (n / 2) )
    | odd n = x * ( power x ((n - 1) / 2)) * ( power x ((n - 1) / 2) )

，但我收到一条错误消息“错误 - 未解决的重载” * 类型：（积分 a，分数 a）=>整数 * 表达式：幂 2 2

原文

how to write a power function which makes use of the following facts: To raise x to a power n (where n is a positive whole number), if n is even, you can find the nth power of x by squaring half that power. For example, x^12 is x^6 * x^6. For odd powers, just subtract one from the power, and multiply the result for the smaller power by x. for example, x^13 is x * x^12, which is x * x^6 * x^6. Recursively, any power can be found with less work than multiplying x by itself the number of times indicated.
I came up with this

power x n
    | n == 0  =  1
    | x == 0  =  0
    | even n = ( power x (n / 2) ) * ( power x (n / 2) )
    | odd n = x * ( power x ((n - 1) / 2)) * ( power x ((n - 1) / 2) )

but I get an error saying ERROR - Unresolved overloading
* Type : (Integral a, Fractional a) => Integer
* Expression : power 2 2

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

┼── 2024-11-11 19:08:05

这里发生的是一种常见的类型不匹配。首先，看一下 even 的类型签名： even :: (Integral a) =>一个->布尔。 odd 有类似的签名。因此您可以看到，even 和 odd 采用 Integral 类型类的任何类型并对其进行求值。然后查看 / 的签名： (/) :: (Fractional a) =>一个->一个->一个。 / 仅采用 Fractional 类型，而不采用 Integral 类型。一种类型不可能同时被这两个函数求值。在这种情况下，有一个简单的解决方法：使用 div 而不是 /。请注意，如果您使用 div 作为中缀函数（将其放置在参数之间），则需要在 div 周围添加反引号。

回复收藏 0 原文

浅唱々樱花落 2024-11-11 19:08:05

查看 even 的类型并将其与 / 的类型进行比较。

回复收藏 0 原文

挽心 2024-11-11 19:08:05

现在您的代码正在运行，请注意：Haskell 不会自动记忆函数，因此您在最后两行中计算了两次对 power 的递归调用。我建议引入一个简单的函数 sqr k = k * k 并使用它。有几种方式：单独的函数；一个 where 子句；并让。

我更喜欢 let：

power _ 0 = 1
power 0 _ = 0
power x n  = let sqr k = k * k
                 half_n = n `div` 2  
                 sqrHalfPower = sqr ( power x half_n )
             in if even n then sqrHalfPower else x * sqrHalfPower

正如您所看到的，模式匹配处理前两种情况。然后let定义了一些有用的表达式，稍后可以在in中使用。请注意，对于奇数，(n-1) `div` 2 给出的结果与 n `div` 2 相同，因此我们可以统一这两种情况。

Just a remark now that your code is running: Haskell doesn't automatically memoize functions, so you're calculating the recursive calls to power twice in the last two lines. I would recommend to introduce a simple function sqr k = k * k and to use it. There are several ways: a separate function; a where clause; and let.

I would prefer let:

power _ 0 = 1
power 0 _ = 0
power x n  = let sqr k = k * k
                 half_n = n `div` 2  
                 sqrHalfPower = sqr ( power x half_n )
             in if even n then sqrHalfPower else x * sqrHalfPower

As you can see pattern matching deals with the first two cases. Then let defines some useful expressions, which can be used later in in. Note that for odd numbers, (n-1) `div` 2 gives the same result as n `div` 2, so we can unify both cases.

回复收藏 0 原文

断念 2024-11-11 19:08:05

我认为，计算幂的最快方法：

     pow:: Integer->Integer->Integer
     pow x n  |(n==1) = x
              |even n = (pow x ( div n 2))*(pow x ( div n 2)) 
              |odd n  = x * (pow x (n-1))

您也可以使用“Int”代替“Integer”（将签名中的Int上的Integer替换为Integer！）。

I think, the fastest way to calculate power:

     pow:: Integer->Integer->Integer
     pow x n  |(n==1) = x
              |even n = (pow x ( div n 2))*(pow x ( div n 2)) 
              |odd n  = x * (pow x (n-1))

you can also use "Int" instead "Integer"(replace Integer on Int in the signature!).

回复收藏 0 原文

~没有更多了~