From Newsgroup: comp.lang.python

# -*- 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")
--- Synchronet 3.21a-Linux NewsLink 1.2

From Newsgroup: comp.lang.python

Ethan Carter <ec1828@somewhere.edu> wrote or quoted:

## 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:

I think this lies in the nature of lists, as the rest can
have at least two types: it might be another list or empty.

## Can you
## suggest anything beyond the obvious of ``write Python when using
## Python''?

I'd use a two-layered approach:

- CONS (dotted pairs), CAR, CDR, NIL and NULL as the lower layer

- lists on top of that.

from __future__ import annotations
from abc import ABC, abstractmethod
from dataclasses import dataclass
from typing import Any

# Layer 0: CONS, CAR, CDR, and NIL

class Object( ABC ): # common interface for CONS and NIL

@abstractmethod
def null( self ) -> bool: ...

@dataclass( frozen=True )
class Cons( Object ): # dotted pairs

car: Any
cdr: Any

def null( self ) -> bool:
return False

@dataclass( frozen=True )
class Nil( Object ):

def null( self )-> bool:
return True

nil: Nil = Nil() # singleton

def null( x: Object ) -> bool:
return x.null()

# Layer 1: lists

def make_list( *args: Any )-> Object:
result: Object = nil
for arg in reversed( args ):
result = Cons( arg, result )
return result

def print_list( lst: Object )-> None:
print( end="(" )
current = lst
first = True
while not null( current ):
assert isinstance( current, Cons )
if not first: print( end=" " )
print( end=str( current.car ))
current = current.cdr
first = False
print( end=")" )

# A perfect LISP imitation would also have special LISP-like int
# objects, but for brevity's sake, here, I just use Python's ints.

l = make_list( 1, 2, 3 )
print_list( l )

prints:

(1 2 3)


--- Synchronet 3.21a-Linux NewsLink 1.2

From Newsgroup: comp.lang.python

Ethan Carter <ec1828@somewhere.edu> wrote:

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

Why not
def __init__(self, d, ls=None):

and avoid the need for a List.Empty ?
--
pa at panix dot com
--- Synchronet 3.21a-Linux NewsLink 1.2

From Newsgroup: comp.lang.python

pa@see.signature.invalid (Pierre Asselin) writes:

Ethan Carter <ec1828@somewhere.edu> wrote:

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

Why not
def __init__(self, d, ls=None):

and avoid the need for a List.Empty ?

Thanks! That's a good suggestion.
--- Synchronet 3.21a-Linux NewsLink 1.2