関数プログラミングの帰納的関数(14)

ここからは実際にプログラミング言語を定義した方が良さそうということで、以前にも調査したフィボナッチ数列の例を再び取り上げることにします。ChatGPT で調べてみました。

F# でフィボナッチ数列の無限列を生成するプログラムを作ってください

と入力すると以下の結果となりました。

F# でフィボナッチ数列の無限列を生成するには、遅延シーケンス (`Seq.unfold` など) を利用すると便利です。以下にその実装を示します。

実装例:

let fibonacci =
    Seq.unfold (fun (a, b) -> Some(a, (b, a + b))) (0, 1)

// フィボナッチ数列の最初の 10 項を表示
fibonacci |> Seq.take 10 |> Seq.toList |> printfn "%A"

説明:

1. `Seq.unfold` を使い、タプル `(a, b)` を元にして次の値を生成。
2. `(a, b)` の最初の値 `a` を出力し、次の状態 `(b, a + b)` に更新。
3. `fibonacci` は無限にフィボナッチ数列を生成するシーケンス。
4. `Seq.take 10` を使って、最初の 10 項を取得し、リストに変換して表示。

この方法で無限列としてフィボナッチ数列を扱うことができます！

F# でフィボナッチ数列の無限列を生成するプログラムをコンピューテーション式を使って書いてください

と入力すると以下の結果となりました。

F# の コンピューテーション式 (Computation Expressions) を使ってフィボナッチ数列の無限列を生成する方法を紹介します。

コンピューテーション式を使うと、非同期処理 (`async`) やシーケンス (`seq`) などの複雑な処理を直感的に記述できます。ここでは `seq` コンピューテーション式 を使って、遅延評価される無限のフィボナッチ数列を作成します。

コンピューテーション式を使ったフィボナッチ数列

let fibonacciSeq =
    seq {
        let mutable a, b = 0, 1
        while true do
            yield a
            let temp = a + b
            a <- b
            b <- temp
    }

// フィボナッチ数列の最初の 10 項を取得して表示
fibonacciSeq |> Seq.take 10 |> Seq.toList |> printfn "%A"

解説

1. `seq { ... }` を使うことで、 遅延評価されるシーケンス を作成。
2. `let mutable a, b = 0, 1` でフィボナッチ数列の初期値を設定。
3. `while true do` を使って 無限ループ を作成。
4. `yield a` で現在の `a` を出力（これにより 無限のシーケンス になる）。
5. `a <- b` と `b <- a + b` でフィボナッチ数列の次の値を計算。

ポイント

• コンピューテーション式 `seq {}` を使うと、イミュータブルな値を持つシーケンスを簡単に作成できる。
• 遅延評価 (`seq` の特性) により、無限にフィボナッチ数を生成できる。
• 必要な個数だけ `Seq.take n` で取り出せるため、リソース効率が良い。

これで コンピューテーション式を活用したフィボナッチ数列の無限生成 ができます！

F# に C# の「イテレーターを実装するクラス」のようなものはありますか

と入力すると以下の結果となりました。

F# には C# の 「イテレーターを実装するクラス」（`IEnumerable` を実装するカスタムクラス）のようなものはありません。しかし、F# では シーケンス (`seq`) や カスタム `IEnumerator` の実装 を使うことで、同じような動作を実現できます。

1. `seq {}` を使う（F# の標準的な方法）

F# では、C# の `yield return` に相当するものとして `seq {}` を使い、遅延評価されるイテレーターを簡単に作成できます。

フィボナッチ数列の例

let fibonacciSeq =
    seq {
        let mutable a, b = 0, 1
        while true do
            yield a
            let temp = a + b
            a <- b
            b <- temp
    }

// 最初の 10 項を取得して表示
fibonacciSeq |> Seq.take 10 |> Seq.toList |> printfn "%A"

ポイント

• `seq {}` は C# のイテレーター (`IEnumerable`) に相当するもの で、遅延評価される。
• `yield` を使って要素を順番に返す。
• F# では通常、この方法でイテレーターを作る。

2. `IEnumerator` を実装するカスタムクラス

もし C# の `IEnumerable` を実装するクラスのようなものを F# で手動で作りたい 場合、`IEnumerator` を実装することも可能です。

フィボナッチ数列を `IEnumerator` で実装

type FibonacciIterator() =
    let mutable a, b = 0, 1
    interface System.Collections.Generic.IEnumerator<int> with
        member _.Current = a
        member _.MoveNext() =
            let temp = a + b
            a <- b
            b <- temp
            true // 無限に続く
        member _.Reset() = a <- 0; b <- 1
        member _.Dispose() = ()

type FibonacciSequence() =
    interface System.Collections.Generic.IEnumerable<int> with
        member _.GetEnumerator() = new FibonacciIterator() :> System.Collections.Generic.IEnumerator<int>
    interface System.Collections.IEnumerable with
        member this.GetEnumerator() = (this :> System.Collections.Generic.IEnumerable<int>).GetEnumerator() :> System.Collections.IEnumerator

