[Feature Request] add ducktyping between traits

[martinvuyk]

Review Mojo's priorities

• I have read the roadmap and priorities and I believe this request falls within the priorities.

What is your request?

if the trait defines all of the methods needed that are defined in another trait definition, then the compiler should accept it

What is your motivation for this change?

I was trying to implement an interface to sort and sorted similar to python's

trait ComparableCollectable:
    fn __copyinit__(inout self: Self, existing: Self):
        ...

    fn __moveinit__(inout self: Self, owned existing: Self):
        ...

    fn __del__(owned self: Self):
        ...

    fn __eq__(self: Self, other: Self) -> Bool:
        ...

    fn __ne__(self: Self, other: Self) -> Bool:
        ...

    fn __lt__(self: Self, other: Self) -> Bool:
        ...

    fn __le__(self: Self, other: Self) -> Bool:
        ...

    fn __gt__(self: Self, other: Self) -> Bool:
        ...

    fn __ge__(self: Self, other: Self) -> Bool:
        ...


# when trait declarations do support parameters
#
# trait Collection[T: ComparableCollectable, A: KeyElement]:
#     fn __getitem__(self: Self, i: A) -> T:
#         ...
#     fn __setitem__(self: Self, i: A) -> T:
#         ...
#
# that way key could be
# key: fn (Collection[T], KeyElement) -> T = List[T].__getitem__
# where for List, Set, Tuple, et al.  KeyElement is of type Int


@always_inline
fn _swap[T: ComparableCollectable](inout buf: List[T], a: Int, b: Int):
    var tmp = buf[a]
    buf[a] = buf[b]
    buf[b] = tmp


@always_inline
fn _partition[
    T: ComparableCollectable, key: fn (List[T], Int) -> T = List[T].__getitem__
](inout buf: List[T], low: Int, high: Int) -> Int:
    var pivot = key(buf, high)
    var i = low - 1
    for j in range(low, high):
        if key(buf, j) <= pivot:
            i += 1
            _swap(buf, i, j)
    _swap(buf, i + 1, high)
    return i + 1


fn _qsort[
    T: ComparableCollectable, key: fn (List[T], Int) -> T = List[T].__getitem__
](inout buf: List[T], low: Int, high: Int):
    if low < high:
        var pi = _partition[T, key](buf, low, high)
        _qsort(buf, low, pi - 1)
        _qsort(buf, pi + 1, high)


fn qsort[
    T: ComparableCollectable, key: fn (List[T], Int) -> T = List[T].__getitem__
](inout buf: List[T]):
    _qsort[T, key](buf, 0, len(buf) - 1)


fn sort[
    T: ComparableCollectable,
    max_size: Int = 999,
    key: fn (List[T], Int) -> T = List[T].__getitem__,
](inout buf: List[T]):
    if max_size == 3:
        # TODO: AlphaDev sort3..sort8
        pass
    elif False:  # type: ignore
        # TODO: other algos
        pass
    else:
        qsort(buf)


fn sorted[
    T: ComparableCollectable,
    max_size: Int = 999,
    key: fn (List[T], Int) -> T = List[T].__getitem__,
](owned buf: List[T]) -> List[T]:
    sort[T, max_size, key](buf)
    return buf


fn main():
    var items = List[Int](2, 3, 4, 5, 1, 9, 8, 7, 0)
    print(sorted(items))

Any other details?

This might also count as a proposal for adding builtin sort and sorted functions #2390