Simplify chained calls

Adriano_Ferreira · June 28, 2016, 2:50pm

Hi everyone!

I’m experimenting with this functional selection sort code and I wonder if anyone could help me simplify the portion indicated below.

// Swift 3

func selectionSort(_ array: [Int]) -> [Int] {

    guard array.count > 1, let minElement = array.min() else {
        return array
    }

let indexOfMinElement = array.index(of: minElement)!

    // All of this just to filter out the first smallest element and return the rest
    // Also tried ‘suffix(from:)' here, but couldn’t make it work properly
    let rest = array.enumerated()
                    .filter({ index, _ in index != indexOfMinElement })
                    .map({ _, element in element })

return [minElement] + selectionSort(rest)
}

By the way, it feels really weird to chain method calls like this in Swift 3, particularly due to the mixing of terms of art (e.g. “filter” and “map”) with other methods that follow the -ed/-ing rules from the API guidelines (e.g. enumerated).

Best,

— A

Aaron_Bohannon · June 29, 2016, 12:20am

I think that's about as simple as you can make it unless you allow yourself
to remove more than one element at a time when the minimum appears more
than once.

Here's the question I find interesting: what's the simplest way to change
that code into a version based on lazy collections? After all, there would
arguably be some real practical value to a lazy recursive selection sort in
cases where only a relatively small prefix of the resulting collection was
expected to be needed. I took a stab at making your code lazy but quickly
realized that it wasn't going to be as easy as I thought.

···

On Tue, Jun 28, 2016 at 8:50 AM, Adriano Ferreira via swift-users < swift-users@swift.org> wrote:

Hi everyone!

I’m experimenting with this functional selection sort code and I wonder if
anyone could help me simplify the portion indicated below.

// Swift 3

func selectionSort(_ array: [Int]) -> [Int] {

    guard array.count > 1, let minElement = array.min() else {
        return array
    }

    let indexOfMinElement = array.index(of: minElement)!

    // All of this just to filter out the first smallest element and
return the rest
    // Also tried ‘suffix(from:)' here, but couldn’t make it work properly
    let rest = array.enumerated()
                    .filter({ index, _ in index != indexOfMinElement })
                    .map({ _, element in element })

    return [minElement] + selectionSort(rest)
}

By the way, it feels really weird to chain method calls like this in Swift
3, particularly due to the mixing of terms of art (e.g. “filter” and “map”)
with other methods that follow the -ed/-ing rules from the API
guidelines (e.g. enumerated).

Best,

— A

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

Dan_Loewenherz · June 29, 2016, 2:18am

I’m not sure if you wanted to stick with the pure functional approach, but
here’s an alternative that uses Range<Int> to take care of most of the work.

func selectionSort(_ array: [Int]) -> [Int] {
    guard let minValue = array.min(), let index = array.index(of: minValue)
else {
        return
    }

let ranges = [0..<index, index.advanced(by: 1)..<array.endIndex]
return [minValue] + selectionSort(ranges.flatMap { array[$0] })
}

···

On Tue, Jun 28, 2016 at 7:20 PM, Aaron Bohannon via swift-users < swift-users@swift.org> wrote:

I think that's about as simple as you can make it unless you allow
yourself to remove more than one element at a time when the minimum appears
more than once.

Here's the question I find interesting: what's the simplest way to change
that code into a version based on lazy collections? After all, there would
arguably be some real practical value to a lazy recursive selection sort in
cases where only a relatively small prefix of the resulting collection was
expected to be needed. I took a stab at making your code lazy but quickly
realized that it wasn't going to be as easy as I thought.

On Tue, Jun 28, 2016 at 8:50 AM, Adriano Ferreira via swift-users < > swift-users@swift.org> wrote:

Hi everyone!

I’m experimenting with this functional selection sort code and I wonder
if anyone could help me simplify the portion indicated below.

// Swift 3

func selectionSort(_ array: [Int]) -> [Int] {

    guard array.count > 1, let minElement = array.min() else {
        return array
    }

    let indexOfMinElement = array.index(of: minElement)!

    // All of this just to filter out the first smallest element and
return the rest
    // Also tried ‘suffix(from:)' here, but couldn’t make it work
properly
    let rest = array.enumerated()
                    .filter({ index, _ in index != indexOfMinElement })
                    .map({ _, element in element })

    return [minElement] + selectionSort(rest)
}

By the way, it feels really weird to chain method calls like this in
Swift 3, particularly due to the mixing of terms of art (e.g. “filter” and
“map”) with other methods that follow the -ed/-ing rules from the API
guidelines (e.g. enumerated).