// C# スタイルでイテレーションする
let fibonacci = new FibonacciSequence()
for n in fibonacci |> Seq.take 10 do
    printf "%d " n

ポイント

• `FibonacciIterator` は `IEnumerator` を実装し、`MoveNext()` で次の値を計算する。
• `FibonacciSequence` は `IEnumerable` を実装し、`GetEnumerator()` で `FibonacciIterator` を返す。
• これは C# スタイルの「カスタムイテレータークラス」に近い実装 だが、F# では `seq {}` の方がシンプルで使いやすい。

3. C# の `yield return` を使ったクラスを F# で利用

C# の `yield return` を使ったクラスを F# から利用することもできます。

C# で `IEnumerable` を実装

using System.Collections;
using System.Collections.Generic;

public class FibonacciSequence : IEnumerable<int>
{
    public IEnumerator<int> GetEnumerator()
    {
        int a = 0, b = 1;
        while (true)
        {
            yield return a;
            int temp = a + b;
            a = b;
            b = temp;
        }
    }

    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
}

F# で利用

let fibonacci = FibonacciSequence()
fibonacci |> Seq.take 10 |> Seq.toList |> printfn "%A"

ポイント

• C# の `IEnumerable` は F# の `seq` として扱える。
• C# でイテレーターを実装し、F# で使うのもアリ。

まとめ

方法	メリット	デメリット
`seq {}` （F# 推奨）	簡潔で F# に最適化されている	`IEnumerator` を直接使えない
`IEnumerator` を実装	C# に近い、より制御可能	冗長で F# らしくない
C# の `yield return` を利用	C# / F# の両方で共通に使える	C# のコードが必要

F# では 通常 `seq {}` を使うのが最もシンプルで推奨される方法 ですが、C# スタイルの `IEnumerator` を実装することも可能です。用途に応じて適切な方法を選びましょう！

FibonacciIterator() を返す代わりに無名関数を返すようにすることはできますか

と入力すると以下の結果となりました。

はい、`FibonacciIterator()` の代わりに 無名関数を返すようにする ことは可能です。
具体的には、無名関数を返すことで、状態を内部に持ったイテレーターを関数として実装できます。

1. 無名関数を使ったフィボナッチ・イテレーター

Fibonacci シーケンスを無名関数で 状態を保持 しながら生成する方法です。

let fibonacciGenerator () =
    let a = ref 0
    let b = ref 1
    fun () ->
        let result = !a
        let temp = !a + !b
        a := !b
        b := temp
        result

// 使い方
let nextFib = fibonacciGenerator()

printfn "%d" (nextFib())  // 0
printfn "%d" (nextFib())  // 1
printfn "%d" (nextFib())  // 1
printfn "%d" (nextFib())  // 2
printfn "%d" (nextFib())  // 3

ポイント

• `fibonacciGenerator()` は 無名関数 `fun () -> ...` を返す。
• `ref` を使って `a` と `b` の状態を保持 し、次の呼び出し時に更新する。
• `nextFib()` を呼ぶたびに次のフィボナッチ数を計算。

2. 無名関数を `Seq.unfold` に適用

もう少し F# らしく書くなら、`Seq.unfold` を使って無限のフィボナッチ数列を生成し、それを無名関数としてラップすることもできます。

let fibonacciSeq = 
    Seq.unfold (fun (a, b) -> Some(a, (b, a + b))) (0, 1)

let nextFib =
    let enumerator = fibonacciSeq.GetEnumerator()
    fun () -> 
        enumerator.MoveNext() |> ignore
        enumerator.Current

// 使い方
printfn "%d" (nextFib())  // 0
printfn "%d" (nextFib())  // 1
printfn "%d" (nextFib())  // 1
printfn "%d" (nextFib())  // 2
printfn "%d" (nextFib())  // 3

ポイント

• `Seq.unfold` でフィボナッチ数列の 無限シーケンス を作る。
• `GetEnumerator()` を取得し、`MoveNext()` を実行して `Current` を取得 する無名関数を返す。
• こうすると、C# の `IEnumerator` に近い動作 をする。

まとめ

方法	説明
`ref` を使う	状態 (`a`, `b`) を `ref` で持たせ、更新しながら無名関数を返す。
`Seq.unfold` を使う	`Seq.unfold` で無限列を作り、`IEnumerator` を使って無名関数化する。

どちらの方法でも「無名関数としてフィボナッチ数列を生成する」ことが可能！

復刊 帰納的関数

数学基礎論　増補版

数学基礎論 (ちくま学芸文庫)

計算理論の基礎［原著第3版］ 1.オートマトンと言語

計算理論の基礎［原著第3版］ 2.計算可能性の理論

計算理論の基礎［原著第3版］ 3.複雑さの理論