自由モノイドのイテレーター(3) (original) (raw)

プログラミング言語の機能との対応

実際のプログラミング言語のイテレーターの機能では変換される先はどうなっているかを調べていきます。プログラミング言語ではどこかで無限の回数実行されるとそれ以後は実行されないので、結局「有限＋無限」が定義できればそれ以外はどのような定義でも良いと思われます。したがって前回の定義でも良いと思われますが、とりあえず進めていきます。

C# のイテレーターの機能について調べていきます。

「ラムダ計算と無限ラムダ多項式(15) - エレファント・ビジュアライザー調査記録」、「ラムダ計算と無限ラムダ多項式(16) - エレファント・ビジュアライザー調査記録」でフィボナッチ数列を値が変更できない変数を使って書き換える例について調べていましたが、最初はこれと同じような感じになります。最終的にはモノイドを使って書く予定です。最初からそうすると対応がよくわからなくなるため、最初は実際のプログラミング言語で書いていきます。

フィボナッチ数列の定義

定義については上記の記事を見てください。これを C# で「無限の長さのリスト」で書くと以下のようになります。

引数で渡すバージョン

    private static IEnumerable<int> FibonacciPrms(int x, int y)
    {
        yield return x;
        foreach (int num in FibonacciPrms(y, x + y))
        {
            yield return num;
        }
    }

Zip を使うバージョン

    private static IEnumerable<int> FibonacciZip()
    {
        yield return 0;
        yield return 1;
        foreach (int num in FibonacciZip().Zip(FibonacciZip().Skip(1), (x, y) => x + y))
        {
            yield return num;
        }
    }

イテレーターを実装するクラス

上記のイテレーターを C# のクラスで書くと以下のようになります。

引数で渡すバージョン

初期値は一段階戻した値にしないと最初の項を取得できないので、そのようになっています。

internal class FibonacciIterator : IEnumerable<int>
{
    private int x;
    private int y;
    public FibonacciIterator(int x, int y)
    {
        this.x = x;
        this.y = y;
    }

    public IEnumerator<int> GetEnumerator()
    {
        return new FibonacciEnumerator(x, y);
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }

    private class FibonacciEnumerator : IEnumerator<int>
    {
        private int x;
        private int y;

        public FibonacciEnumerator(int x, int y)
        {
            
            this.x = y - x;
            this.y = x;
        }

        public int Current
        {
            get
            {
                return x;
            }
        }

        object IEnumerator.Current => Current;

        public bool MoveNext()
        {
            (x, y) = (y, x + y);
            return true;
        }

        public void Reset()
        {
        }

        public void Dispose()
        {
        }
    }
}

Zip を使うバージョン

無理矢理ですが、以下のようになります。Concat、Zip も定義しています。

internal class FibonacciZipIterator : IEnumerable<int>
{
    private List<int> list;
    public FibonacciZipIterator(int x, int y)
    {
        list = new List<int> { x, y };
    }

    public IEnumerator<int> GetEnumerator()
    {
        return Concat(list, Zip(this, this.Skip(1), (x, y) => x + y)).GetEnumerator();
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
    private static IEnumerable<int> Concat(IEnumerable<int> e1, IEnumerable<int> e2)
    {
        foreach (int n in e1)
        {
            yield return n;
        }
        foreach (int n in e2)
        {
            yield return n;
        }
    }
    private static IEnumerable<int> Zip(IEnumerable<int> e1, IEnumerable<int> e2, Func<int, int, int> func)
    {
        IEnumerator<int> enumerator2 = e2.GetEnumerator();
        foreach (int n in e1)
        {
            if (!enumerator2.MoveNext())
            {
                break;
            }
            yield return func(n, enumerator2.Current);
        }
    }
}

「形式的写像」の展開

関数を展開する回数を有限に制限するバージョンです。回数を指定すると、一つの関数として書くことができます。

引数で渡すバージョン

    private static List<int> FibonacciListPrms(int k, int n, int x, int y)
    {
        if (k > n)
        {
            return new List<int>();
        }
        return new List<int> { x }.Concat(FibonacciListPrms(k + 1, n, y, x + y)).ToList();
    }

Zip を使うバージョン

    private static List<int> FibonacciListZip(int k, int n)
    {
        if (k > n)
        {
            return new List<int>();
        }
        return new List<int> { 0, 1 }.Concat(FibonacciListZip(k + 1, n).Zip(FibonacciListZip(k + 1, n).Skip(1), (x, y) => x + y)).ToList();
    }

モノイドの「素因数分解」

取得する項の個数を制限するバージョンです。項の個数に関する遅延評価に対応します。まず C# のイテレーターを実装するクラスと同じようなクラスを作成します。

internal class Iterator<T>
{
    private List<T> normal_part;
    private Func<Iterator<T>> next_func;