Best,

— A

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

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

Erica_Sadun · June 29, 2016, 2:58am

I’m not sure if you wanted to stick with the pure functional approach, but here’s an alternative that uses Range<Int> to take care of most of the work.

func selectionSort(_ array: [Int]) -> [Int] {
    guard let minValue = array.min(), let index = array.index(of: minValue) else {
        return
    }

    let ranges = [0..<index, index.advanced(by: 1)..<array.endIndex]
    return [minValue] + selectionSort(ranges.flatMap { array[$0] })
}

Most everyone is doing two passes, one to get the minimum value, another to get its index.
I aesthetically prefer using enumerate to do both at once.

-- E

···

On Jun 28, 2016, at 8:18 PM, Dan Loewenherz via swift-users <swift-users@swift.org> wrote:

Dan_Loewenherz · June 29, 2016, 5:42am

Makes sense. Here’s a revision. It’s not as simple, but it does just one
pass through the array:

func selectionSort(_ array: [Int]) -> [Int] {

guard let first = array.first else { return }

let (index, minValue) = array.enumerated().reduce((0, first)) { (carry,
item) in

if item.element < carry.1 { return item } else { return carry }

}

let ranges = [0..<index, index.advanced(by: 1)..<array.endIndex]

return [minValue] + selectionSort(ranges.flatMap { array[$0] })

}

~Dan

···

On Tue, Jun 28, 2016 at 9:58 PM, Erica Sadun <erica@ericasadun.com> wrote:

Most everyone is doing two passes, one to get the minimum value, another
to get its index.
I aesthetically prefer using enumerate to do both at once.

-- E

Tod_Cunningham · June 29, 2016, 11:12pm

Was trying to using some functional programming concepts while also using as little memory as possible. The big advantage of using a selections sort is that it sorts w/o having to allocation additional memory. This still violates that, but it’s closer. :)

func selectionSort(_ array: inout [Int]) {
    for index in 0..<array.count {
        // .1 is value .0 is the index on the enumeration
        let minElement = array.enumerated().dropFirst(index).min(isOrderedBefore: { $0.1 < $1.1 } )
        if index != minElement!.0 {
            swap(&array[index], &array[minElement!.0])
        }
    }
}

or using recursion:

func selectionSort(_ array: inout [Int], index: Int = 0) {
    if index < array.count {
        // .1 is value .0 is the index on the enumeration
        let minElement = array.indexed().dropFirst(index).min(isOrderedBefore: { $0.1 < $1.1 } )
        if index != minElement!.0 {
            swap(&array[index], &array[minElement!.0])
        }
        selectionSort(&array, index: index+1)
    }
}

···

On 6/28/16, 10:58 PM, "swift-users-bounces@swift.org on behalf of Erica Sadun via swift-users" <swift-users-bounces@swift.org on behalf of swift-users@swift.org> wrote:

On Jun 28, 2016, at 8:18 PM, Dan Loewenherz via swift-users <swift-users@swift.org> wrote:

I’m not sure if you wanted to stick with the pure functional approach, but here’s an alternative that uses Range<Int> to take care of most of the work.

func selectionSort(_ array: [Int]) -> [Int] {
    guard let minValue = array.min(), let index = array.index(of: minValue) else {
        return
    }

    let ranges = [0..<index, index.advanced(by: 1)..<array.endIndex]
    return [minValue] + selectionSort(ranges.flatMap { array[$0] })
}

Most everyone is doing two passes, one to get the minimum value, another to get its index.
I aesthetically prefer using enumerate to do both at once.

-- E

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

Tod_Cunningham · June 30, 2016, 3:32pm

This was bugging me last night, as I still didn’t like the solution. What about something like:

func selectionSort(_ originalArray: [Int]) -> [Int] {
    var array = originalArray
    for index in 0..<array.count {
        let minIndex = array.indices.clamped(to: index..<x.count).min(isOrderedBefore: { array[$0] < array[$1] })
        if index != minIndex {
            swap(&array[index], &array[minIndex!])
        }
    }
    return array
}

Was trying to using some functional programming concepts while also using as little memory as possible. The big advantage of using a selections sort is that it sorts w/o having to allocation additional memory. This still violates that, but it’s closer. :)

func selectionSort(_ array: inout [Int]) {
    for index in 0..<array.count {
        // .1 is value .0 is the index on the enumeration
        let minElement = array.enumerated().dropFirst(index).min(isOrderedBefore: { $0.1 < $1.1 } )
        if index != minElement!.0 {
            swap(&array[index], &array[minElement!.0])
        }
    }
}

