sortBy, minElementBy and maxElementBy methods


#1

Consider the follows:

struct Person {

    var name: String

    var age: Int

}

let peoples = [Person(name: "Hawk", age: 24), Person(name: "Andrew", age: 23
)]

let youngest = peoples.minElement { $0.age < $1.age }

print(youngest?.name)

it's silly that we always have to write the code like { $0.some < $1.some }
or { some($0) < some($1) }

so, we should add those methods to stdlib:

extension SequenceType {

    /// Returns the minimum element in `self` or `nil` if the sequence is
empty.

    ///

    /// - Complexity: O(`elements.count`).

    ///

    @warn_unused_result

    public func minElement<R : Comparable>(@noescape by:
(Generator.Element) throws -> R) rethrows -> Generator.Element? {

        return try self.minElement { try by($0) < by($1) }

    }

    /// Returns the maximum element in `self` or `nil` if the sequence is
empty.

    ///

    /// - Complexity: O(`elements.count`).

    ///

    @warn_unused_result

    public func maxElement<R : Comparable>(@noescape by:
(Generator.Element) throws -> R) rethrows -> Generator.Element? {

        return try self.maxElement { try by($0) < by($1) }

    }

}

public extension MutableCollectionType {

    /// Return an `Array` containing the sorted elements of `source`.

    /// according to `by`.

    ///

    /// The sorting algorithm is not stable (can change the relative order
of

    /// elements that compare equal).

    @warn_unused_result(mutable_variant="sortInPlace")

    func sort<R : Comparable>(@noescape by: (Generator.Element) -> R) -> [
Generator.Element] {

        return self.sort { by($0) < by($1) }

    }

}

public extension MutableCollectionType where Self.Index :
RandomAccessIndexType {

    /// Sort `self` in-place according to `by`.

    ///

    /// The sorting algorithm is not stable (can change the relative order
of

    /// elements that compare equal).

    mutating func sortInPlace<R : Comparable>(@noescape by: (Generator.
Element) -> R) {

        self.sortInPlace { by($0) < by($1) }

    }

}


(Jacob Bandes-Storch) #2

+1, although I wonder if the method names should be distinct (such as
minElementBy, sortBy, etc.)

···

On Wed, Dec 30, 2015 at 10:38 PM, Susan Cheng via swift-evolution < swift-evolution@swift.org> wrote:

Consider the follows:

struct Person {

    var name: String

    var age: Int

}

let peoples = [Person(name: "Hawk", age: 24), Person(name: "Andrew", age:
23)]

let youngest = peoples.minElement { $0.age < $1.age }

print(youngest?.name)

it's silly that we always have to write the code like { $0.some < $1.some }
or { some($0) < some($1) }

so, we should add those methods to stdlib:

extension SequenceType {

    /// Returns the minimum element in `self` or `nil` if the sequence is
empty.

    ///

    /// - Complexity: O(`elements.count`).

    ///

    @warn_unused_result

    public func minElement<R : Comparable>(@noescape by:
(Generator.Element) throws -> R) rethrows -> Generator.Element? {

        return try self.minElement { try by($0) < by($1) }

    }

    /// Returns the maximum element in `self` or `nil` if the sequence is
empty.

    ///

    /// - Complexity: O(`elements.count`).

    ///

    @warn_unused_result

    public func maxElement<R : Comparable>(@noescape by:
(Generator.Element) throws -> R) rethrows -> Generator.Element? {

        return try self.maxElement { try by($0) < by($1) }

    }

}

public extension MutableCollectionType {

    /// Return an `Array` containing the sorted elements of `source`.

    /// according to `by`.

    ///

    /// The sorting algorithm is not stable (can change the relative
order of

    /// elements that compare equal).

    @warn_unused_result(mutable_variant="sortInPlace")

    func sort<R : Comparable>(@noescape by: (Generator.Element) -> R) -> [
Generator.Element] {

        return self.sort { by($0) < by($1) }

    }

}

public extension MutableCollectionType where Self.Index :
RandomAccessIndexType {

    /// Sort `self` in-place according to `by`.

    ///

    /// The sorting algorithm is not stable (can change the relative
order of

    /// elements that compare equal).

    mutating func sortInPlace<R : Comparable>(@noescape by: (Generator.
Element) -> R) {

        self.sortInPlace { by($0) < by($1) }

    }

}

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Dave Abrahams) #3

Why add all those algorithms when you can write this

func byComparing<T, U: Comparable>(getComparisonKey: (T)->U) -> (T, T) -> Bool {
  return { getComparisonKey($0) < getComparisonKey($1) }
}

peoples.sort(byComparing { $0.name })

?

-Dave

···

On Dec 30, 2015, at 10:38 PM, Susan Cheng via swift-evolution <swift-evolution@swift.org> wrote:

Consider the follows:

struct Person {
    
    var name: String
    var age: Int
}

let peoples = [Person(name: "Hawk", age: 24), Person(name: "Andrew", age: 23)]

let youngest = peoples.minElement { $0.age < $1.age }

print(youngest?.name)

it's silly that we always have to write the code like { $0.some < $1.some } or { some($0) < some($1) }

so, we should add those methods to stdlib:

