Path: csiph.com!fu-berlin.de!uni-berlin.de!not-for-mail
From: ram@zedat.fu-berlin.de (Stefan Ram)
Newsgroups: comp.lang.python
Subject: Re: an adventure: a Lisp-style linked list
Date: 4 Sep 2025 00:47:38 GMT
Organization: Stefan Ram
Lines: 82
Expires: 1 Jun 2026 11:59:58 GMT
Message-ID: <lists-20250904013639@ram.dialup.fu-berlin.de>
References: <87o6rrt9kq.fsf@somewhere.edu>
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
X-Trace: news.uni-berlin.de vTTdrUphG+8NgiyxfNMgSw9VwY43dxjZeOJQACPHyO0rQS
Cancel-Lock: sha1:mDqSespa5dvLGoRCntL+hVPeYhQ= sha256:RShtcAtmFUfUADo7dpYVB3ZVYV7wIXEqVZIPx2WzhrA=
X-Copyright: (C) Copyright 2025 Stefan Ram. All rights reserved. Distribution through any means other than regular usenet channels is forbidden. It is forbidden to publish this article in the Web, to change URIs of this article into links, and to transfer the body without this notice, but quotations of parts in other Usenet posts are allowed.
X-No-Archive: Yes
Archive: no
X-No-Archive-Readme: "X-No-Archive" is set, because this prevents some services to mirror the article in the web. But the article may be kept on a Usenet archive server with only NNTP access.
X-No-Html: yes
Content-Language: en
Xref: csiph.com comp.lang.python:197552

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)