an adventure: a Lisp-style linked list

# -*- mode: python; python-indent-offset: 2 -*-

## As an exercise, I decided to implement a Lisp-style linked list
## using a class List.  I'm a bit surprised by the result: it seems
## polymorphism forces me to write a recursive procedure in two
## halves: one half in the List class itself and the other half in the
## Empty class.  For example, I created a class called Empty as a
## singleton.  So when I wrote the __len__ procedure for a List, I
## cannot treat the base case in the List.__len__ procedure because
## the base case really belongs to another class---since an empty list
## is not really a List, but rather of type Empty.

## This is because the Lisp list is really a union of two types, so
## using classes produces this situation.  What do you think?  Can you
## suggest anything beyond the obvious of ``write Python when using
## Python''?  Perhaps you do know how to implement a union in a more
## elegant way?  I'd love to see if you can workaround this in a
## prettier way.  Thanks very much.

## Usage:
## 
## >>> ls = List(0, List(1, List(2, List.Empty())))
## >>> len(ls)
## 3
## >>> ls[1]
## 1
## >>> ls[2]
## 2
## >>> ls[3]
## Traceback (most recent call last):
## [...]
## Exception: no such element

class List:
  head = None
  tail = None

  def __init__(self, d, ls):
    self.head = d
    self.tail = ls

  def getitem(self, n):
    if n == 0:
      return self.first()
    return self.rest().getitem(n - 1)

  def __getitem__(self, n):
    return self.getitem(n)
  
  def empty(self):
    return self is List.Empty()
  
  def first(self):
    return self.head

  def rest(self):
    return self.tail

  def __repr__(self):
    return f"List({self.head}, {self.rest()})"

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

  class Empty:
    instance = None

    def __new__(cls):
      if cls.instance is None:
        cls.instance = super().__new__(cls)
      return cls.instance

    def __repr__(self):
      return "List.Empty()"

    def __len__(self):
      return 0

    def getitem(self, n):
      raise Exception("no such element")