3 ms·

Aside from trivial types, like strings or integers, how does the language know how to sort a list of values, if you don't tell it how to? Translate this into w

by NateDad 11y ago

Aside from trivial types, like strings or integers, how does the language know how to sort a list of values, if you don't tell it how to? Translate this into whatever language you like: Machine { Name string OS string RAM int } You have 3 places that want to sort a list of machines, one by name, one by OS, and one by RAM. You're telling me there's a language that can do that without having to write some kind of code like this for each? sort(machines, key: Name) I don't understand how that's possible, but I welcome your explanation.

pklausler 11y ago
Sorting on all three fields in priority order is what I had in mind, and that's trivial in Haskell by adding "deriving(Ord)" to the data type definition and then just using the standard "sort :: Ord a => [a] -> [a]". If you're always going to sort them based on some (other) relation between the fields, make your type a custom instance of Ord, e.g. "instance Ord Machine where compare = compare `on` name". To sort the same type with distinct comparators, you'll obviously need to distinguish them, as in e.g. "osSort = sortBy (compare `on` os)".
- NateDad 11y ago
  So... you will still need 57 spots in the code where you define how to sort a type. Maybe my reference to sort.Interface is confusing people. When I say we have 57 implementations of sort.Interface, that's 57 different types and/or different ways of sorting one of those types. So, like, sorting Machine by Name would be one implementation, sorting Machine by Name then OS then RAM would be another implementation. You write an implementation of sort.Interface for every type, and for each way you would like to be able to sort it. An implementation of sort.Interface just requires three methods: Len() int // return the length of the list Swap(i, j int) // swap items at indices i and j Less(i, j int) bool // return true if list[i] is less than list[j] It's the implementation in Less that determines the order. That's not really so different than what you're describing in Haskell, it's just not part of the type, it's a new type that you convert the original type into, to pass into the sort.Sort() function (and because the underlying type is a slice, which is a glorified struct with a pointer to an array, that also sorts the original value).
  - infogulch 10y ago
    It's possible to make one implementation for a type that supports multiple orderings, at the cost of another indirection [0]. This turns O(N*M) implementations for N types and M sorting orders into just O(N). (I'm not counting an inline anonymous function as a new implementation.) In practice, it's rare to need to sort a slice more than one way. [0]: https://gist.github.com/infogulch/5db15e5ae5cf073f1088033ba4c714fb https://gist.github.com/infogulch/5db15e5ae5cf073f1088033ba4...
jimbokun 11y ago
The canonical solution to this problem is to provide a function to perform the comparison, or to require the types implement a "Sortable" or "Comparable" interface.
- NateDad 11y ago
  yes, which for 57 different types and/or comparison methods requires 57 different functions... which is basically the exact same thing you do in Go. It's just in go, you define a new type based on the original value, rather than just a function.
parenthephobia 11y ago
There are no languages where you can sort machines by either name, OS, or RAM without in some way saying which to sort by. That's a straw man: nobody is telling you that. But, you are being told there are multiple languages where you can sort machines by their fields without having to write type byName []Machine type byOS []Machine type byRAM []Machine func (a byName) Len () int { return len(a) } func (a byOS) Len () int { return len(a) } func (a byRAM) Len () int { return len(a) } func (a byName) Swap(i, j int) { a[i], a[j] = a[j], a[i] } func (a byOS) Swap(i, j int) { a[i], a[j] = a[i], a[i] } func (a byRAM) Swap(i, j int) { a[i], a[j] = a[j], a[i] } func (a byName) Less(i, j int) bool { return a[i].Name < a[j].Name } func (a byOS) Less(i, j int) bool { return a[i].RAM < a[i].RAM } func (a byRAM) Less(i, j int) bool { return a[i].OS < a[j].OS } sort.Sort(byName(machines)) sort.Sort(byOS(machines)) sort.Sort(byRAM(machines)) For example, in Julia, you can just do sort(machines, by=m->m.Name) sort(machines, by=m->m.OS) sort(machines, by=m->m.RAM) The equivalent is possible in any almost modern language. E.g. in C# machines.OrderBy(m=>m.Name) machines.OrderBy(m=>m.OS) machines.OrderBy(m=>m.RAM) In Haskell sortBy (comparing Name) machines sortBy (comparing OS) machines sortBy (comparing RAM) machines This is an extensively solved problem in modern programming languages. As a bonus, the opportunity for making an error each time you want to sort a new type of array in a new way is reduced if you only have to write one line of code each time.

