Cons List in Python

The best way to improve this is to change Cons to tuple. But if you don't want to do that then I'd make the code more Pythonic, and by that use class special methods. You should:

• Use __len__ rather length.
• Use __getitem__ rather than nth.
• Use __iter__ rather than manually looping, either via recursion or with a while loop through the linked list.

I'd remove the unneeded ABCMetaclass, and change Nil from a singleton to a class. This is as it can make the code slightly easier to understand.

After this you should notice that Cons is actually a node not a list, and so I'd write an interface for it to act like a list by renaming Cons to ConsNode and creating a list interface Cons.

From this I managed to get:

class Nil:
    def __len__(self):
        return 0

    def __getitem__(self, n):
        raise Exception('Out of bounds')

class ConsNode:
    """Class cons, the non empty list: (head, list)"""
    def __init__(self, _head, _tail):
        self.head = _head
        self.tail = _tail

    def __len__(self):
        return 1 + len(self.tail)

    def __iter__(self):
        current = self
        while not isinstance(current, Nil):
            yield current.head
            current = current.tail

    def __getitem__(self, n):
        if n == 0:
            return self.head
        else:
            return self.tail[n - 1]

class Cons:
    def __init__(self, args):
        """Crates immutable list from an iterable"""
        if len(args) == 0:
            return Nil()
        tmp = len(args) - 1
        def helper(xs, cnt, limit):
            if cnt > limit:
                return Nil()
            else:
                return ConsNode(xs[cnt], helper(xs, cnt + 1, limit))
        self.root = helper(args, 0, tmp)

    def __len__(self):
        return len(self.root)

    def __iter__(self):
        return iter(self.root)

    def __getitem__(self, i):
        return self.root[i]

    def __str__(self):
        return '(' + ' '.join(str(i) for i in self) + ')'

It keeps your recursion in a much easier to read fashion, and adds an abstraction to your recursion, recursion is slow, hard to understand and erroneous if the depth exceeds 1000. So I'd recommend not to use it in Python. It's not the correct language for the job.

Using the above should leave you with two functions, subs_in_expr and subst. This is as we've moved all the other ones into Python's sugar. I changed these to use the __iter__ method, and to instead use isinstance to check that the input is actually your special list. I kept the recursion between both these functions, as it makes sense to keep it. But left me with:

def subs_in_expr(new, old, xs): 
    """ this helper function works put single    
     list element which maybe list itself"""
    if isinstance(xs, Cons):
        return subst(new, old, xs)
    else:
        return new if xs == old else xs


def subst(new, old, xs):
    """substitutes new as old in a list (possible nested) """
    return Cons([subs_in_expr(new, old, n) for n in xs])

Honestly I'd suggest you'd use better variable names xs is horribly cryptic, both the genetic list or data are much better. But if you want to keep nth you'd add:

def nth(n , xs):
    """Returns nt-h (0 based indexing) elemt of the list, 
    throws an exception when out of range"""
    return xs[n]

But I'd recommend that you don't as it is removing syntactic sugar. Which leaves the main of the code to be:

l1 = Cons(range(10))
print(l1)
print(l1[3])
print(len(l1))
l2 = subst("A CAT", 0, l1)
print(l2)

Just a couple of renames on what you provided. But the best part is you can change your code to use tuple instead of Cons, and it work exactly the same. But should give better reliability and better performance. C is hands down faster than Python. And it also remove potential problematic code, that you have to maintain.

Finally the data structure that you're creating is a linked list, which is intended to be mutable, in fact the entire point of a linked list is \$O(1)\$ insertion at any point in the list, if your pointer is already there. And is used in Queues, Stacks and deques due to this benefit, that you're removing. But on the all it's a whole lot less efficient than a properly implemented datatype, and so use a tuple. Cons = tuple will allow you to remove all the classes, and keep all the functions and the module level code.