イテレーターとして定義するとどうなるか ChatGPT で調べてみました。以下のように入力しました。
fibonacciGenerator の定義をイテレーターの定義のように変更します。
- f().current で最初の項
- f().next().current で2番目の項
- f().next().next().current で3番目の項
を取得できるような f に変更するとします。
このような f は「μ-帰納的関数」になりますか
以下の結果となりました。
「μ-帰納的関数」としての `fibonacciGenerator` の可能性
1. 変更後の `fibonacciGenerator` の挙動
質問の意図に従い、`fibonacciGenerator` を イテレーター のように定義するとします。すなわち、以下のような API を持つオブジェクト `f` を返す関数になります：
- `f().current` → 最初の項（F(0)）
- `f().next().current` → 2 番目の項（F(1)）
- `f().next().next().current` → 3 番目の項（F(2)）
F# でこの仕様に合う形で定義すると、次のようになります：
type FibonacciIterator(a: int, b: int) = member this.current = a member this.next() = FibonacciIterator(b, a + b) let fibonacciGenerator () = FibonacciIterator(0, 1)ここで、`fibonacciGenerator()` は `FibonacciIterator(0, 1)` を返し、
`.current` を取得すれば現在の値、`.next()` を呼ぶと次の状態のイテレーターを得られます。2. μ-帰納的関数の定義との比較
μ-帰納的関数（μ-recursive function）は、次の操作から構成される関数のクラスです：
1. 基本関数
- ゼロ関数:
- 後者関数:
- 射影関数:
（入力の一部を取り出す）
2. 構成規則
- 原始再帰（Primitive Recursion）:
ある関数
を次のように定義できる場合：
これは原始再帰的関数である。
- 最小化（μ-operator）:
ある条件を満たす最小の
を見つける操作（計算不能性に関わる）。
3. `fibonacciGenerator` は μ-帰納的関数か？
μ-帰納的関数の通常の形式に合致しない
μ-帰納的関数は基本的に「自然数を入力として自然数を出力する関数」に制限されるため、高階関数のようなオブジェクトの返し方は μ-帰納的関数としては扱えない。
- `fibonacciGenerator` は「次の状態を持つ新しいオブジェクト」を生成し続けるが、μ-帰納的関数では状態を更新しながらオブジェクトを返す操作を直接定義できない。
個別のフィボナッチ値を取得する関数なら μ-帰納的
`fibonacciGenerator` の `.current` や `.next().current` を使って特定の
番目の値を取得できるが、そのままだと μ-帰納的関数とは言えない。ただし、以下のような形で「n 番目のフィボナッチ数」を求める関数に変形すれば μ-帰納的関数となる：
let rec fibonacci n a b = if n = 0 then a else fibonacci (n - 1) b (a + b) let fibonacciAt n = fibonacci n 0 1 // n 番目のフィボナッチ数を計算この `fibonacciAt` は
- `fibonacci(0) = 0`
- `fibonacci(1) = 1`
- `fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)`