extension SequenceType {
    /// Returns the minimum element in `self` or `nil` if the sequence is empty.
    ///
    /// - Complexity: O(`elements.count`).
    ///
    @warn_unused_result
    public func minElement<R : Comparable>(@noescape by: (Generator.Element) throws -> R) rethrows -> Generator.Element? {
        return try self.minElement { try by($0) < by($1) }
    }
    /// Returns the maximum element in `self` or `nil` if the sequence is empty.
    ///
    /// - Complexity: O(`elements.count`).
    ///
    @warn_unused_result
    public func maxElement<R : Comparable>(@noescape by: (Generator.Element) throws -> R) rethrows -> Generator.Element? {
        return try self.maxElement { try by($0) < by($1) }
    }
}

public extension MutableCollectionType {
    
    /// Return an `Array` containing the sorted elements of `source`.
    /// according to `by`.
    ///
    /// The sorting algorithm is not stable (can change the relative order of
    /// elements that compare equal).
    @warn_unused_result(mutable_variant="sortInPlace")
    func sort<R : Comparable>(@noescape by: (Generator.Element) -> R) -> [Generator.Element] {
        return self.sort { by($0) < by($1) }
    }
}

public extension MutableCollectionType where Self.Index : RandomAccessIndexType {
    
    /// Sort `self` in-place according to `by`.
    ///
    /// The sorting algorithm is not stable (can change the relative order of
    /// elements that compare equal).
    mutating func sortInPlace<R : Comparable>(@noescape by: (Generator.Element) -> R) {
        self.sortInPlace { by($0) < by($1) }
    }
}

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Dave Abrahams) #4

This seems to be essentially the same design as Susan’s, and has the same problem: it requires a new overload for every algorithm that takes a comparison predicate.

-Dave

···

On Dec 31, 2015, at 4:14 AM, Tino Heth <2th@gmx.de> wrote:

func byComparing<T, U: Comparable>(getComparisonKey: (T)->U) -> (T, T) -> Bool {
  return { getComparisonKey($0) < getComparisonKey($1) }
}

I've written something similar to bring file URLs into the order of their creation dates.
It is a small extension for collection types, and its only downside will disappear as soon as properties are accessible via method calls (afair there is a proposal in the making).

It was quite a lot fiddling with generics, and I don't have the tiny piece of code on my own computer, but it works in a way that you can do
let sorted = array.sortUsingAccessor(ElementType.methodThatReturnsComparable)
Beside the problems with properties, I really liked that approach.


(David Owens II) #5

I don’t get the resistance to Dave’s solution? I think it works well and much more applicable. Taking Susan’s original example, it’s not uncommon to want to sort or filter by multiple mechanisms.

func byComparing<T, U: Comparable>(getComparisonKey: (T)->U) -> (T, T) -> Bool {
    return { getComparisonKey($0) < getComparisonKey($1) }
}

struct Person {
    var name: String
    var age: Int
    var height: Int
}

let peoples = [
    Person(name: "Hawk", age: 24, height: 60),
    Person(name: "Andrew", age: 23, height: 66)
]

let youngest = peoples.minElement(byComparing { $0.age })
let tallest = peoples.maxElement(byComparing { $0.height })

print("youngest: \(youngest?.name ?? "<none>")")
print("tallest: \(tallest?.name ?? "<none>")")

-David

···

On Dec 31, 2015, at 8:19 AM, Dave Abrahams via swift-evolution <swift-evolution@swift.org> wrote:

On Dec 31, 2015, at 4:14 AM, Tino Heth <2th@gmx.de <mailto:2th@gmx.de>> wrote:

func byComparing<T, U: Comparable>(getComparisonKey: (T)->U) -> (T, T) -> Bool {
  return { getComparisonKey($0) < getComparisonKey($1) }
}

I've written something similar to bring file URLs into the order of their creation dates.
It is a small extension for collection types, and its only downside will disappear as soon as properties are accessible via method calls (afair there is a proposal in the making).

It was quite a lot fiddling with generics, and I don't have the tiny piece of code on my own computer, but it works in a way that you can do
let sorted = array.sortUsingAccessor(ElementType.methodThatReturnsComparable)
Beside the problems with properties, I really liked that approach.

This seems to be essentially the same design as Susan’s, and has the same problem: it requires a new overload for every algorithm that takes a comparison predicate.

-Dave

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Brent Royal-Gordon) #6

I don’t get the resistance to Dave’s solution? I think it works well and much more applicable.

I have two issues:

1. It's less discoverable. Someone merely *typing* `sort` into their editor will see `sortBy` right below it in their autocompletion list, and might discover it that way.

2. It forces a naïve implementation, which may not be the best idea. In the Perl world, for instance, we would usually use a Schwartzian transform to implement this, particularly if the key might be expensive to compute:

  array.map { ($0, sortKey($0)) }.sort { $0.1 < $1.1 }.map { $0.0 }

Having said that, I think both of these concerns are relatively minor.

···

--
Brent Royal-Gordon
Architechies


(Tino) #7

func byComparing<T, U: Comparable>(getComparisonKey: (T)->U) -> (T, T) -> Bool {
  return { getComparisonKey($0) < getComparisonKey($1) }
}

I've written something similar to bring file URLs into the order of their creation dates.
It is a small extension for collection types, and its only downside will disappear as soon as properties are accessible via method calls (afair there is a proposal in the making).

It was quite a lot fiddling with generics, and I don't have the tiny piece of code on my own computer, but it works in a way that you can do
let sorted = array.sortUsingAccessor(ElementType.methodThatReturnsComparable)
Beside the problems with properties, I really liked that approach.

Tino


#8