or using recursion:

func selectionSort(_ array: inout [Int], index: Int = 0) {
    if index < array.count {
        // .1 is value .0 is the index on the enumeration
        let minElement = array.indexed().dropFirst(index).min(isOrderedBefore: { $0.1 < $1.1 } )
        if index != minElement!.0 {
            swap(&array[index], &array[minElement!.0])
        }
        selectionSort(&array, index: index+1)
    }
}

···

On 6/29/16, 7:12 PM, "swift-users-bounces@swift.org on behalf of Tod Cunningham via swift-users" <swift-users-bounces@swift.org on behalf of swift-users@swift.org> wrote:

On 6/28/16, 10:58 PM, "swift-users-bounces@swift.org on behalf of Erica Sadun via swift-users" <swift-users-bounces@swift.org on behalf of swift-users@swift.org> wrote:

On Jun 28, 2016, at 8:18 PM, Dan Loewenherz via swift-users <swift-users@swift.org> wrote:

I’m not sure if you wanted to stick with the pure functional approach, but here’s an alternative that uses Range<Int> to take care of most of the work.

func selectionSort(_ array: [Int]) -> [Int] {
    guard let minValue = array.min(), let index = array.index(of: minValue) else {
        return
    }

    let ranges = [0..<index, index.advanced(by: 1)..<array.endIndex]
    return [minValue] + selectionSort(ranges.flatMap { array[$0] })
}

Most everyone is doing two passes, one to get the minimum value, another to get its index.
I aesthetically prefer using enumerate to do both at once.

-- E

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

Adriano_Ferreira · June 30, 2016, 7:57pm

Hi Tod, thanks for sharing your ideas. Much appreciated!

Feel free to take a look at my playground where I explore many other alternative implementations.

https://github.com/adrfer/Sort/tree/swift-3

Best,

— A

···

On Jun 30, 2016, at 11:32 AM, Tod Cunningham via swift-users <swift-users@swift.org> wrote:

This was bugging me last night, as I still didn’t like the solution. What about something like:

func selectionSort(_ originalArray: [Int]) -> [Int] {
   var array = originalArray
   for index in 0..<array.count {
       let minIndex = array.indices.clamped(to: index..<x.count).min(isOrderedBefore: { array[$0] < array[$1] })
       if index != minIndex {
           swap(&array[index], &array[minIndex!])
       }
   }
   return array
}

On 6/29/16, 7:12 PM, "swift-users-bounces@swift.org on behalf of Tod Cunningham via swift-users" <swift-users-bounces@swift.org on behalf of swift-users@swift.org> wrote:

Was trying to using some functional programming concepts while also using as little memory as possible. The big advantage of using a selections sort is that it sorts w/o having to allocation additional memory. This still violates that, but it’s closer. :)

func selectionSort(_ array: inout [Int]) {
   for index in 0..<array.count {
       // .1 is value .0 is the index on the enumeration
       let minElement = array.enumerated().dropFirst(index).min(isOrderedBefore: { $0.1 < $1.1 } )
       if index != minElement!.0 {
           swap(&array[index], &array[minElement!.0])
       }
   }
}

or using recursion:

func selectionSort(_ array: inout [Int], index: Int = 0) {
   if index < array.count {
       // .1 is value .0 is the index on the enumeration
       let minElement = array.indexed().dropFirst(index).min(isOrderedBefore: { $0.1 < $1.1 } )
       if index != minElement!.0 {
           swap(&array[index], &array[minElement!.0])
       }
       selectionSort(&array, index: index+1)
   }
}

On 6/28/16, 10:58 PM, "swift-users-bounces@swift.org on behalf of Erica Sadun via swift-users" <swift-users-bounces@swift.org on behalf of swift-users@swift.org> wrote:

On Jun 28, 2016, at 8:18 PM, Dan Loewenherz via swift-users <swift-users@swift.org> wrote:

I’m not sure if you wanted to stick with the pure functional approach, but here’s an alternative that uses Range<Int> to take care of most of the work.

func selectionSort(_ array: [Int]) -> [Int] {
   guard let minValue = array.min(), let index = array.index(of: minValue) else {
       return
   }

   let ranges = [0..<index, index.advanced(by: 1)..<array.endIndex]
   return [minValue] + selectionSort(ranges.flatMap { array[$0] })
}

Most everyone is doing two passes, one to get the minimum value, another to get its index.
I aesthetically prefer using enumerate to do both at once.

-- E

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

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

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