Re: an adventure: a Lisp-style linked list

Ethan Carter <[email protected]> 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)