It confuses people if provide a global function byComparing in stdlib
which's doing nothing alone.

Dave Abrahams <dabrahams@apple.com> 於 2015年12月31日星期四 寫道:

···

Why add all those algorithms when you can write this

func byComparing<T, U: Comparable>(getComparisonKey: (T)->U) -> (T, T) ->
Bool {
  return { getComparisonKey($0) < getComparisonKey($1) }
}

peoples.sort(byComparing { $0.name })

?

-Dave

On Dec 30, 2015, at 10:38 PM, Susan Cheng via swift-evolution < > swift-evolution@swift.org > <javascript:_e(%7B%7D,'cvml','swift-evolution@swift.org');>> wrote:

Consider the follows:

struct Person {

    var name: String
    var age: Int
}

let peoples = [Person(name: "Hawk", age: 24), Person(name: "Andrew", age:
23)]

let youngest = peoples.minElement { $0.age < $1.age }

print(youngest?.name)

it's silly that we always have to write the code like { $0.some < $1.some }
or { some($0) < some($1) }

so, we should add those methods to stdlib:

extension SequenceType {
    /// Returns the minimum element in `self` or `nil` if the sequence is
empty.
    ///
    /// - Complexity: O(`elements.count`).
    ///
    @warn_unused_result
    public func minElement<R : Comparable>(@noescape by:
(Generator.Element) throws -> R) rethrows -> Generator.Element? {
        return try self.minElement { try by($0) < by($1) }
    }
    /// Returns the maximum element in `self` or `nil` if the sequence is
empty.
    ///
    /// - Complexity: O(`elements.count`).
    ///
    @warn_unused_result
    public func maxElement<R : Comparable>(@noescape by:
(Generator.Element) throws -> R) rethrows -> Generator.Element? {
        return try self.maxElement { try by($0) < by($1) }
    }
}

public extension MutableCollectionType {

    /// Return an `Array` containing the sorted elements of `source`.
    /// according to `by`.
    ///
    /// The sorting algorithm is not stable (can change the relative
order of
    /// elements that compare equal).
    @warn_unused_result(mutable_variant="sortInPlace")
    func sort<R : Comparable>(@noescape by: (Generator.Element) -> R) -> [
Generator.Element] {
        return self.sort { by($0) < by($1) }
    }
}

public extension MutableCollectionType where Self.Index :
RandomAccessIndexType {

    /// Sort `self` in-place according to `by`.
    ///
    /// The sorting algorithm is not stable (can change the relative
order of
    /// elements that compare equal).
    mutating func sortInPlace<R : Comparable>(@noescape by: (Generator.
Element) -> R) {
        self.sortInPlace { by($0) < by($1) }
    }
}

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
<javascript:_e(%7B%7D,'cvml','swift-evolution@swift.org');>
https://lists.swift.org/mailman/listinfo/swift-evolution


#9

yes.
Shouldn't have shorter names to replace the minElementBy, maxElementBy and
sortInPlaceBy

minBy and maxBy?

Jacob Bandes-Storch <jtbandes@gmail.com> 於 2015年12月31日星期四 寫道:

···

+1, although I wonder if the method names should be distinct (such as
minElementBy, sortBy, etc.)

On Wed, Dec 30, 2015 at 10:38 PM, Susan Cheng via swift-evolution < > swift-evolution@swift.org > <javascript:_e(%7B%7D,'cvml','swift-evolution@swift.org');>> wrote:

Consider the follows:

struct Person {

    var name: String

    var age: Int

}

let peoples = [Person(name: "Hawk", age: 24), Person(name: "Andrew",
age: 23)]

let youngest = peoples.minElement { $0.age < $1.age }

print(youngest?.name)

it's silly that we always have to write the code like { $0.some < $1.some }
or { some($0) < some($1) }

so, we should add those methods to stdlib:

extension SequenceType {

    /// Returns the minimum element in `self` or `nil` if the sequence
is empty.

    ///

    /// - Complexity: O(`elements.count`).

    ///

    @warn_unused_result

    public func minElement<R : Comparable>(@noescape by:
(Generator.Element) throws -> R) rethrows -> Generator.Element? {

        return try self.minElement { try by($0) < by($1) }

    }

    /// Returns the maximum element in `self` or `nil` if the sequence
is empty.

    ///

    /// - Complexity: O(`elements.count`).

    ///

    @warn_unused_result

    public func maxElement<R : Comparable>(@noescape by:
(Generator.Element) throws -> R) rethrows -> Generator.Element? {

        return try self.maxElement { try by($0) < by($1) }

    }

}

public extension MutableCollectionType {

    /// Return an `Array` containing the sorted elements of `source`.

    /// according to `by`.

    ///

    /// The sorting algorithm is not stable (can change the relative
order of

    /// elements that compare equal).

    @warn_unused_result(mutable_variant="sortInPlace")

    func sort<R : Comparable>(@noescape by: (Generator.Element) -> R) ->
[Generator.Element] {

        return self.sort { by($0) < by($1) }

    }

}

public extension MutableCollectionType where Self.Index :
RandomAccessIndexType {

    /// Sort `self` in-place according to `by`.

    ///

    /// The sorting algorithm is not stable (can change the relative
order of

    /// elements that compare equal).

    mutating func sortInPlace<R : Comparable>(@noescape by: (Generator.
Element) -> R) {

        self.sortInPlace { by($0) < by($1) }

    }

}

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
<javascript:_e(%7B%7D,'cvml','swift-evolution@swift.org');>
https://lists.swift.org/mailman/listinfo/swift-evolution


