Skip to content

Instantly share code, notes, and snippets.

@Sinha-Ujjawal
Last active September 25, 2022 08:15
Show Gist options
  • Save Sinha-Ujjawal/034b1253b6fd4fb6200e436815c6f784 to your computer and use it in GitHub Desktop.
Save Sinha-Ujjawal/034b1253b6fd4fb6200e436815c6f784 to your computer and use it in GitHub Desktop.
Linked List Definition In Python Using SKI Combinators
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)))))
)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment