SML 中的 Hofstadter 女性和男性序列
Hofstadter Female and Male sequences in SML
这是我的第一个 SML 程序。我正在尝试编写一个函数,该函数 returns 以列表形式显示 Hofstadter 的 Female 或 Male 序列的第一个数字到第 n 个数字。我目前拥有的是:
val m = fn (n) => if n = 0 then 1 :: [] else m f (n - 1);
val f = fn (n) => if n = 0 then 0 :: [] else f m (n - 1);
您可以在此处了解序列:
https://en.wikipedia.org/wiki/Hofstadter_sequence#Hofstadter_Female_and_Male_sequences
我得到的错误是:
[opening sequence.sml]
sequence.sml:1.49 Error: unbound variable or constructor: f
sequence.sml:1.47-1.58 Error: operator is not a function [tycon mismatch]
operator: int list
in expression:
(m <errorvar>) (n - 1)
val it = () : unit
我该如何纠正?
我最终采用了这种方法:
fun
m (n) = if n = 0 then 0 else n - (f (m (n - 1)))
and
f (n) = if n = 0 then 1 else n - (m (f (n - 1)));
val seq = fn n => List.tabulate((n), f);
速度很慢。如果有人有更快的版本,那么我很乐意看到它。
虽然你已经修复了它们,但你原来的方法有两个问题:
函数应用程序在 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! *)
为了更快,你可以记忆!诀窍是让 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
由 memoizeMutual
贯穿 female
和 male
。有趣的是,如果我们调用 male'
,那么 male'
和 female'
的结果都会被记忆。
要确认它确实更快,请尝试评估 hofstadter 10000
。这比你的版本永远要快得多。
最后一点,递归函数只有 fMemo
和 gMemo
。我写的每个其他函数都可以写成匿名函数(val memoizeMutual = fn ...
、val female = fn ...
等),但我选择不这样做,因为编写递归函数的语法在 SML 中要紧凑得多。
为了概括这一点,您可以将记忆化的数组版本替换为哈希 table 之类的东西。这样我们就不必预先指定记忆的大小。
这是我的第一个 SML 程序。我正在尝试编写一个函数,该函数 returns 以列表形式显示 Hofstadter 的 Female 或 Male 序列的第一个数字到第 n 个数字。我目前拥有的是:
val m = fn (n) => if n = 0 then 1 :: [] else m f (n - 1);
val f = fn (n) => if n = 0 then 0 :: [] else f m (n - 1);
您可以在此处了解序列: https://en.wikipedia.org/wiki/Hofstadter_sequence#Hofstadter_Female_and_Male_sequences
我得到的错误是:
[opening sequence.sml]
sequence.sml:1.49 Error: unbound variable or constructor: f
sequence.sml:1.47-1.58 Error: operator is not a function [tycon mismatch]
operator: int list
in expression:
(m <errorvar>) (n - 1)
val it = () : unit
我该如何纠正?
我最终采用了这种方法:
fun
m (n) = if n = 0 then 0 else n - (f (m (n - 1)))
and
f (n) = if n = 0 then 1 else n - (m (f (n - 1)));
val seq = fn n => List.tabulate((n), f);
速度很慢。如果有人有更快的版本,那么我很乐意看到它。
虽然你已经修复了它们,但你原来的方法有两个问题:
函数应用程序在 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! *)
为了更快,你可以记忆!诀窍是让 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
由 memoizeMutual
贯穿 female
和 male
。有趣的是,如果我们调用 male'
,那么 male'
和 female'
的结果都会被记忆。
要确认它确实更快,请尝试评估 hofstadter 10000
。这比你的版本永远要快得多。
最后一点,递归函数只有 fMemo
和 gMemo
。我写的每个其他函数都可以写成匿名函数(val memoizeMutual = fn ...
、val female = fn ...
等),但我选择不这样做,因为编写递归函数的语法在 SML 中要紧凑得多。
为了概括这一点,您可以将记忆化的数组版本替换为哈希 table 之类的东西。这样我们就不必预先指定记忆的大小。