#10

What's problem of overloading? We only have four methods to do so.

Dave Abrahams <dabrahams@apple.com> 於 2016年1月1日星期五 寫道:

···

On Dec 31, 2015, at 4:14 AM, Tino Heth <2th@gmx.de > <javascript:_e(%7B%7D,'cvml','2th@gmx.de');>> wrote:

func byComparing<T, U: Comparable>(getComparisonKey: (T)->U) -> (T, T) ->
Bool {
  return { getComparisonKey($0) < getComparisonKey($1) }
}

I've written something similar to bring file URLs into the order of their
creation dates.
It is a small extension for collection types, and its only downside will
disappear as soon as properties are accessible via method calls (afair
there is a proposal in the making).

It was quite a lot fiddling with generics, and I don't have the tiny piece
of code on my own computer, but it works in a way that you can do
let sorted =
array.sortUsingAccessor(ElementType.methodThatReturnsComparable)
Beside the problems with properties, I really liked that approach.

This seems to be essentially the same design as Susan’s, and has the same
problem: it requires a new overload for every algorithm that takes a
comparison predicate.

-Dave


(Andrew Bennett) #11

As an alternative to minElement and maxElement, this could reduce the
number of overloads and provide autocomplete:

extension SequenceType {

    @warn_unused_result

    func reduce<C: Comparable>(

        @noescape combine: (C, C) throws -> Bool,

        @noescape by key: Generator.Element -> C

    ) rethrows -> Generator.Element?

    {

        var generator = self.generate()

        guard let first = generator.next() else {

            return nil

        }

        var best = first, bestKey = key(first)

        while let element = generator.next() {

            let elementKey = key(element)

            if try !combine(bestKey, elementKey) {

                bestKey = elementKey

                best = element

            }

        }

        return best

    }

}

print(["a","ab","abc"].reduce(<, by: { $0.characters.count })) //
Optional("a")

print(["a","ab","abc"].reduce(>, by: { $0.characters.count })) //
Optional("abc")

The regular minElement, maxElement methods could have this alternative when
you don't want "by":

extension SequenceType {

    @warn_unused_result

    func reduce(

        @noescape combine: (Generator.Element, Generator.Element) throws ->
Bool

    ) rethrows -> Generator.Element?

    {

        var generator = self.generate()

        guard let first = generator.next() else {

            return nil

        }

        var best = first

        while let element = generator.next() {

            best = try combine(best, element) ? best : element

        }

        return best

    }

}

print([0,1,2,3].reduce(<)) // Optional(0)

print([0,1,2,3].reduce(>)) // Optional(3)

It may be more efficient to define this on CollectionType where
SubSequence.Generator.Element == Generator.Element, using .first and .
dropFirst() rather than .generate(), but it's less flexible and this was
enough to illustrate the alternative.

···

On Fri, Jan 1, 2016 at 7:20 AM, Brent Royal-Gordon via swift-evolution < swift-evolution@swift.org> wrote:

> I don’t get the resistance to Dave’s solution? I think it works well and
much more applicable.

I have two issues:

1. It's less discoverable. Someone merely *typing* `sort` into their
editor will see `sortBy` right below it in their autocompletion list, and
might discover it that way.

2. It forces a naïve implementation, which may not be the best idea. In
the Perl world, for instance, we would usually use a Schwartzian transform
to implement this, particularly if the key might be expensive to compute:

        array.map { ($0, sortKey($0)) }.sort { $0.1 < $1.1 }.map { $0.0 }

Having said that, I think both of these concerns are relatively minor.

--
Brent Royal-Gordon
Architechies

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Sune Foldager) #12

Agreed. I’m +1 on Dave’s solution, and in general on primitives that can be composed.

/Sune

···

On 31 Dec 2015, at 17:45, David Owens II via swift-evolution <swift-evolution@swift.org> wrote:

I don’t get the resistance to Dave’s solution? I think it works well and much more applicable. Taking Susan’s original example, it’s not uncommon to want to sort or filter by multiple mechanisms.


(Jordan Rose) #13

