Прелюдия возведение в степень трудно понять

Question

Я читал Прелюдию на Хаскеле и нашел ее довольно понятной, а потом наткнулся на определение экспоненты:

(^)              :: (Num a, Integral b) => a -> b -> a
x ^ 0            =  1
x ^ n | n > 0    =  f x (n-1) x
                         where f _ 0 y = y
                         f x n y = g x n  where
                                g x n | even n  = g (x*x) (n `quot` 2)
                                     | otherwise = f x (n-1) (x*y)
_ ^ _            = error "Prelude.^: negative exponent"

Я не понимаю необходимости двух вложенных wheres.

Что я понял до сих пор:

(^)              :: (Num a, Integral b) => a -> b -> a

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

x ^ 0            =  1

Базовый случай, легко.

g x n | even n  = g (x*x) (n `quot` 2)
      | otherwise = f x (n-1) (x*y)

Вычисление в квадрате... вроде... Почему f нужен помощник? Почему f а также g заданные имена из одной буквы? Это просто оптимизация, я что-то упускаю очевидное?

 _ ^ _            = error "Prelude.^: negative exponent"

N> 0 было проверено ранее, N отрицательно, если мы приехали сюда, поэтому ошибка.

---

Моя реализация была бы прямым переводом к коду:

Function exp-by-squaring(x, n )
    if n < 0 then return exp-by-squaring(1 / x, - n );
    else if n = 0 then return 1; else if n = 1 then return x ;
    else if n is even then return exp-by-squaring(x * x, n / 2);
    else if n is odd then return x * exp-by-squaring(x * x, (n - 1) / 2).

Псевдокод из википедии.

Answer 1

Чтобы проиллюстрировать, что говорит @dfeuer, обратите внимание, что f написано это либо:

1. f возвращает значение
2. или же, f называет себя новыми аргументами

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

С другой стороны, рассмотрим альтернативную реализацию возведения в степень путем возведения в квадрат:

-- assume n >= 0
exp x 0 = 1
exp x n | even n    = exp (x*x) (n `quot` 2)
        | otherwise = x * exp x (n-1)

Проблема здесь в том, что в предложении иначе последняя выполненная операция является умножением. Так exp или:

1. возвращает 1
2. называет себя новыми аргументами
3. вызывает себя с некоторыми новыми аргументами и умножает результат на x,

exp не является хвостовой рекурсией и поэтому не может быть преобразован в цикл.

Answer 2

f это действительно оптимизация. Наивный подход будет "сверху вниз", рассчитывая x^(n `div` 2) а затем возвести в квадрат результат. Недостатком этого подхода является то, что он создает стек промежуточных вычислений. Какие f позволяет этой реализации сделать это в первую очередь x (однократное умножение), а затем поднять результат до приведенного показателя, рекурсивно хвост. Конечным результатом является то, что функция, скорее всего, будет работать полностью в регистрах машины. g кажется, помогает избежать проверки конца цикла, когда показатель равен, но я не совсем уверен, хорошая ли это идея.

Answer 3

Как уже отмечалось, функция написана с использованием хвостовой рекурсии для эффективности.

Тем не менее, обратите внимание, что можно удалить самый внутренний where сохраняя хвостовую рекурсию следующим образом: вместо

x ^ n | n > 0 =  f x (n-1) x
      where f _ 0 y = y
            f x n y = g x n
              where g x n | even n  = g (x*x) (n `quot` 2)
                          | otherwise = f x (n-1) (x*y)

мы можем использовать

x ^ n | n > 0 =  f x (n-1) x
      where f _ 0 y = y
            f x n y | even n    = f (x*x) (n `quot` 2) y
                    | otherwise = f x (n-1) (x*y)

что также возможно более читабельно.

Однако я понятия не имею, почему авторы Prelude выбрали свой вариант.

Answer 4

Насколько я понимаю, возведение в степень решается путем возведения в квадрат до тех пор, пока показатель будет четным.

Это приводит к ответу почему f нужен в случае нечетного числа - мы используем f вернуть результат в случае g x 1в каждом другом нечетном случае мы используем f чтобы вернуться в g-routine.

Вы можете увидеть это лучше, я думаю, если вы посмотрите на пример:

x ^ n | n > 0 = f x (n-1) x
  where f _ 0 y = y
        f x n y = g x n
          where g x n | even n  = g (x*x) (n `quot` 2)
                      | otherwise = f x (n-1) (x*y)

2^6 = -- x = 2, n = 6, 6 > 0 thus we can use the definition
f 2 (6-1) 2 = f 2 5 2 -- (*)
            = g 2 5 -- 5 is odd we are in the "otherwise" branch
            = f 2 4 (2*2) -- note that the second '2' is still in scope from  (*)
            = f 2 4 (4) -- (**) for reasons of better readability evaluate the expressions, be aware that haskell is lazy and wouldn't do that
            = g 2 4
            = g (2*2) (4 `quot` 2) = g 4 2
            = g (4*4) (2 `quot` 2) = g 16 1
            = f 16 0 (16*4) -- note that the 4 comes from the line marked with (**)
            = f 16 0 64 -- which is the base case for f
            = 64

Теперь к вашему вопросу об использовании однобуквенных названий функций - это то, к чему вы должны привыкнуть, так пишут большинство людей в сообществе. На компилятор не влияет то, как вы называете свои функции, если они начинаются со строчной буквы.