用于查找固定点的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只是一个循环，在这种情况下，恰好终止并以有用的答案终止。

您可以在Toplevel中使用#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