LISP-like list class

Question

So, here's my code:

public class NList : SExp, IEnumerable<Object>
{
    private Object _car;
    private NList _cdr;

    IEnumerator<Object> IEnumerable<Object>.GetEnumerator()
    {
        return new NListEnumerator(this);
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return new NListEnumerator(this);
    }

    public object car ()
    {
        return _car;
    }

    public NList cdr ()
    {
        return _cdr;
    }

    public NList cons (object o)
    {
        return new NList(o, this);
    }

    public NList() // empty list
    {

    }

    public NList(List<Object> lst)
    {
        if (lst.Count == 1)
        {
            this._car = lst[0];
            this._cdr = null;
        }
        else
        {
            this._car = lst[0];
            this._cdr = new NList(lst.GetRange(1, lst.Count - 1));
        }
    }

    public NList (Object fst)
    {
        this._car = fst;
        this._cdr = null;
    }

    public NList (Object fst, NList rst)
    {
        this._car = fst;
        this._cdr = rst;
    }

    public object Last()
    {
        NList list = this;
        while(list.cdr() != null)
        {
            list = list.cdr();
        }
        return list.car();
    }

    public int Count { get { return this.length(); } }

    public int length()
    {
        if (this._car == null && this._cdr == null) return 0;
        NList list = this;
        int len = 1;
        while(list.cdr() != null)
        {
            list = list.cdr();
            len++;
        }       
        return len;
    }

    public NList cddr()
    {
        return this.cdr().cdr();
    }

    public object cadr()
    {
        return this.cdr().car();
    }

    public object elm(int k)
    {
        if(k == 0) return car();
        NList list = cdr();
        for(int i = 1; i < k; i++, list = list.cdr()) ;
        return list.car();
    }


    public NList append(NList lst)
    {
        NList lst1 = this;
        NList lst2 = lst;
        if (this._car == null && this._cdr == null)
            return lst2;
        foreach(var e in Reverse(lst1))
        {
            lst2 = lst2.cons(e);
        }
        return lst2;
        //return lst1.Aggregate(lst2, (NList acc, object b) => acc);
    }

    public static NList Reverse(NList lst)
    {
        NList l = lst;
        NList res = null;
        while(l != null)
        {
            res = new NList(l.car(), res);
            l = l.cdr();
        }
        return res;
    }

    public override string ToString ()
    {
        if (this._car == null && this._cdr == null) return "()";
        string s = "(";
        for(int i = 0; i<this.Count-1; i++)
        {
            s+=this.elm(i).ToString() + " ";
        }
        s+=this.Last().ToString() + ")";
        return s;
    }
    public NObj[] ToNObjArray()
    {
        NObj[] a = new NObj[this.Count];
        int k = 0;
        foreach (var e in this)
        {
            a[k] = (e as NObj);
            k++;
        }
        return a;
    }
    public object[] ToArray()
    {
        object[] a = new object[this.Count];
        int k = 0;
        foreach(var e in this)
        {
            a[k] = e;
            k++;
        }
        return a;
    }
}

public class NListEnumerator : IEnumerator<Object>, IEnumerator
{
    NList list;
    NList tmp;
    public void Dispose()
    {
    }
    public NListEnumerator(NList list)
    {
        this.list = list;
        this.tmp = list.cons(null);
    }

    public object Current
    {
        get { return tmp.car(); }
    }

    public bool MoveNext()
    {
        tmp = tmp.cdr();
        return (tmp != null);
    }

    public void Reset()
    {
        tmp = list.cons(null);
    }
}

I am kinda worried that I have no separate class for simple pairs (eg: non-properly terminated lists like (1 . 2), (a . b)). Should I create a separate class (and an interface for both classes), or should I try to expand this one?

TIA.

Answer 1

There is a serious flaw in your handling of the empty list. A user would expect that these definitions are equivalent, but they ain't:

Nlist n1 = new NList("x");
Nlist n2 = new NList("x", new NList());

I strongly recommend to have an explicit subclass for the empty list (possibly a singleton) and to prohibit null for _cdr.

Answer 2

Should I create a separate class (and an interface for both classes), or should I try to expand this one?

In real LISP there is no separate representation for lists. List is just a chain of dotted pairs actually. So, I think, it's better to modify the original class and allow assigning list's cdr to anything other than NList.

By the way, why not just use properties for this:

public object car ()
{
    return _car;
}

public NList cdr ()
{
    return _cdr;
}

Also, if you already have class SExp, it may be a good idea to return SExp instead of object here.

Answer 3

Review

^{Note that I'm using arrow notation which was not available back then. But that does not impact the issues addresses in this review.}

Method overload resolution allows an explicitly implemented interface method to call the implicitly one:

IEnumerator IEnumerable.GetEnumerator()
{
    return new NListEnumerator(this);
}

IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();

Use properties for getters, and pascal-case naming convention.

public object car ()
{
    return _car;
}

public NList cdr ()
{
    return _cdr;
}

public object Car => _car;

public NList Cdr =>_cdr; // TODO and favour using a fully qualified name over an abbreviation

The factory method should be made static and use naming conventions.

public NList cons (object o)
{
    return new NList(o, this);
}

public static NList Construct(object o) => new NList(o, this);

Extract all common steps out the branches to have more DRY code.

public NList(List<Object> lst)
{
    if (lst.Count == 1)
    {
        this._car = lst[0];
        this._cdr = null;
    }
    else
    {
        this._car = lst[0];
        this._cdr = new NList(lst.GetRange(1, lst.Count - 1));
    }
}

public NList(List<Object> lst)
{
    _car = lst.FirstOrDefault();
    if (lst.Count > 1)
    {
        _cdr = new NList(lst.GetRange(1, lst.Count - 1));
    }
}

Use constructor overloads.

public NList (Object fst)
{
    this._car = fst;
    this._cdr = null;
}

public NList (Object fst) : this (fst, null)
{
}

There is no need for the function length. Put the logic behind property Count.