    public Iterator(T current, Func<Iterator<T>> func)
    {
        next_func = func;
        normal_part = new List<T> { current };
    }
    public Iterator(List<T> list, Func<Iterator<T>> func)
    {
        next_func = func;
        normal_part = list;
    }
    public T Current
    {
        get
        {
            return normal_part[0];
        }
    }
    public void MoveNext()
    {
        Reduce(next_func());
    }
    public void Reduce(Iterator<T> new_iterator)
    {
        normal_part = normal_part.Skip(1).Concat(new_iterator.normal_part).ToList();
        next_func = new_iterator.next_func;
    }
    private bool IsNormal
    {
        get
        {
            return normal_part.Count >= 1;
        }
    }
    public void Normalize()
    {
        if (!IsNormal)
        {
            MoveNext();
        }
    }
    public Iterator<T> Tail()
    {
        Normalize();
        if(normal_part.Count == 1)
        {
            return next_func();
        }
        return new Iterator<T>(normal_part.Skip(1).ToList(), next_func);
    }
    public Iterator<T> Zip(Iterator<T> iterator2, Func<T, T, T> func)
    {
        Normalize();
        iterator2.Normalize();
        T current = func(Current, iterator2.Current);
        return new Iterator<T>(current, () => Tail().Zip(iterator2.Tail(), func));
    }
}

引数で渡すバージョン

    private static Iterator<int> FibonacciIteratorPrms(int x, int y)
    {
        return new Iterator<int>(x, () => FibonacciIteratorPrms(y, x + y));
    }
    private static List<int> FibonacciIteratorRepeatPrms(int n, int x, int y)
    {
        Iterator<int> iter = FibonacciIteratorPrms(x, y);
        return IteratorRepeat(n, iter);
    }

Zip を使うバージョン

    private static Iterator<int> FibonacciIteratorZip()
    {
        return new Iterator<int>(new List<int> { 0, 1 }, () => FibonacciIteratorZip().Zip(FibonacciIteratorZip().Tail(), (x, y) => x + y));
    }
    private static List<int> FibonacciIteratorRepeatZip(int n)
    {
        Iterator<int> iter = FibonacciIteratorZip();
        return IteratorRepeat(n, iter);
    }

共通関数

上記のもので共通して使う、指定した回数繰り返す関数です。

    private static List<int> IteratorRepeat(int n, Iterator<int> iter)
    {
        List<int> res = new List<int> { };
        for (int i = 0; i < n; i++)
        {
            res.Add(iter.Current);
            iter.MoveNext();
        }
        return res;
    }

モノイドの「素因数分解」(変数を変更しない)

上記のものをなるべく変数を変更しないように書き換えます。イテレーターを実装するクラスは以下のようになります。

internal class PureIterator<T>
{
    private readonly List<T> normal_part;
    private readonly Func<PureIterator<T>> next_func;

    public PureIterator(T current, Func<PureIterator<T>> func)
    {
        next_func = func;
        normal_part = new List<T> { current };
    }
    public PureIterator(List<T> list, Func<PureIterator<T>> func)
    {
        next_func = func;
        normal_part = list;
    }
    public T Current
    {
        get
        {
            return normal_part[0];
        }
    }
    public PureIterator<T> MoveNext()
    {
        return Reduce(next_func());
    }
    public PureIterator<T> Reduce(PureIterator<T> new_iterator)
    {
        List<T> normal_part_new = normal_part.Skip(1).Concat(new_iterator.normal_part).ToList();
        Func<PureIterator<T>> next_func = new_iterator.next_func;
        return new PureIterator<T>(normal_part_new, next_func);
    }
    private bool IsNormal
    {
        get
        {
            return normal_part.Count >= 1;
        }
    }
    public PureIterator<T> Normalize()
    {
        if (!IsNormal)
        {
            return MoveNext();
        }
        return this;
    }
    public PureIterator<T> Tail()
    {
        PureIterator<T> iter = Normalize();
        if (iter.normal_part.Count == 1)
        {
            return iter.next_func();
        }
        return new PureIterator<T>(iter.normal_part.Skip(1).ToList(), iter.next_func);
    }
    public PureIterator<T> Zip(PureIterator<T> iterator2, Func<T, T, T> func)
    {
        PureIterator<T> iter1 = Normalize();
        PureIterator<T> iter2 = iterator2.Normalize();
        T current = func(iter1.Current, iter2.Current);
        return new PureIterator<T>(current, () => iter1.Tail().Zip(iter2.Tail(), func));
    }
}

引数で渡すバージョン

    private static PureIterator<int> FibonacciPureIteratorPrms(int x, int y)
    {
        return new PureIterator<int>(x, () => FibonacciPureIteratorPrms(y, x + y));
    }
    private static List<int> FibonacciPureIteratorRepeatPrms(int n, int x, int y)
    {
        PureIterator<int> iter = FibonacciPureIteratorPrms(x, y);
        return PureIteratorRepeat(n, iter);
    }

Zip を使うバージョン

    private static PureIterator<int> FibonacciPureIteratorZip()
    {
        return new PureIterator<int>(new List<int> { 0, 1 }, () => FibonacciPureIteratorZip().Zip(FibonacciPureIteratorZip().Tail(), (x, y) => x + y));
    }
    private static List<int> FibonacciPureIteratorRepeatZip(int n)
    {
        PureIterator<int> iter = FibonacciPureIteratorZip();
        return PureIteratorRepeat(n, iter);
    }

共通関数

上記のもので共通して使う、指定した回数繰り返す関数です。

    private static List<int> PureIteratorRepeat(int n, PureIterator<int> iter)
    {
        List<int> res = new List<int> { };
        for (int i = 0; i < n; i++)
        {
            res.Add(iter.Current);
            iter = iter.MoveNext();
        }
        return res;
    }