[LINQ via C# series]

[Lambda Calculus via C# series]

Latest version: https://weblogs.asp.net/dixin/lambda-calculus-via-csharp-5-list

Previous part encoded Church list with one Church pair (2-tuple) as a list node. An alternative way is to use 2 tuples as a node, one wrapping the other.

• Outer tuple’s Item1 will be the null flag (a Church Boolean value to indicate this node is null or not)
• Outer tuple’s Item2 is the inner tuple:
  • Inner tuple’s Item1 is the value of this node
  • Inner tuple’s Item2 is the next node

IsNull and Null

Above definition can immediately have:

IsNull2 = λl.(Item1 l)

So Null is easy to be defined to:

Null2 = λf.True

just returns True no matter what, which also guarantees above IsNull works.

C#:

// ListNode2 is the alias of Tuple<Boolean, Tuple<T, ListNode2<T>>>
public delegate object ListNode2<out T>(Boolean<Boolean, Tuple<T, ListNode2<T>>> f);

public static partial class ChurchList2
{
    // Null = f => ChurchBoolean.True
    public static object Null<T>
        (Boolean<Boolean, Tuple<T, ListNode2<T>>> f) => new Boolean(ChurchBoolean.True);

    // IsNull = node => node.Item1()
    public static Boolean IsNull<T>
        (this ListNode2<T> node) => new Tuple<Boolean, Tuple<T, ListNode2<T>>>(node).Item1();
}

Create, Value, and Next

Again from to above definitions:

CreateListNode2 = λv.λn.CreateTuple False (CreateTuple v n)
Value2 = λl.Item1 (Item2 l)
Next2 = λl.If (IsNull2 l) (λx.l) (λx.(Item2 (Item2 l)))

Next uses If again to return Null as its next node, the same as previous Church list implemented by 1 Church pair for each node.

C#:

public static partial class ChurchList2
{
    // Create = value => next => ChurchTuple.Create(ChurchBoolean.False)(ChurchTuple.Create(value)(next))
    public static Func<ListNode2<T>, ListNode2<T>> Create<T>
        (T value) => next =>
            new ListNode2<T>(ChurchTuple.Create<Boolean, Tuple<T, ListNode2<T>>>
                (ChurchBoolean.False)
                (ChurchTuple.Create<T, ListNode2<T>>(value)(next)));

    // Value = node => node.Item2().Item1()
    public static T Value<T>
        (this ListNode2<T> node) => new Tuple<Boolean, Tuple<T, ListNode2<T>>>(node).Item2().Item1();

    // Next = node => ChurchBoolean.If(node.IsNull())(_ => node)(_ => node.Item2().Item2())
    public static ListNode2<T> Next<T>
        (this ListNode2<T> node) =>
            ChurchBoolean.If<ListNode2<T>>(node.IsNull())
                (_ => node)
                (_ => new Tuple<Boolean, Tuple<T, ListNode2<T>>>(node).Item2().Item2());
}

Index

The same as previous part as well:

Index2 = λl.λi.i Next2 l

C#:

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

Unit tests

Again, the same thing as previous part:

[TestClass()]
public class ChurchList2Tests
{
    [TestMethod()]
    public void CreateValueNextTest()
    {
        ListNode2<int> node1 = ChurchList2.Create(1)(ChurchList2.Null);
        ListNode2<int> node2 = ChurchList2.Create(2)(node1);
        ListNode2<int> node3 = ChurchList2.Create(3)(node2);
        Assert.AreEqual(1, node1.Value());
        Assert.AreEqual(ChurchList2.Null, node1.Next());
        Assert.AreEqual(2, node2.Value());
        Assert.AreEqual(node1, node2.Next());
        Assert.AreEqual(3, node3.Value());
        Assert.AreEqual(node2, node3.Next());
        Assert.IsTrue(new ListNode2<object>(ChurchList2.Null).Next().IsNull()._Unchurch());
    }

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

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