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

或多或少是偶然的。

发生的事情是，您正在对 2 的幂使用 cubed，这会导致更大的 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

用于查找不动点的 OCaml 函数

An OCaml function for finding fixed points

recursion

ocaml

fixed-point-iteration