C# によるラムダ計算 (17) Fold (Aggregate) 関数を使用した教会リストのエンコード

[C# シリーズ経由の LINQ]

[C# シリーズによるラムダ計算]

最新バージョン:https://weblogs.asp.net/dixin/lambda-calculus-via-csharp-5-list

教会リストをエンコードする 3 つ目の方法は、fold 関数 (C#/.NET では集計とも呼ばれます) を使用することです:

CreateListNode3 = λv.λn.λf.λx.f v (n f x)
Null3 = λf.λx.x
IsNull3 = λl.l (λv.λx.False) True
Value3 = λl.λx.l (λv.λy.v) x
Next3 = λl.Item2 (l (λv.λt.Shift (CreateListNode3 v)) (CreateTuple Null3 Null3))
Index3 = λl.λi.i Next3 l

ListNode とラッパー

定義によると、これは C# の ListNode です:

// Curried from TResult ListNode<out T, TResult>(Func<T, TResult, TResult> f, TResult x)
public delegate Func<TAccumulate, TAccumulate> ListNode<out T, TAccumulate>(Func<TAccumulate, Func<T, TAccumulate>> f);
// ListNode is the alias of: Func<Func<T, Func<TResult, TResult>>, Func<TResult, TResult>>

f は折り畳み/集約関数です。 .NET 集計関数は Func ですが、ラムダ計算では Func にカリー化されます。

教会の数字ラッパー _Numeral と同様に、TAccumulate を「内部」に隠すにはラッパーが必要です。

public partial class _ListNode<T>
{
    private readonly T value;

    protected virtual _ListNode<T> Next { get; set; }

    public _ListNode(T value, _ListNode<T> next)
    {
        this.value = value;
        this.Next = next;
    }

    public virtual ListNode<T, TAccumulate> Node<TAccumulate>
        () => 
            f => x => f(this.Next.Node<TAccumulate>()(f)(x))(this.value);
}

ここでも、クラスは C# 固有であるため、クラス名はアンダースコアでタグ付けされています。

Null は特殊なケースであるため、教会の数字で 0 を処理する方法とまったく同じです:

public partial class _ListNode<T>
{
    private _ListNode()
    {
    }

    private class _NullListNode : _ListNode<T>
    {
        protected override _ListNode<T> Next { get { return this; } set { } }

        public override ListNode<T, TAccumulate> Node<TAccumulate>
            () => 
                f => x => x;
    }

    public static _ListNode<T> Null { get; } = new _NullListNode();
}

IsNull

Null は _ListNode.Null なので、IsNull 関数は簡単に実装できます:

public static partial class _ListNodeExtensions
{
    // IsNull = node => node(value => _ => ChurchBoolean.False)(ChurchBoolean.True)
    public static Boolean IsNull<T>
        (this _ListNode<T> node) =>
            node.Node<Boolean>()(value => _ => ChurchBoolean.False)(ChurchBoolean.True);
}

IsNull 述語は、各ノードとして 1 つのタプルでエンコードされた Church リストの IsNull に似ています。

創造、価値、そして次へ

public static partial class _ListNodeExtensions
{
    // Create = value => next => f => x => f(value)(next(f)(x))
    public static Func<_ListNode<T>, _ListNode<T>> Create<T>
        (T value) => next => new _ListNode<T>(value, next);


    // Value = node => anyValueToIgnore => node(value => _ => value)(anyValueToIgnore)
    public static T Value<T>
        (this _ListNode<T> node, T anyValueToIgnore = default(T)) =>
            node.Node<T>()(_ => value => value)(anyValueToIgnore);

    // Next = node => node(value => tuple => tuple.Shift(Create(value)))(ChurchTuple.Create(Null)(Null)).Item1()
    public static _ListNode<T> Next<T>
        (this _ListNode<T> node) =>
            node.Node<Tuple<_ListNode<T>, _ListNode<T>>>()
                (tuple => value => tuple.Shift(Create(value)))
                (ChurchTuple.Create<_ListNode<T>, _ListNode<T>>(_ListNode<T>.Null)(_ListNode<T>.Null))
                .Item1();
}

次はトリッキーですが、タプルをずらしたバージョンのチャーチ数字の Decrease2 と同じ方法です。

インデックス

他のリストエンコーディングと同じ:

public static partial class _ListNodeExtensions
{
    // Index = start => index => index(Next)(start)
    public static _ListNode<T> Index<T>
        (this _ListNode<T> start, _Numeral index) => index.Numeral<_ListNode<T>>()(Next)(start);
}

単体テスト

[TestClass()]
public class _ListNodeTests
{
    [TestMethod()]
    public void CreateValueNextTest()
    {
        _ListNode<int> node1 = _ListNodeExtensions.Create(1)(_ListNodeExtensions.GetNull<int>());
        _ListNode<int> node2 = _ListNodeExtensions.Create(2)(node1);
        _ListNode<int> node3 = _ListNodeExtensions.Create(3)(node2);
        Assert.AreEqual(1, node1.Value());
        Assert.AreEqual(_ListNodeExtensions.GetNull<int>(), node1.Next());
        Assert.AreEqual(2, node2.Value());
        Assert.AreEqual(node1.Value(), node2.Next().Value());
        Assert.AreEqual(3, node3.Value());
        Assert.AreEqual(node2.Value(), node3.Next().Value());
        Assert.IsTrue(_ListNodeExtensions.GetNull<object>().Next().IsNull()._Unchurch());
    }

    [TestMethod()]
    public void NullIsNullTest()
    {
        _ListNode<int> node = _ListNodeExtensions.Create(1)(_ListNodeExtensions.GetNull<int>());
        Assert.IsTrue(_ListNodeExtensions.GetNull<object>().IsNull()._Unchurch());
        Assert.IsFalse(node.IsNull()._Unchurch());
    }

    [TestMethod()]
    public void IndexTest()
    {
        _ListNode<int> node1 = _ListNodeExtensions.Create(1)(_ListNodeExtensions.GetNull<int>());
        _ListNode<int> node2 = _ListNodeExtensions.Create(2)(node1);
        _ListNode<int> node3 = _ListNodeExtensions.Create(3)(node2);
        Assert.AreEqual(node3.Value(), node3.Index(0U._Church()).Value());
        Assert.AreEqual(node2.Value(), node3.Index(1U._Church()).Value());
        Assert.AreEqual(node1.Value(), node3.Index(2U._Church()).Value());
        Assert.IsTrue(node3.Index(3U._Church()).IsNull()._Unchurch());
        Assert.IsTrue(node3.Index(4U._Church()).IsNull()._Unchurch());
        Assert.IsTrue(node3.Index(5U._Church()).IsNull()._Unchurch());
    }
}