Функция OCaml для поиска фиксированных точек

Question

У меня есть функция OCaml для поиска фиксированных точек:

>> let rec fix f x =
     let x' = f x in
       if x = x' then x else fix f x';;
(system message) val fix : ('a -> 'a) -> 'a -> 'a = <fun>

Вопрос в том, я не понимаю, как это работает, когда я печатаю:

>> let cubed x = x*x*x;;
(system message) val cubed : int -> int = <fun>

>> fix cubed 2;;
(system message) - : int = 0

В моем понимании, fix cubed 2 войдет в бесконечный цикл fix cubed 2*2*2, fix cubed (2*2*2)*(2*2*2)*(2*2*2) и так далее.Как эта функция правильно находит фиксированную точку 0?

Answer 1

Более или менее случайно.

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

Для полной ясности, OCamlне будет выполнять какой-либо сложный поиск или обман, fix - это просто цикл, который в этом случае заканчивается полезным ответом.

Вы можете использовать #trace на верхнем уровне, чтобы увидеть, как это происходит:

# #trace cubed;;
cubed is now traced.
# fix cubed 2
  ;;
  cubed <-- 2
cubed --> 8
cubed <-- 8
cubed --> 512
cubed <-- 512
cubed --> 134217728
cubed <-- 134217728
cubed --> 0
cubed <-- 0
cubed --> 0
- : int = 0