エレファント・ビジュアライザー調査記録

ビジュアルプログラミングで数式の変形を表すことを考えていくブロクです。

ラムダ計算と無限ラムダ多項式(16)

フィボナッチ数列の例(4)

クラスを使ったものを考えます。

        private class FibClass
        {
            private int x = 0;
            private int y = 1;
            public int Next()
            {
                int z = x + y;
                x = y;
                y = z;
                return z;
            }
        }

このクラスを使ったものは以下のようになります。

            IEnumerable<int> fib()
            {
                FibClass fibobj = new FibClass();
                yield return 0;
                yield return 1;
                for (; ; )
                {
                    yield return fibobj.Next();
                }
            }

このクラスを変更しないようにしたものを考えます。

        private class FibClassImmutable
        {
            private readonly int x = 0;
            private readonly int y = 1;
            public FibClassImmutable()
            {
                x = 0;
                y = 1;
            }
            public FibClassImmutable(int x, int y)
            {
                this.x = x;
                this.y = y;
            }
            public FibClassImmutable Next()
            {
                return new FibClassImmutable(y, x + y);
            }
            public int Current
            {
                get
                {
                    return y;
                }
            }
        }

このクラスを使うと以下のようになります。

            IEnumerable<int> fib()
            {
                FibClassImmutable fibobj = new FibClassImmutable(0, 1);
                yield return 0;
                yield return 1;
                for (; ; )
                {
                    fibobj = fibobj.Next();
                    yield return fibobj.Current;
                }
            }

for を展開して変数を変更しないようにすると以下のようになります。

            IEnumerable<int> fib()
            {
                FibClassImmutable fibobj_0 = new FibClassImmutable(0, 1);
                yield return 0;
                yield return 1;
                FibClassImmutable fibobj_1 = fibobj_0.Next();
                yield return fibobj_1.Current;
                FibClassImmutable fibobj_2 = fibobj_1.Next();
                yield return fibobj_2.Current;
                FibClassImmutable fibobj_3 = fibobj_2.Next();
                yield return fibobj_3.Current;
                FibClassImmutable fibobj_4 = fibobj_3.Next();
                yield return fibobj_4.Current;
                FibClassImmutable fibobj_5 = fibobj_4.Next();
                yield return fibobj_5.Current;
                FibClassImmutable fibobj_6 = fibobj_5.Next();
                yield return fibobj_6.Current;
                FibClassImmutable fibobj_7 = fibobj_6.Next();
                yield return fibobj_7.Current;
                FibClassImmutable fibobj_8 = fibobj_7.Next();
                yield return fibobj_8.Current;
            }

フィボナッチ数列の例(5)

再帰的定義の関数を考えます。

            IEnumerable<int> fib()
            {
                int fib(int n)
                {
                    if (n == 0)
                    {
                        return 0;
                    }
                    else if (n == 1)
                    {
                        return 1;
                    }
                    else
                    {
                        return fib(n - 1) + fib(n - 2);
                    }
                }
                for (int i = 0; ; i++)
                {
                    yield return fib(i);
                }
            }

この関数は変数を変更しないので、for を展開すれば変数を変更しないようにすることができます。さらに再帰的定義を展開して再帰的定義を含まない形に書き直します。

            IEnumerable<int> fib()
            {
                int fib_0(int n)
                {
                    if (n == 0)
                    {
                        return 0;
                    }
                    else if (n == 1)
                    {
                        return 1;
                    }
                    else
                    {
                        return fib_1(n - 1) + fib_1(n - 2);
                    }
                }
                int fib_1(int n)
                {
                    if (n == 0)
                    {
                        return 0;
                    }
                    else if (n == 1)
                    {
                        return 1;
                    }
                    else
                    {
                        return fib_2(n - 1) + fib_2(n - 2);
                    }
                }
                int fib_2(int n)
                {
                    if (n == 0)
                    {
                        return 0;
                    }
                    else if (n == 1)
                    {
                        return 1;
                    }
                    else
                    {
                        return fib_3(n - 1) + fib_3(n - 2);
                    }
                }
                int fib_3(int n)
                {
                    if (n == 0)
                    {
                        return 0;
                    }
                    else if (n == 1)
                    {
                        return 1;
                    }
                    else
                    {
                        return fib_4(n - 1) + fib_4(n - 2);
                    }
                }
                int fib_4(int n)
                {
                    if (n == 0)
                    {
                        return 0;
                    }
                    else if (n == 1)
                    {
                        return 1;
                    }
                    else
                    {
                        return fib_5(n - 1) + fib_5(n - 2);
                    }
                }
                int fib_5(int n)
                {
                    if (n == 0)
                    {
                        return 0;
                    }
                    else if (n == 1)
                    {
                        return 1;
                    }
                    else
                    {
                        return fib_6(n - 1) + fib_6(n - 2);
                    }
                }
                int fib_6(int n)
                {
                    if (n == 0)
                    {
                        return 0;
                    }
                    else if (n == 1)
                    {
                        return 1;
                    }
                    else
                    {
                        return fib_7(n - 1) + fib_7(n - 2);
                    }
                }
                int fib_7(int n)
                {
                    if (n == 0)
                    {
                        return 0;
                    }
                    else if (n == 1)
                    {
                        return 1;
                    }
                    else
                    {
                        return fib_8(n - 1) + fib_8(n - 2);
                    }
                }
                int fib_8(int n)
                {
                    if (n == 0)
                    {
                        return 0;
                    }
                    else if (n == 1)
                    {
                        return 1;
                    }
                    else
                    {
                        return fib_9(n - 1) + fib_9(n - 2);
                    }
                }
                int fib_9(int n)
                {
                    return 0;
                }
                yield return fib_0(0);
                yield return fib_0(1);
                yield return fib_0(2);
                yield return fib_0(3);
                yield return fib_0(4);
                yield return fib_0(5);
                yield return fib_0(6);
                yield return fib_0(7);
                yield return fib_0(8);
                yield return fib_0(9);
            }