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

プログラミング言語の機能との対応(自由モノイドクラス作成)

自由モノイドを表すクラスを作成します。「有限＋無限」の続きです。

自由モノイドクラスの定義

以下のクラスを定義します(Zero、Unit はモナドの用語です。これはモナドに対応させたいためで今後検討することがあるかもしれません)。

public class FreeMonoid<T>
{
    protected List<T> list;
    protected FreeMonoid()
    {
        
        list = new List<T>();
    }
    public static FreeMonoid<T> Zero
    {
        get
        {
            return new FreeMonoid<T>();
        }
    }
    public bool IsZero
    {
        get
        {
            return list.Count == 0;
        }
    }
    public static FreeMonoid<T> Unit(T element)
    {
        FreeMonoid<T> res = new FreeMonoid<T>();
        res.list.Add(element);
        return res;
    }
    public List<T> List { get => list; set => list = value; }

    public static FreeMonoid<T> operator *(FreeMonoid<T> x, FreeMonoid<T> y)
    {
        FreeMonoid<T> product = new FreeMonoid<T>();
        product.list = x.list.Concat(y.list).ToList();
        return product;
    }
    public static FreeMonoid<T> operator *(T x, FreeMonoid<T> y)
    {
        FreeMonoid<T> product = new FreeMonoid<T>();
        product.list = y.list.Prepend(x).ToList();
        return product;
    }
    public static FreeMonoid<T> operator *(FreeMonoid<T> x, T y)
    {
        FreeMonoid<T> product = new FreeMonoid<T>();
        product.list = x.list.Append(y).ToList();
        return product;
    }
    public static FreeMonoid<Domain<T>> operator *(FreeMonoid<T> x, FreeMonoid<Domain<T>> y)
    {
        return x.Map(x => new Domain<T>(x)) * y;
    }
    public T Head()
    {
        return list.First();
    }
    public FreeMonoid<T> Tail()
    {
        FreeMonoid<T> res = new FreeMonoid<T>();
        res.list = list.Skip(1).ToList();
        return res;
    }
    public FreeMonoid<T> Zip(FreeMonoid<T> x, Func<T, T, T> f)
    {
        FreeMonoid<T> res = new FreeMonoid<T>();
        res.list = list.Zip(x.list, f).ToList();
        return res;
    }
    public FreeMonoid<U> Map<U>(Func<T, U> f)
    {
        FreeMonoid<U> res = new FreeMonoid<U>();
        res.list = list.Select(f).ToList();
        return res;
    }
    public bool IsSingle
    {
        get
        {
            return list.Count == 1;
        }
    }
    public bool IsNormal
    {
        get
        {
            return list.Count >= 1;
        }
    }
}

「形式的写像」の展開

引数で渡すバージョン(自由モノイド版)

    private static FreeMonoid<int> FibonacciMonoidPrms(int k, int n, int x, int y)
    {
        if (k > n)
        {
            return FreeMonoid<int>.Zero;
        }
        return x * FibonacciMonoidPrms(k + 1, n, y, x + y);
    }

Zip を使うバージョン

    private static FreeMonoid<int> FibonacciMonoidZip(int k, int n)
    {
        if (k > n)
        {
            return FreeMonoid<int>.Zero;
        }
        return FreeMonoid<int>.Unit(0) * 1 * FibonacciMonoidZip(k + 1, n).Zip(FibonacciMonoidZip(k + 1, n).Tail(), (x, y) => x + y);
    }

イテレーターを実装するクラス(自由モノイド版)

internal class MonoidIterator<T>
{
    private readonly FreeMonoid<T> normal_part;
    private readonly Func<MonoidIterator<T>> next_func;

    public MonoidIterator(T current, Func<MonoidIterator<T>> func)
    {
        next_func = func;
        normal_part = FreeMonoid<T>.Unit(current);
    }
    public MonoidIterator(FreeMonoid<T> list, Func<MonoidIterator<T>> func)
    {
        next_func = func;
        normal_part = list;
    }
    public T Current
    {
        get
        {
            return normal_part.Head();
        }
    }
    public MonoidIterator<T> MoveNext()
    {
        return Reduce(next_func());
    }
    public MonoidIterator<T> Reduce(MonoidIterator<T> new_iterator)
    {
        FreeMonoid<T> normal_part_new = normal_part.Tail() * new_iterator.normal_part;
        Func<MonoidIterator<T>> next_func = new_iterator.next_func;
        return new MonoidIterator<T>(normal_part_new, next_func);
    }
    private bool IsNormal
    {
        get
        {
            return normal_part.IsNormal;
        }
    }
    public MonoidIterator<T> Normalize()
    {
        if (!IsNormal)
        {
            return MoveNext();
        }
        return this;
    }
    public MonoidIterator<T> Tail()
    {
        MonoidIterator<T> iter = Normalize();
        if (iter.normal_part.IsSingle)
        {
            return iter.next_func();
        }
        return new MonoidIterator<T>(iter.normal_part.Tail(), iter.next_func);
    }
    public MonoidIterator<T> Zip(MonoidIterator<T> iterator2, Func<T, T, T> func)
    {
        MonoidIterator<T> iter1 = Normalize();
        MonoidIterator<T> iter2 = iterator2.Normalize();
        T current = func(iter1.Current, iter2.Current);
        return new MonoidIterator<T>(current, () => iter1.Tail().Zip(iter2.Tail(), func));
    }
}

