Как сделать эту мощную хвостовую функцию Haskell рекурсивной?

Question

Как бы я сделал эту хвостовую функцию мощности Haskell рекурсивной?

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

Answer 1

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" (так как именно это предотвращает изначально хвостовую рекурсию), в другой параметр.

Отредактировано, чтобы добавить строку, в которой все три параметра строго оценены вместо ленивых, поскольку это одна из тех известных ситуаций, когда лень может причинить нам боль.