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

[LINQ via C# series]

[Lambda Calculus via C# series]

Latest version:

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.


// 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.


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>>>
                (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) =>
                (_ => node)
                (_ => new Tuple<Boolean, Tuple<T, ListNode2<T>>>(node).Item2().Item2());


The same as previous part as well:

Index2 = λl.λi.i Next2 l


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:

public class ChurchList2Tests
    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());

    public void NullIsNullTest()
        ListNode2<int> node = ChurchList2.Create(1)(ChurchList2.Null);

    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()));

1 Comment

Add a Comment

As it will appear on the website

Not displayed

Your website