如何使这个 Haskell 幂函数尾递归？

发布于 2024-08-31 00:31:27 字数 174 浏览 10 评论 0原文

我如何使这个 Haskell 幂函数尾递归？

turboPower a 0 = 1
turboPower a b
    | even b = turboPower (a*a) (b `div` 2)
    | otherwise = a * turboPower a (b-1)

原文

How would I make this Haskell power function tail recursive?

turboPower a 0 = 1
turboPower a b
    | even b = turboPower (a*a) (b `div` 2)
    | otherwise = a * turboPower a (b-1)

分享到QQ

分享到微博

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

发布评论

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

舂唻埖巳落 2024-09-07 00:31:27

turboPower a b = turboPower' 1 a b
  where
    turboPower' x a 0 = x
    turboPower' x a b
        | x `seq` a `seq` b `seq` False = undefined
        | even b = turboPower' x (a*a) (b `div` 2)
        | otherwise = turboPower' (x*a) a (b-1)

基本上，您想要做的是将您在“otherwise”步骤中执行的乘法移动到另一个参数（因为这就是阻止尾递归的原因）。

编辑添加一行，使所有三个参数严格评估，而不是惰性，因为这是惰性会伤害我们的众所周知的情况之一。

turboPower a b = turboPower' 1 a b
  where
    turboPower' x a 0 = x
    turboPower' x a b
        | x `seq` a `seq` b `seq` False = undefined
        | even b = turboPower' x (a*a) (b `div` 2)
        | otherwise = turboPower' (x*a) a (b-1)

Basically, what you want to do is move the multiplication that you're doing in the "otherwise" step (since that's what keeps this from being tail-recursive initially) to another parameter.

Edited to add a line making all three parameters strictly evaluated, instead of lazy, since this is one of those well-known situations where laziness can hurt us.

回复收藏 0 原文

~没有更多了~