Lambda Calculus via C# (17) Encoding Church List with Fold (Aggregate) Function

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

ListNode and wrapper#

According to the definition, this is the ListNode in C#:

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

f is the fold/aggregate function. In .NET aggregate function is a Func<TAccumulate, T, TAccumulate>, here in lambda calculus it is curried to Func<TAccumulate, Func<T, TAccumulate>.

Just like the Church numeral wrapper _Numeral, a wrapper is needed to hide TAccumulate “inside”:

1
public partial class _ListNode<T>
2
{
3
    private readonly T value;
4

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

7
    public _ListNode(T value, _ListNode<T> next)
8
    {
9
        this.value = value;
10
        this.Next = next;
11
    }
12

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

Again, class name is tagged with underscore since class is C# specific.

Null is a special case, so, exactly the same way how 0 is handled in Church numeral:

1
public partial class _ListNode<T>
2
{
3
    private _ListNode()
4
    {
5
    }
6

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

11
        public override ListNode<T, TAccumulate> Node<TAccumulate>
12
            () =>
13
                f => x => x;
14
    }
15

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

IsNull#

Null is _ListNode.Null, so IsNull function is easy to implement:

1
public static partial class _ListNodeExtensions
2
{
3
    // IsNull = node => node(value => _ => ChurchBoolean.False)(ChurchBoolean.True)
4
    public static Boolean IsNull<T>
5
        (this _ListNode<T> node) =>
6
            node.Node<Boolean>()(value => _ => ChurchBoolean.False)(ChurchBoolean.True);
7
}

IsNull predicate is similar to the IsNull of Church list encoded with 1 tuple as each node.

Create, value and Next#

1
public static partial class _ListNodeExtensions
2
{
3
    // Create = value => next => f => x => f(value)(next(f)(x))
4
    public static Func<_ListNode<T>, _ListNode<T>> Create<T>
5
        (T value) => next => new _ListNode<T>(value, next);
6
// Value = node => anyValueToIgnore => node(value => _ => value)(anyValueToIgnore)
7
    public static T Value<T>
8
        (this _ListNode<T> node, T anyValueToIgnore = default(T)) =>
9
            node.Node<T>()(_ => value => value)(anyValueToIgnore);
10

11
    // Next = node => node(value => tuple => tuple.Shift(Create(value)))(ChurchTuple.Create(Null)(Null)).Item1()
12
    public static _ListNode<T> Next<T>
13
        (this _ListNode<T> node) =>
14
            node.Node<Tuple<_ListNode<T>, _ListNode<T>>>()
15
                (tuple => value => tuple.Shift(Create(value)))
16
                (ChurchTuple.Create<_ListNode<T>, _ListNode<T>>(_ListNode<T>.Null)(_ListNode<T>.Null))
17
                .Item1();
18
}

Next is tricky but the same way as Church numeral’s Decrease2, which version with shifting the tuple.

Index#

The same as other list encodings:

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

Unit tests#

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

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

27
    [TestMethod()]
28
    public void IndexTest()
29
    {
30
        _ListNode<int> node1 = _ListNodeExtensions.Create(1)(_ListNodeExtensions.GetNull<int>());
31
        _ListNode<int> node2 = _ListNodeExtensions.Create(2)(node1);
32
        _ListNode<int> node3 = _ListNodeExtensions.Create(3)(node2);
33
        Assert.AreEqual(node3.Value(), node3.Index(0U._Church()).Value());
34
        Assert.AreEqual(node2.Value(), node3.Index(1U._Church()).Value());
35
        Assert.AreEqual(node1.Value(), node3.Index(2U._Church()).Value());
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
}