引数で渡すバージョン

    private static MonoidIterator<int> FibonacciMonoidIteratorPrms(int x, int y)
    {
        return new MonoidIterator<int>(x, () => FibonacciMonoidIteratorPrms(y, x + y));
    }
    private static FreeMonoid<int> FibonacciMonoidIteratorRepeatPrms(int n, int x, int y)
    {
        MonoidIterator<int> iter = FibonacciMonoidIteratorPrms(x, y);
        return MonoidIteratorRepeat(n, iter);
    }

Zip を使うバージョン

    private static MonoidIterator<int> FibonacciMonoidIteratorZip()
    {
        return new MonoidIterator<int>(FreeMonoid<int>.Unit(0) * 1, () => FibonacciMonoidIteratorZip().Zip(FibonacciMonoidIteratorZip().Tail(), (x, y) => x + y));
    }
    private static FreeMonoid<int> FibonacciMonoidIteratorRepeatZip(int n)
    {
        MonoidIterator<int> iter = FibonacciMonoidIteratorZip();
        return MonoidIteratorRepeat(n, iter);
    }

共通関数

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

    private static FreeMonoid<int> MonoidIteratorRepeat(int n, MonoidIterator<int> iter)
    {
        FreeMonoid<int> res = FreeMonoid<int>.Zero;
        for (int i = 0; i < n; i++)
        {
            res = res * iter.Current;
            iter = iter.MoveNext();
        }
        return res;
    }

モノイドの「素因数分解」(自由モノイド版)

「有限＋無限」クラス

public class LimitMonoid<T>
{
    private FreeMonoid<T> reduced_part;
    private FreeMonoid<Domain<T>> unreduced_part;
    public LimitMonoid(FreeMonoid<Domain<T>> prod)
    {
        reduced_part = FreeMonoid<T>.Zero;
        unreduced_part = prod;
        Normalize();
    }
    public static LimitMonoid<T> Unit(T val)
    {
        return new LimitMonoid<T>(FreeMonoid<Domain<T>>.Unit(new Domain<T>(val)));
    }
    
    
    public static LimitMonoid<T> Unit(Func<LimitMonoid<T>> val)
    {
        return new LimitMonoid<T>(FreeMonoid<Domain<T>>.Unit(new Domain<T>(val)));
    }
    private void Normalize()
    {
        while (!unreduced_part.IsZero && unreduced_part.Head().IsIrreducible)
        {
            reduced_part = reduced_part * unreduced_part.Head().IrreducibleOne;
            unreduced_part = unreduced_part.Tail();
        }
    }
    public bool IsReducible
    {
        get => !unreduced_part.IsZero && unreduced_part.Head().IsReducible;
    }
    public LimitMonoid<T> Eval()
    {
        if (IsReducible)
        {
            
            LimitMonoid<T> reduced_head = unreduced_part.Head().Eval();
            reduced_head.reduced_part = reduced_part * reduced_head.reduced_part;
            reduced_head.unreduced_part = reduced_head.unreduced_part * unreduced_part.Tail();
            return reduced_head;
        }
        else
        {
            return this;
        }
    }
    public LimitMonoid<T> RepeatEval(int n)
    {
        LimitMonoid<T> products = this;
        for (int k = 0; k < n; k++)
        {
            products = products.Eval();
        }
        return products;
    }
    public List<T> ReducedList
    {
        get
        {
            return reduced_part.List;
        }
    }
    private LimitMonoid<T> Prod(T y)
    {
        return new LimitMonoid<T>(reduced_part * unreduced_part * new Domain<T>(y));
    }
    private LimitMonoid<T> Prod(Domain<T> y)
    {
        return new LimitMonoid<T>(reduced_part * unreduced_part * y);
    }
    public static LimitMonoid<T> operator *(LimitMonoid<T> x, T y)
    {
        return x.Prod(y);
    }
    public static LimitMonoid<T> operator *(LimitMonoid<T> x, Domain<T> y)
    {
        return x.Prod(y);
    }
    public LimitMonoid<T> Tail()
    {
        if (reduced_part.IsNormal)
        {
            return new LimitMonoid<T>(reduced_part.Tail() * unreduced_part);
        }
        if (IsReducible)
        {
            return Eval().Tail();
        }
        return this;
    }
    private FreeMonoid<Domain<T>> Unnormalize()
    {
        return reduced_part * unreduced_part;
    }

