adts2.py

adts2.py

# mypy 1.8.0, python 3.12
# supports recursion + generics unlike (https://gist.github.com/hanshoglund/cd4302f2c1e07370649b5983bead320e)
# OTOH, no exhaustive checks in match clasuses. And issues like: https://gist.github.com/hanshoglund/d255b3a9ff0a07cf7504a3b4313d6d7c
#
# Note: if we ONLY use frozen dataclasses as here, we have Eq,Ord,Show,Hashable, so the need for ad-hoc polymorphism is greatly reduced
from typing import Generic, TypeVar, final
from typing import Callable
from dataclasses import dataclass

T = TypeVar("T")

class List(Generic[T]): ...

@final
@dataclass(frozen=True)
class Cons(List[T]):
    car: T
    cdr: List[T]

@final
class Nil(List): ...


T1 = TypeVar("T1")
S = TypeVar("S")

def foldr(fn: Callable[[S, T1], T1], acc: T1, lst: List[S]) -> T1:
    match lst:
        case Nil():
            return acc

        case Cons(x, xs):
            return fn(x, foldr(fn, acc, xs))
    assert False