Linked List Definition In Python Using SKI Combinators

linked_list_skipy.py

from typing import Generic, Tuple, TypeVar, Iterable, List, Optional, Any

L = TypeVar("L")
R = TypeVar("R")

# SKI+ Combinators
S = lambda f: lambda g: lambda x: f(x)(g(x))
K = lambda x: lambda y: x
I = S(K)(K(K))
KI = K(I)
B = S(K(S))(K)
T = B(S(I))(K)
V = S(B(B)(B(S)(T)))(K(K))


# Definition of Pair
class Pair(Generic[L, R]):
    def __init__(self) -> None:
        raise NotImplementedError("Should not be used")

    def __call__(self, func):
        return self(func)


def mk_pair(left: L, right: R) -> Pair[L, R]:
    return V(left)(right)


def fst(p: Pair[L, R]) -> L:
    return p(K)


def snd(p: Pair[L, R]) -> R:
    return p(KI)


def unpack(p: Pair[L, R]) -> Tuple[L, R]:
    return fst(p), snd(p)


# Definition of Linked List
Node = Pair[Any, int]
LinkedList = Optional[Pair[Node, "LinkedList"]]  # type: ignore

empty: LinkedList = None


def len(linked_list: LinkedList) -> int:
    if linked_list is None:
        return 0
    return snd(fst(linked_list))


def is_empty(linked_list: LinkedList) -> bool:
    return linked_list is None


def cons(head: Any, linked_list: LinkedList) -> LinkedList:
    return mk_pair(mk_pair(head, len(linked_list) + 1), linked_list)


def head(linked_list: LinkedList) -> Optional[Any]:
    if linked_list is None:
        return None
    return fst(fst(linked_list))


def tail(linked_list: LinkedList) -> LinkedList:
    if linked_list is None:
        return None
    return snd(linked_list)


def iter(linked_list: LinkedList) -> Iterable[Any]:
    while linked_list is not None:
        yield head(linked_list)
        linked_list = tail(linked_list)


def to_python_list(linked_list: LinkedList) -> List[Any]:
    return list(iter(linked_list))


def from_iter(items: Iterable[Any]) -> LinkedList:
    ret = empty
    for item in items:
        ret = cons(item, ret)
    return ret


# Usage
if __name__ == "__main__":
    s = cons(3, cons(2, empty))  # [3, 2]
    assert head(s) == 3
    assert head(tail(s)) == 2
    s = cons(100, cons(2, cons(3, cons(45, empty))))  # [100, 2, 3, 45]
    assert head(s) == 100
    assert to_python_list(s) == [100, 2, 3, 45]
    assert to_python_list(from_iter([1, 2, 3, 4, 5])) == to_python_list(
        cons(5, cons(4, cons(3, cons(2, cons(1, empty)))))
    )