+1 and -1 to this. Computing the sort key N times instead of 2*(# of comparisons) can be a big win sometimes. On the other hand, allocating memory for the sort keys might be a net loss, especially if the collection being sorted is large. I guess that means it's better to be made explicit, but it would be nice™ if it were more convenient than it is now. Brent's way does a lot of copies; I tried to avoid that but quickly ran into trouble…

var keys = array.map { $0.key }
array.sort { ??? }

…because the current 'sort' takes a comparator, which just takes values, not indices.

Jordan

···

On Dec 31, 2015, at 12:20, Brent Royal-Gordon via swift-evolution <swift-evolution@swift.org> wrote:

2. It forces a naïve implementation, which may not be the best idea. In the Perl world, for instance, we would usually use a Schwartzian transform to implement this, particularly if the key might be expensive to compute:

  array.map { ($0, sortKey($0)) }.sort { $0.1 < $1.1 }.map { $0.0 }


(Dave Abrahams) #14

I don’t understand that argument. Obviously the function would be documented and there would be examples showing how to use it. Why would it confuse people?

I think you’d need much stronger reasons to justify adding an unbounded set of overloads (is every algorithm that takes a comparison closure going to get one of these?) when we can handle the problem economically with a single function.

-Dave

···

On Dec 31, 2015, at 12:04 AM, Susan Cheng <susan.doggie@gmail.com> wrote:

It confuses people if provide a global function byComparing in stdlib which's doing nothing alone.

Dave Abrahams <dabrahams@apple.com <mailto:dabrahams@apple.com>> 於 2015年12月31日星期四 寫道:
Why add all those algorithms when you can write this

func byComparing<T, U: Comparable>(getComparisonKey: (T)->U) -> (T, T) -> Bool {
  return { getComparisonKey($0) < getComparisonKey($1) }
}

peoples.sort(byComparing { $0.name <http://0.name/> })

?

-Dave

On Dec 30, 2015, at 10:38 PM, Susan Cheng via swift-evolution <swift-evolution@swift.org <javascript:_e(%7B%7D,'cvml','swift-evolution@swift.org');>> wrote:

Consider the follows:

struct Person {
    
    var name: String
    var age: Int
}

let peoples = [Person(name: "Hawk", age: 24), Person(name: "Andrew", age: 23)]

let youngest = peoples.minElement { $0.age < $1.age }

print(youngest?.name)

it's silly that we always have to write the code like { $0.some < $1.some } or { some($0) < some($1) }

so, we should add those methods to stdlib:

extension SequenceType {
    /// Returns the minimum element in `self` or `nil` if the sequence is empty.
    ///
    /// - Complexity: O(`elements.count`).
    ///
    @warn_unused_result
    public func minElement<R : Comparable>(@noescape by: (Generator.Element) throws -> R) rethrows -> Generator.Element? {
        return try self.minElement { try by($0) < by($1) }
    }
    /// Returns the maximum element in `self` or `nil` if the sequence is empty.
    ///
    /// - Complexity: O(`elements.count`).
    ///
    @warn_unused_result
    public func maxElement<R : Comparable>(@noescape by: (Generator.Element) throws -> R) rethrows -> Generator.Element? {
        return try self.maxElement { try by($0) < by($1) }
    }
}

public extension MutableCollectionType {
    
    /// Return an `Array` containing the sorted elements of `source`.
    /// according to `by`.
    ///
    /// The sorting algorithm is not stable (can change the relative order of
    /// elements that compare equal).
    @warn_unused_result(mutable_variant="sortInPlace")
    func sort<R : Comparable>(@noescape by: (Generator.Element) -> R) -> [Generator.Element] {
        return self.sort { by($0) < by($1) }
    }
}

public extension MutableCollectionType where Self.Index : RandomAccessIndexType {
    
    /// Sort `self` in-place according to `by`.
    ///
    /// The sorting algorithm is not stable (can change the relative order of
    /// elements that compare equal).
    mutating func sortInPlace<R : Comparable>(@noescape by: (Generator.Element) -> R) {
        self.sortInPlace { by($0) < by($1) }
    }
}

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <javascript:_e(%7B%7D,'cvml','swift-evolution@swift.org');>
https://lists.swift.org/mailman/listinfo/swift-evolution


(Dave Abrahams) #15

What's problem of overloading? We only have four methods to do so.

The set of potential algorithms using comparison predicates is not closed, and they will be implemented not only by the standard library but also by third parties. One component gets us the functionality for all those algorithms.

Dave Abrahams <dabrahams@apple.com <mailto:dabrahams@apple.com>> 於 2016年1月1日星期五 寫道:

func byComparing<T, U: Comparable>(getComparisonKey: (T)->U) -> (T, T) -> Bool {
  return { getComparisonKey($0) < getComparisonKey($1) }
}

I've written something similar to bring file URLs into the order of their creation dates.
It is a small extension for collection types, and its only downside will disappear as soon as properties are accessible via method calls (afair there is a proposal in the making).

It was quite a lot fiddling with generics, and I don't have the tiny piece of code on my own computer, but it works in a way that you can do
let sorted = array.sortUsingAccessor(ElementType.methodThatReturnsComparable)
Beside the problems with properties, I really liked that approach.

This seems to be essentially the same design as Susan’s, and has the same problem: it requires a new overload for every algorithm that takes a comparison predicate.

-Dave

-Dave

···

On Dec 31, 2015, at 8:44 AM, Susan Cheng <susan.doggie@gmail.com> wrote:

On Dec 31, 2015, at 4:14 AM, Tino Heth <2th@gmx.de <javascript:_e(%7B%7D,'cvml','2th@gmx.de');>> wrote:


#16

And how do you write a @noescape version with this function?

Dave Abrahams <dabrahams@apple.com> 於 2015年12月31日星期四 寫道:

···

I don’t understand that argument. Obviously the function would be
documented and there would be examples showing how to use it. Why would it
confuse people?

I think you’d need much stronger reasons to justify adding an unbounded
set of overloads (is every algorithm that takes a comparison closure going
to get one of these?) when we can handle the problem economically with a
single function.

-Dave

On Dec 31, 2015, at 12:04 AM, Susan Cheng <susan.doggie@gmail.com > <javascript:_e(%7B%7D,'cvml','susan.doggie@gmail.com');>> wrote:

It confuses people if provide a global function byComparing in stdlib
which's doing nothing alone.

Dave Abrahams <dabrahams@apple.com
<javascript:_e(%7B%7D,'cvml','dabrahams@apple.com');>> 於 2015年12月31日星期四
寫道:

Why add all those algorithms when you can write this

func byComparing<T, U: Comparable>(getComparisonKey: (T)->U) -> (T, T) ->
Bool {
  return { getComparisonKey($0) < getComparisonKey($1) }
}

peoples.sort(byComparing { $0.name })

?

-Dave

On Dec 30, 2015, at 10:38 PM, Susan Cheng via swift-evolution < >> swift-evolution@swift.org> wrote:

Consider the follows:

struct Person {

    var name: String
    var age: Int
}

let peoples = [Person(name: "Hawk", age: 24), Person(name: "Andrew",
age: 23)]

let youngest = peoples.minElement { $0.age < $1.age }

print(youngest?.name)

it's silly that we always have to write the code like { $0.some < $1.some }
or { some($0) < some($1) }

so, we should add those methods to stdlib:

extension SequenceType {
    /// Returns the minimum element in `self` or `nil` if the sequence
is empty.
    ///
    /// - Complexity: O(`elements.count`).
    ///
    @warn_unused_result
    public func minElement<R : Comparable>(@noescape by:
(Generator.Element) throws -> R) rethrows -> Generator.Element? {
        return try self.minElement { try by($0) < by($1) }
    }
    /// Returns the maximum element in `self` or `nil` if the sequence
is empty.
    ///
    /// - Complexity: O(`elements.count`).
    ///
    @warn_unused_result
    public func maxElement<R : Comparable>(@noescape by:
(Generator.Element) throws -> R) rethrows -> Generator.Element? {
        return try self.maxElement { try by($0) < by($1) }
    }
}

public extension MutableCollectionType {

    /// Return an `Array` containing the sorted elements of `source`.
    /// according to `by`.
    ///
    /// The sorting algorithm is not stable (can change the relative
order of
    /// elements that compare equal).
    @warn_unused_result(mutable_variant="sortInPlace")
    func sort<R : Comparable>(@noescape by: (Generator.Element) -> R) ->
[Generator.Element] {
        return self.sort { by($0) < by($1) }
    }
}

public extension MutableCollectionType where Self.Index :
RandomAccessIndexType {

    /// Sort `self` in-place according to `by`.
    ///
    /// The sorting algorithm is not stable (can change the relative
order of
    /// elements that compare equal).
    mutating func sortInPlace<R : Comparable>(@noescape by: (Generator.
Element) -> R) {
        self.sortInPlace { by($0) < by($1) }
    }
}

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Howard Lovatt) #17

+1 for the reduce version that Andrew presented, it has wider applicability.

···

On 4 Jan 2016, at 10:42 AM, Andrew Bennett via swift-evolution <swift-evolution@swift.org> wrote:

As an alternative to minElement and maxElement, this could reduce the number of overloads and provide autocomplete:

extension SequenceType {
    @warn_unused_result
    func reduce<C: Comparable>(
        @noescape combine: (C, C) throws -> Bool,
        @noescape by key: Generator.Element -> C
    ) rethrows -> Generator.Element?
    {
        var generator = self.generate()
        guard let first = generator.next() else {
            return nil
        }
        var best = first, bestKey = key(first)
        while let element = generator.next() {
            let elementKey = key(element)
            if try !combine(bestKey, elementKey) {
                bestKey = elementKey
                best = element
            }
        }
        return best
    }
}

print(["a","ab","abc"].reduce(<, by: { $0.characters.count })) // Optional("a")
print(["a","ab","abc"].reduce(>, by: { $0.characters.count })) // Optional("abc")

The regular minElement, maxElement methods could have this alternative when you don't want "by":

extension SequenceType {
    @warn_unused_result
    func reduce(
        @noescape combine: (Generator.Element, Generator.Element) throws -> Bool
    ) rethrows -> Generator.Element?
    {
        var generator = self.generate()
        guard let first = generator.next() else {
            return nil
        }
        var best = first
        while let element = generator.next() {
            best = try combine(best, element) ? best : element
        }
        return best
    }
}

print([0,1,2,3].reduce(<)) // Optional(0)
print([0,1,2,3].reduce(>)) // Optional(3)

It may be more efficient to define this on CollectionType where SubSequence.Generator.Element == Generator.Element, using .first and .dropFirst() rather than .generate(), but it's less flexible and this was enough to illustrate the alternative.

On Fri, Jan 1, 2016 at 7:20 AM, Brent Royal-Gordon via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:
> I don’t get the resistance to Dave’s solution? I think it works well and much more applicable.

I have two issues:

1. It's less discoverable. Someone merely *typing* `sort` into their editor will see `sortBy` right below it in their autocompletion list, and might discover it that way.

2. It forces a naïve implementation, which may not be the best idea. In the Perl world, for instance, we would usually use a Schwartzian transform to implement this, particularly if the key might be expensive to compute:

        array.map { ($0, sortKey($0)) }.sort { $0.1 < $1.1 }.map { $0.0 }

Having said that, I think both of these concerns are relatively minor.

--
Brent Royal-Gordon
Architechies

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Dave Abrahams) #18

You don’t. Is that a problem for the intended use-cases?

-Dave

···

On Dec 31, 2015, at 12:11 AM, Susan Cheng <susan.doggie@gmail.com> wrote:

And how do you write a @noescape version with this function?

Dave Abrahams <dabrahams@apple.com <mailto:dabrahams@apple.com>> 於 2015年12月31日星期四 寫道:
I don’t understand that argument. Obviously the function would be documented and there would be examples showing how to use it. Why would it confuse people?

I think you’d need much stronger reasons to justify adding an unbounded set of overloads (is every algorithm that takes a comparison closure going to get one of these?) when we can handle the problem economically with a single function.

-Dave

On Dec 31, 2015, at 12:04 AM, Susan Cheng <susan.doggie@gmail.com <javascript:_e(%7B%7D,'cvml','susan.doggie@gmail.com');>> wrote:

It confuses people if provide a global function byComparing in stdlib which's doing nothing alone.

Dave Abrahams <dabrahams@apple.com <javascript:_e(%7B%7D,'cvml','dabrahams@apple.com');>> 於 2015年12月31日星期四 寫道:
Why add all those algorithms when you can write this

func byComparing<T, U: Comparable>(getComparisonKey: (T)->U) -> (T, T) -> Bool {
  return { getComparisonKey($0) < getComparisonKey($1) }
}

peoples.sort(byComparing { $0.name <http://0.name/> })

?

-Dave

On Dec 30, 2015, at 10:38 PM, Susan Cheng via swift-evolution <swift-evolution@swift.org <>> wrote:

Consider the follows:

struct Person {
    
    var name: String
    var age: Int
}

let peoples = [Person(name: "Hawk", age: 24), Person(name: "Andrew", age: 23)]

let youngest = peoples.minElement { $0.age < $1.age }

print(youngest?.name)

it's silly that we always have to write the code like { $0.some < $1.some } or { some($0) < some($1) }

so, we should add those methods to stdlib:

extension SequenceType {
    /// Returns the minimum element in `self` or `nil` if the sequence is empty.
    ///
    /// - Complexity: O(`elements.count`).
    ///
    @warn_unused_result
    public func minElement<R : Comparable>(@noescape by: (Generator.Element) throws -> R) rethrows -> Generator.Element? {
        return try self.minElement { try by($0) < by($1) }
    }
    /// Returns the maximum element in `self` or `nil` if the sequence is empty.
    ///
    /// - Complexity: O(`elements.count`).
    ///
    @warn_unused_result
    public func maxElement<R : Comparable>(@noescape by: (Generator.Element) throws -> R) rethrows -> Generator.Element? {
        return try self.maxElement { try by($0) < by($1) }
    }
}

public extension MutableCollectionType {
    
    /// Return an `Array` containing the sorted elements of `source`.
    /// according to `by`.
    ///
    /// The sorting algorithm is not stable (can change the relative order of
    /// elements that compare equal).
    @warn_unused_result(mutable_variant="sortInPlace")
    func sort<R : Comparable>(@noescape by: (Generator.Element) -> R) -> [Generator.Element] {
        return self.sort { by($0) < by($1) }
    }
}

public extension MutableCollectionType where Self.Index : RandomAccessIndexType {
    
    /// Sort `self` in-place according to `by`.
    ///
    /// The sorting algorithm is not stable (can change the relative order of
    /// elements that compare equal).
    mutating func sortInPlace<R : Comparable>(@noescape by: (Generator.Element) -> R) {
        self.sortInPlace { by($0) < by($1) }
    }
}

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <>
https://lists.swift.org/mailman/listinfo/swift-evolution


(Jacob Bandes-Storch) #19

With the optimizer as it is today, if this were @_transparent could the
extra function invocation(s) be optimized out when you use it in a
non-escaping context such as sort()?

Jacob

···

On Thu, Dec 31, 2015 at 12:26 AM, Dave Abrahams via swift-evolution < swift-evolution@swift.org> wrote:

You don’t. Is that a problem for the intended use-cases?

-Dave

On Dec 31, 2015, at 12:11 AM, Susan Cheng <susan.doggie@gmail.com> wrote:

And how do you write a @noescape version with this function?

Dave Abrahams <dabrahams@apple.com> 於 2015年12月31日星期四 寫道:

I don’t understand that argument. Obviously the function would be
documented and there would be examples showing how to use it. Why would it
confuse people?

I think you’d need much stronger reasons to justify adding an unbounded
set of overloads (is every algorithm that takes a comparison closure going
to get one of these?) when we can handle the problem economically with a
single function.

-Dave

On Dec 31, 2015, at 12:04 AM, Susan Cheng <susan.doggie@gmail.com> wrote:

It confuses people if provide a global function byComparing in stdlib
which's doing nothing alone.

Dave Abrahams <dabrahams@apple.com> 於 2015年12月31日星期四 寫道:

Why add all those algorithms when you can write this

func byComparing<T, U: Comparable>(getComparisonKey: (T)->U) -> (T, T)
-> Bool {
  return { getComparisonKey($0) < getComparisonKey($1) }
}

peoples.sort(byComparing { $0.name })

?

-Dave

On Dec 30, 2015, at 10:38 PM, Susan Cheng via swift-evolution < >>> swift-evolution@swift.org> wrote:

Consider the follows:

struct Person {

    var name: String
    var age: Int
}

let peoples = [Person(name: "Hawk", age: 24), Person(name: "Andrew",
age: 23)]

let youngest = peoples.minElement { $0.age < $1.age }

print(youngest?.name)

it's silly that we always have to write the code like { $0.some < $1.
some } or { some($0) < some($1) }

so, we should add those methods to stdlib:

extension SequenceType {
    /// Returns the minimum element in `self` or `nil` if the sequence
is empty.
    ///
    /// - Complexity: O(`elements.count`).
    ///
    @warn_unused_result
    public func minElement<R : Comparable>(@noescape by:
(Generator.Element) throws -> R) rethrows -> Generator.Element? {
        return try self.minElement { try by($0) < by($1) }
    }
    /// Returns the maximum element in `self` or `nil` if the sequence
is empty.
    ///
    /// - Complexity: O(`elements.count`).
    ///
    @warn_unused_result
    public func maxElement<R : Comparable>(@noescape by:
(Generator.Element) throws -> R) rethrows -> Generator.Element? {
        return try self.maxElement { try by($0) < by($1) }
    }
}

public extension MutableCollectionType {

    /// Return an `Array` containing the sorted elements of `source`.
    /// according to `by`.
    ///
    /// The sorting algorithm is not stable (can change the relative
order of
    /// elements that compare equal).
    @warn_unused_result(mutable_variant="sortInPlace")
    func sort<R : Comparable>(@noescape by: (Generator.Element) -> R)
-> [Generator.Element] {
        return self.sort { by($0) < by($1) }
    }
}

public extension MutableCollectionType where Self.Index :
RandomAccessIndexType {

    /// Sort `self` in-place according to `by`.
    ///
    /// The sorting algorithm is not stable (can change the relative
order of
    /// elements that compare equal).
    mutating func sortInPlace<R : Comparable>(@noescape by: (Generator.
Element) -> R) {
        self.sortInPlace { by($0) < by($1) }
    }
}

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Dave Abrahams) #20

-Dave

With the optimizer as it is today, if this were @_transparent could the extra function invocation(s) be optimized out when you use it in a non-escaping context such as sort()?

Sure. It doesn’t need to be @_transparent; in general use @inline(__always) instead except in very special cases, (e.g. when you need constant folding to propagate through the function so you can give arithmetic overflow diagnostics at compile-time).

···

On Dec 31, 2015, at 12:28 AM, Jacob Bandes-Storch <jtbandes@gmail.com> wrote:

Jacob

On Thu, Dec 31, 2015 at 12:26 AM, Dave Abrahams via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:
You don’t. Is that a problem for the intended use-cases?

-Dave

On Dec 31, 2015, at 12:11 AM, Susan Cheng <susan.doggie@gmail.com <mailto:susan.doggie@gmail.com>> wrote:

And how do you write a @noescape version with this function?

Dave Abrahams <dabrahams@apple.com <mailto:dabrahams@apple.com>> 於 2015年12月31日星期四 寫道:
I don’t understand that argument. Obviously the function would be documented and there would be examples showing how to use it. Why would it confuse people?

I think you’d need much stronger reasons to justify adding an unbounded set of overloads (is every algorithm that takes a comparison closure going to get one of these?) when we can handle the problem economically with a single function.

-Dave

On Dec 31, 2015, at 12:04 AM, Susan Cheng <susan.doggie@gmail.com <>> wrote:

It confuses people if provide a global function byComparing in stdlib which's doing nothing alone.

Dave Abrahams <dabrahams@apple.com <>> 於 2015年12月31日星期四 寫道:
Why add all those algorithms when you can write this

func byComparing<T, U: Comparable>(getComparisonKey: (T)->U) -> (T, T) -> Bool {
  return { getComparisonKey($0) < getComparisonKey($1) }
}

peoples.sort(byComparing { $0.name <http://0.name/> })

?

-Dave

On Dec 30, 2015, at 10:38 PM, Susan Cheng via swift-evolution <swift-evolution@swift.org <>> wrote:

Consider the follows:

struct Person {
    
    var name: String
    var age: Int
}

let peoples = [Person(name: "Hawk", age: 24), Person(name: "Andrew", age: 23)]

let youngest = peoples.minElement { $0.age < $1.age }

print(youngest?.name)

it's silly that we always have to write the code like { $0.some < $1.some } or { some($0) < some($1) }

so, we should add those methods to stdlib:

extension SequenceType {
    /// Returns the minimum element in `self` or `nil` if the sequence is empty.
    ///
    /// - Complexity: O(`elements.count`).
    ///
    @warn_unused_result
    public func minElement<R : Comparable>(@noescape by: (Generator.Element) throws -> R) rethrows -> Generator.Element? {
        return try self.minElement { try by($0) < by($1) }
    }
    /// Returns the maximum element in `self` or `nil` if the sequence is empty.
    ///
    /// - Complexity: O(`elements.count`).
    ///
    @warn_unused_result
    public func maxElement<R : Comparable>(@noescape by: (Generator.Element) throws -> R) rethrows -> Generator.Element? {
        return try self.maxElement { try by($0) < by($1) }
    }
}

public extension MutableCollectionType {
    
    /// Return an `Array` containing the sorted elements of `source`.
    /// according to `by`.
    ///
    /// The sorting algorithm is not stable (can change the relative order of
    /// elements that compare equal).
    @warn_unused_result(mutable_variant="sortInPlace")
    func sort<R : Comparable>(@noescape by: (Generator.Element) -> R) -> [Generator.Element] {
        return self.sort { by($0) < by($1) }
    }
}

public extension MutableCollectionType where Self.Index : RandomAccessIndexType {
    
    /// Sort `self` in-place according to `by`.
    ///
    /// The sorting algorithm is not stable (can change the relative order of
    /// elements that compare equal).
    mutating func sortInPlace<R : Comparable>(@noescape by: (Generator.Element) -> R) {
        self.sortInPlace { by($0) < by($1) }
    }
}

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <>
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution