sort.py

from collections.abc import Callable
from dataclasses import dataclass
from typing import Protocol, Self


def curry[First, *Rest, Result](
    function: Callable[[First, *Rest], Result],
) -> Callable[[*Rest], Callable[[First], Result]]:
    return lambda *rest: lambda first: function(first, *rest)


type Ordering = Worse | Equal | Better


@dataclass(frozen=True)
class Worse:
    pass


@dataclass(frozen=True)
class Equal:
    pass


@dataclass(frozen=True)
class Better:
    pass


def ordering_worse(ordering: Ordering) -> bool:
    match ordering:
        case Worse():
            return True
        case _:
            return False


def ordering_not_worse(ordering: Ordering) -> bool:
    match ordering:
        case Worse():
            return False
        case _:
            return True


def ordering_reverse(ordering: Ordering) -> Ordering:
    match ordering:
        case Worse():
            return Better()
        case Equal():
            return Equal()
        case Better():
            return Worse()


ordering_neutral = Equal()


@curry
def ordering_add(first: Ordering, second: Ordering) -> Ordering:
    match first:
        case Equal():
            return second
        case _:
            return first


type Order[T] = Callable[[T], Callable[[T], Ordering]]


@curry
@curry
def worse[T](first: T, second: T, order: Order[T]) -> bool:
    return ordering_worse(order(second)(first))


@curry
@curry
def not_worse[T](first: T, second: T, order: Order[T]) -> bool:
    return ordering_not_worse(order(second)(first))


@curry
@curry
def order_reverse[T](first: T, second: T, order: Order[T]) -> Ordering:
    return ordering_reverse(order(second)(first))


@curry
@curry
def order_neutral[T](first: T, second: T) -> Ordering:
    return ordering_neutral


@curry
@curry
@curry
def order_add[T](
    first: T, second: T, order_first: Order[T], order_second: Order[T]
) -> Ordering:
    return ordering_add(order_second(second)(first))(order_first(second)(first))


@curry
@curry
@curry
def order_map[From, To](
    first: To, second: To, order: Order[From], function: Callable[[To], From]
) -> Ordering:
    return order(function(second))(function(first))


@curry
def filter[T](list: list[T], condition: Callable[[T], bool]) -> list[T]:
    match list:
        case [head, *tail]:
            return ([head] if condition(head) else []) + filter(condition)(tail)
        case _:
            return []


@curry
def sort[T](list: list[T], order: Order[T]) -> list[T]:
    match list:
        case [head, *tail]:
            bad = filter(worse(order)(head))(tail)
            good = filter(not_worse(order)(head))(tail)
            return sort(order)(bad) + [head] + sort(order)(good)
        case _:
            return []


class SupportsRichComparison(Protocol):
    def __lt__(self, other: Self, /) -> bool: ...

    def __gt__(self, other: Self, /) -> bool: ...


@curry
def dunder_order[T: SupportsRichComparison](first: T, second: T) -> Ordering:
    if first > second:
        return Better()
    if first < second:
        return Worse()
    return Equal()


dunder_order_reversed = order_reverse(dunder_order)


@dataclass(frozen=True)
class User:
    name: str
    age: int


def get_user_name(user: User) -> str:
    return user.name


def get_user_age(user: User) -> int:
    return user.age


user_order_by_name = order_map(get_user_name)(dunder_order)


user_order_by_age = order_map(get_user_age)(dunder_order)


user_order = order_add(user_order_by_age)(user_order_by_name)


user_order_reversed = order_reverse(user_order)


user_sort = sort(user_order)


user_sort_reversed = sort(user_order_reversed)


users_unsorted = [
    User("Norma", 49),
    User("Rose", 46),
    User("Rose", 38),
    User("Harvey", 79),
    User("Tyrone", 44),
]


users_sorted = user_sort(users_unsorted)


users_sorted_reversed = user_sort_reversed(users_unsorted)


print(users_unsorted)
print(users_sorted)
print(users_sorted_reversed)