Почему эта рекурсивная функция для квадратных корней дает неправильный результат?

Question

Я сделал эту хвостовую рекурсивную функцию для вычисления квадратных корней:

sqrt x n a = if n == 0 then a else sqrt x (n - 1) (a + x/a)/2

По какой-то причине он дает неверный результат, когда n больше 1, то есть когда его спрашивают для улучшения приближения, а, более одного раза. Возвращает число, которое становится все ближе и ближе к 0 при увеличении n. Я пытался реализовать одну и ту же рекурсивную формулу различными способами, например так:

sqrt x n = if n == 0 then 1 else (a + x/a)/2 where a = sqrt x (n - 1)

sqrt x = 1:map (\a -> (a + x/a)/2) (sqrt x)

И все это прекрасно работает. Это только первый пример, который не работает, и я не могу понять почему, сколько бы я ни старался.

Answer 1

Выражение:

sqrt x n a = if n == 0 then a else  sqrt x (n - 1) (a + x/a)  / 2

анализируется как:

sqrt x n a = if n == 0 then a else <b>(sqrt x (n - 1) (a + x/a))</b> / 2

Таким образом, sqrt x (n-1) (a+x/a) рассматривается как числитель деления на два. Вы должны добавить квадратные скобки здесь:

sqrt x n a = if n == 0 then a else sqrt x (n - 1) <b>((a + x/a) / 2)</b>

С учетом данного исправления мы можем, например, вычислить квадрат root из пяти как:

Prelude> sqrt 5 10 1
2.23606797749979

Согласно Википедии , это:

2.23606797749978969640917366873127623544061835961152572427089…

, так что это уже совсем близко.