by NateDad 11y ago

pklausler 11y ago

Sorting on all three fields in priority order is what I had in mind, and that's trivial in Haskell by adding "deriving(Ord)" to the data type definition and then just using the standard "sort :: Ord a => [a] -> [a]". If you're always going to sort them based on some (other) relation between the fields, make your type a custom instance of Ord, e.g. "instance Ord Machine where compare = compare `on` name". To sort the same type with distinct comparators, you'll obviously need to distinguish them, as in e.g. "osSort = sortBy (compare `on` os)".

NateDad 11y ago
So... you will still need 57 spots in the code where you define how to sort a type. Maybe my reference to sort.Interface is confusing people. When I say we have 57 implementations of sort.Interface, that's 57 different types and/or different ways of sorting one of those types. So, like, sorting Machine by Name would be one implementation, sorting Machine by Name then OS then RAM would be another implementation. You write an implementation of sort.Interface for every type, and for each way you would like to be able to sort it. An implementation of sort.Interface just requires three methods: Len() int // return the length of the list Swap(i, j int) // swap items at indices i and j Less(i, j int) bool // return true if list[i] is less than list[j] It's the implementation in Less that determines the order. That's not really so different than what you're describing in Haskell, it's just not part of the type, it's a new type that you convert the original type into, to pass into the sort.Sort() function (and because the underlying type is a slice, which is a glorified struct with a pointer to an array, that also sorts the original value).
- infogulch 10y ago
  It's possible to make one implementation for a type that supports multiple orderings, at the cost of another indirection [0]. This turns O(N*M) implementations for N types and M sorting orders into just O(N). (I'm not counting an inline anonymous function as a new implementation.) In practice, it's rare to need to sort a slice more than one way. [0]: https://gist.github.com/infogulch/5db15e5ae5cf073f1088033ba4c714fb https://gist.github.com/infogulch/5db15e5ae5cf073f1088033ba4...

jimbokun 11y ago

The canonical solution to this problem is to provide a function to perform the comparison, or to require the types implement a "Sortable" or "Comparable" interface.

NateDad 11y ago
yes, which for 57 different types and/or comparison methods requires 57 different functions... which is basically the exact same thing you do in Go. It's just in go, you define a new type based on the original value, rather than just a function.

parenthephobia 11y ago

There are no languages where you can sort machines by either name, OS, or RAM without in some way saying which to sort by. That's a straw man: nobody is telling you that. But, you are being told there are multiple languages where you can sort machines by their fields without having to write type byName []Machine type byOS []Machine type byRAM []Machine func (a byName) Len () int { return len(a) } func (a byOS) Len () int { return len(a) } func (a byRAM) Len () int { return len(a) } func (a byName) Swap(i, j int) { a[i], a[j] = a[j], a[i] } func (a byOS) Swap(i, j int) { a[i], a[j] = a[i], a[i] } func (a byRAM) Swap(i, j int) { a[i], a[j] = a[j], a[i] } func (a byName) Less(i, j int) bool { return a[i].Name < a[j].Name } func (a byOS) Less(i, j int) bool { return a[i].RAM < a[i].RAM } func (a byRAM) Less(i, j int) bool { return a[i].OS < a[j].OS } sort.Sort(byName(machines)) sort.Sort(byOS(machines)) sort.Sort(byRAM(machines)) For example, in Julia, you can just do sort(machines, by=m->m.Name) sort(machines, by=m->m.OS) sort(machines, by=m->m.RAM) The equivalent is possible in any almost modern language. E.g. in C# machines.OrderBy(m=>m.Name) machines.OrderBy(m=>m.OS) machines.OrderBy(m=>m.RAM) In Haskell sortBy (comparing Name) machines sortBy (comparing OS) machines sortBy (comparing RAM) machines This is an extensively solved problem in modern programming languages. As a bonus, the opportunity for making an error each time you want to sort a new type of array in a new way is reduced if you only have to write one line of code each time.