recursion - 用于查找不动点的 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？

标签： recursionocamlfixed-point-iteration

Answer 1

或多或少是偶然的。

正在发生的事情是您正在使用cubed2 的幂，这会导致更大的 2 幂。经过几轮这样的结果将大到足以溢出并被截断 - 并且 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