Lambda Calculus via C# (16) Encoding Church List with 2 Church Pairs as a Node

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:

1
IsNull2 = λl.(Item1 l)

So Null is easy to be defined to:

1
Null2 = λf.True

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

C#:

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

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

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

Create, Value, and Next#

Again from to above definitions:

1
CreateListNode2 = λv.λn.CreateTuple False (CreateTuple v n)
2
Value2 = λl.Item1 (Item2 l)
3
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#:

1
public static partial class ChurchList2
2
{
3
    // Create = value => next => ChurchTuple.Create(ChurchBoolean.False)(ChurchTuple.Create(value)(next))
4
    public static Func<ListNode2<T>, ListNode2<T>> Create<T>
5
        (T value) => next =>
6
            new ListNode2<T>(ChurchTuple.Create<Boolean, Tuple<T, ListNode2<T>>>
7
                (ChurchBoolean.False)
8
                (ChurchTuple.Create<T, ListNode2<T>>(value)(next)));
9

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

14
    // Next = node => ChurchBoolean.If(node.IsNull())(_ => node)(_ => node.Item2().Item2())
15
    public static ListNode2<T> Next<T>
16
        (this ListNode2<T> node) =>
17
            ChurchBoolean.If<ListNode2<T>>(node.IsNull())
18
                (_ => node)
19
                (_ => new Tuple<Boolean, Tuple<T, ListNode2<T>>>(node).Item2().Item2());
20
}

Index#

The same as previous part as well:

1
Index2 = λl.λi.i Next2 l

C#:

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

Unit tests#

Again, the same thing as previous part:

1
[TestClass()]
2
public class ChurchList2Tests
3
{
4
    [TestMethod()]
5
    public void CreateValueNextTest()
6
    {
7
        ListNode2<int> node1 = ChurchList2.Create(1)(ChurchList2.Null);
8
        ListNode2<int> node2 = ChurchList2.Create(2)(node1);
9
        ListNode2<int> node3 = ChurchList2.Create(3)(node2);
10
        Assert.AreEqual(1, node1.Value());
11
        Assert.AreEqual(ChurchList2.Null, node1.Next());
12
        Assert.AreEqual(2, node2.Value());
13
        Assert.AreEqual(node1, node2.Next());
14
        Assert.AreEqual(3, node3.Value());
15
        Assert.AreEqual(node2, node3.Next());
16
        Assert.IsTrue(new ListNode2<object>(ChurchList2.Null).Next().IsNull()._Unchurch());
17
    }
18

19
    [TestMethod()]
20
    public void NullIsNullTest()
21
    {
22
        ListNode2<int> node = ChurchList2.Create(1)(ChurchList2.Null);
23
        Assert.IsTrue(ChurchList2.IsNull<object>(ChurchList2.Null)._Unchurch());
24
        Assert.IsFalse(node.IsNull()._Unchurch());
25
    }
26

27
    [TestMethod()]
28
    public void IndexTest()
29
    {
30
        ListNode2<int> node1 = ChurchList2.Create(1)(ChurchList2.Null);
31
        ListNode2<int> node2 = ChurchList2.Create(2)(node1);
32
        ListNode2<int> node3 = ChurchList2.Create(3)(node2);
33
        Assert.AreEqual(node3, node3.Index(0U._Church()));
34
        Assert.AreEqual(node2, node3.Index(1U._Church()));
35
        Assert.AreEqual(node1, node3.Index(2U._Church()));
36
        Assert.IsTrue(node3.Index(3U._Church()).IsNull()._Unchurch());
37
        Assert.IsTrue(node3.Index(4U._Church()).IsNull()._Unchurch());
38
        Assert.IsTrue(node3.Index(5U._Church()).IsNull()._Unchurch());
39
    }
40
}