Path: csiph.com!eternal-september.org!feeder.eternal-september.org!.POSTED!not-for-mail
From: Ethan Carter <ec1828@somewhere.edu>
Newsgroups: comp.lang.python
Subject: an adventure: a Lisp-style linked list
Date: Wed, 03 Sep 2025 20:12:05 -0300
Organization: A noiseless patient Spider
Lines: 80
Message-ID: <87o6rrt9kq.fsf@somewhere.edu>
MIME-Version: 1.0
Content-Type: text/plain
Injection-Date: Wed, 03 Sep 2025 23:12:06 +0000 (UTC)
Injection-Info: dont-email.me; posting-host="ede76955dc8132a9a131d142e9702d64"; logging-data="1531185"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/UYVhclOiNJjHjn9WRAlT6FtYiJtif1zI="
Cancel-Lock: sha1:tT7uKLM4p8otHmzNN20dKFRHnqY= sha1:HiAcbooZtuzFpYYSTF9ddIQYbRw=
Xref: csiph.com comp.lang.python:197551

# -*- 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")