Higher Order Functions return type

Hello :),

I have been using the Collections Package and have been enjoying it a lot. I do though, have one aspect that I find not so great about working with the data structures.
You can see it in the following example:

let students: OrderedSet = ["Kofi", "Abena", "Peter", "Kweku", "Akosua"]
let descendingStudents = students.sorted(by: >)

The type of descendingStudents is [String]. I would have expected the type to be OrderedSet<String>. This also applies to other functions like map(_:), reduce(_:_:) and filter(_:).
Is this something that is planned to be changed in the future?

1 Like

What you're describing is a "higher-kinded type", where a generic parameter can appear on the left of a type constructor: Kind (type theory) - Wikipedia

So you want something like

func map<T : •<•>, Input, Output>(_: T<Input>, _: (Input) -> Output) -> T<Output> {}

Another formulation that I believe is mostly equivalent is generic associated types. It does add a fair amount of complexity to the language and is somewhat tricky to design and implement though.

Another thing to note is that it doesn't make sense for all Collection types. When you call sorted(by:) on a Set, you probably don't want to have the return type be Set.

For something like sorted(by:) where the result type doesn't change, you can actually use a plain old associated type:

protocol SortableCollection {
  associatedtype Element
  associatedtype Sorted : SortableCollection where Sorted.Element == Element

  func sorted(by: (Element, Element) -> Bool) -> Sorted
}
1 Like

Everything @Slava_Pestov has said, but also consider that the result of mapping over a set doesn’t have to have unique elements and thus wouldn’t make sense to be of set type, etc. There are a number of prior discussions on this topic you can search for in these forums.

To answer your question directly though: no change is planned, nor likely to be planned even in the far future.

Note, OrderedSet implements in-place sort(), and has value semantics, so you can achieve your goal by making a mutable copy and sorting it in-place:

let students: OrderedSet = ["Kofi", "Abena", "Peter", "Kweku", "Akosua"]
var descendingStudents = student
descendingStudents.sorted(by: >)

OrderedSet doesn't have a version that returns a new sorted copy but you can can wrap the above code to do that too:

extension OrderedSet {
    func sorted(
        by areInIncreasingOrder: (Element, Element) throws -> Bool
    ) rethrows -> Self {
        var other = self
        try other.sort(by: areInIncreasingOrder)
        return other
    }
}

Same goes for filter, but not map for the reasons @xwu gives. As to reduce... that already works, because reduce returns an arbitrary value.

(incidentally, it's an interesting question whether OrderedSet is the only common data structure that supports the existence of a Swappable protocol between Collection and MutableCollection... being the only collection I know of where you can swap elements but not change them)