虽然你已经修复这些问题,有两个问题您原始的方法:
功能的应用程序是左关联的SML所以m f (n - 1)
被解释为(m f) (n - 1)
,不是期望m (f (n - 1))
。您可以通过明确指定包围m (f (n - 1))
来解决此问题。
为了能够从m
和m
从f
叫f
,您需要在第一个声明中使用关键字fun
,而不是val
(使函数的递归),以及关键字and
,而不是fun
或val
对第二个声明(使函数与第一个函数相互递归)。这看起来像
fun f n = ... (* I can call f or m from here! *)
and m n = ... (* I can call f or m from here! *)
为了使其更快,你可以memoize的!诀窍是让f
和m
作为自己的记忆版本的参数。
(* Convenience function: Update arr[i] to x, and return x. *)
fun updateAndReturn arr i x = (Array.update (arr, i, SOME x); x)
(*
* Look up result of f i in table; if it's not found, calculate f i and
* store in the table. The token is used so that deeper recursive calls
* to f can also try to store in the table.
*)
fun memo table f token i =
case Array.sub (table, i)
of NONE => updateAndReturn table i (f token i)
| SOME x => x
(*
* Given f, g, and n : int, returns a tuple (f', g') where f' and g' are memoized
* versions of f and g, respectively. f' and g' are defined only on the domain
* [0, n).
*)
fun memoizeMutual (f, g) n =
let
val fTable = Array.array (n, NONE)
val gTable = Array.array (n, NONE)
fun fMemo i = memo fTable f (fMemo, gMemo) i
and gMemo i = memo gTable g (gMemo, fMemo) i
in
(fMemo, gMemo)
end
fun female _ 0 = 1
| female (f, m) n = n - m (f (n - 1))
fun male _ 0 = 0
| male (m, f) n = n - f (m (n - 1))
fun hofstadter upTo =
let
val (male', female') = memoizeMutual (male, female) upTo
in
(List.tabulate (upTo, male'), List.tabulate (upTo, female'))
end
我改名为f
和m
到female
和male
。记忆的fMemo
和gMemo
通过female
和male
通过memoizeMutual
进行线程化。有趣的是,如果我们拨打male'
,male'
和female'
的结果被记录下来。
要确认它确实速度更快,请尝试评估hofstadter 10000
。它比你的版本要快得多。
作为最后一点,唯一的递归函数是fMemo
和gMemo
。我写的每一个函数都可以写成一个匿名函数(val memoizeMutual = fn ...
,val female = fn ...
等),但我选择不这样做,因为在SML中写递归函数的语法要紧凑得多。
为了概括这一点,你可以用类似哈希表的东西来替换memoizing的数组版本。然后,我们不必先指定备忘录的大小。
非常感谢您发布和解释您的解决方案。 “记忆”对我来说是一个新的过程。我期待着在未来实施它。感谢您的时间。 –