    public LimitMonoid<T> Zip(LimitMonoid<T> y, Func<T, T, T> f)
    {
        LimitMonoid<T> x = this;
        if (!x.reduced_part.IsNormal)
        {
            x = x.Eval();
        }
        if (!y.reduced_part.IsNormal)
        {
            y = y.Eval();
        }
        T current = f(x.reduced_part.Head(), y.reduced_part.Head());
        FreeMonoid<T> reduced_part = FreeMonoid<T>.Unit(current);
        Func<LimitMonoid<T>> func = () => x.Tail().Zip(y.Tail(), f);
        FreeMonoid<Domain<T>> unreduced_part = FreeMonoid<Domain<T>>.Unit(new Domain<T>(func));
        return new LimitMonoid<T>(reduced_part * unreduced_part);
    }
}

生成元クラス

public class Domain<T>
{
    private enum ValueType { IsIrreducible, IsReducible, IsFailure };
    private ValueType value_type;
    private T irreducible_element;
    private Func<LimitMonoid<T>> redicible_element;
    private Domain()
    {
        value_type = ValueType.IsFailure;
    }
    public Domain(T element)
    {
        value_type = ValueType.IsIrreducible;
        irreducible_element = element;
    }
    public Domain(Func<LimitMonoid<T>> func)
    {
        value_type = ValueType.IsReducible;
        this.redicible_element = func;
    }
    public static Domain<T> Failure
    {
        get
        {
            return new Domain<T>();
        }
    }
    public Func<LimitMonoid<T>> ReducibleOne
    {
        get
        {
            return redicible_element;
        }
    }
    public T IrreducibleOne
    {
        get
        {
            return irreducible_element;
        }
    }
    public bool IsIrreducible { get => value_type == ValueType.IsIrreducible; }
    public bool IsReducible { get => value_type == ValueType.IsReducible; }
    public bool IsFailure { get => value_type == ValueType.IsFailure; }

    public LimitMonoid<T> Eval()
    {
        return redicible_element();
    }
    public static Domain<T> operator +(Domain<T> x, Domain<T> y)
    {
        if (x.IsFailure || y.IsFailure)
        {
            return Failure;
        }
        else if (x.IsReducible || y.IsReducible)
        {
            return Failure;
        }
        else if (x.irreducible_element == null || y.irreducible_element == null)
        {
            return Failure;
        }
        else if (x.irreducible_element is int intx && y.irreducible_element is int inty)
        {
            return new Domain<T>((T)Convert.ChangeType(intx + inty, typeof(T)));
        }
        else
        {
            return Failure;
        }
    }
}

引数で渡すバージョン

    private static LimitMonoid<int> FibonacciLimitMonoidPrms(int x, int y)
    {
        LimitMonoid<int> u = LimitMonoid<int>.Unit(x);
        Domain<int> f = new Domain<int>(() => FibonacciLimitMonoidPrms(y, x + y));
        return (LimitMonoid<int>)(u * f);
    }
    private static LimitMonoid<int> FibonacciLimitMonoidEvalPrms(int n, int x, int y)
    {
        LimitMonoid<int> fib = LimitMonoid<int>.Unit(() => FibonacciLimitMonoidPrms(x, y));
        return fib.RepeatEval(n);
    }

Zip を使うバージョン

    private static LimitMonoid<int> FibonacciLimitMonoidZip()
    {
        LimitMonoid<int> zero = LimitMonoid<int>.Unit(0);
        Domain<int> f = new Domain<int>(() => FibonacciLimitMonoidZip().Zip(FibonacciLimitMonoidZip().Tail(), (a, b) => a + b));
        return (LimitMonoid<int>)(zero * 1 * f);
    }
    private static LimitMonoid<int> FibonacciLimitMonoidEvalZip(int n)
    {
        LimitMonoid<int> fib = LimitMonoid<int>.Unit(() => FibonacciLimitMonoidZip());
        return fib.RepeatEval(n);
    }