用于查找固定点的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

或多或少是偶然的.

发生的事情是你使用cubed2的幂,这导致更大的2的幂.在几轮之后,结果将大到足以溢出并被截断 - 并且两个的大功率将截断为零,这恰好是该函数的固定点.

要完全清楚,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