Decorate-sort-undecorate idiom: Difference between revisions
m
→{{header|Fōrmulæ}}
(J draft) |
|||
| (15 intermediate revisions by 8 users not shown) | |||
Line 1:
{{task}}
[[Category:Sorting]]
;Introduction
Line 210 ⟶ 212:
<pre>
["a", "is", "Code", "site", "Rosetta", "programming", "chrestomathy"]
</pre>
=={{header|C sharp|C#}}==
Linq makes this very easy. We can do this using 2 different syntaxes:
<syntaxhighlight lang="csharp">
public static IEnumerable<T> Schwartzian1<T, TKey>(IEnumerable<T> source, Func<T, TKey> decorator) =>
source.Select(item => (item, key: decorator(item)))
.OrderBy(tuple => tuple.key)
.Select(tuple => tuple.item);
public static IEnumerable<T> Schwartzian2<T, TKey>(IEnumerable<T> source, Func<T, TKey> decorator) =>
from item in source
let key = decorator(item)
orderby key
select item;
//Call:
string[] array = {"Rosetta", "Code", "is", "a", "programming", "chrestomathy", "site"};
Console.WriteLine(string.Join(" ", Schwartzian1(array, i => i.Length)));
</syntaxhighlight>
{{out}}
<pre>
a is Code site Rosetta programming chrestomathy
</pre>
=={{header|C++}}==
<syntaxhighlight lang="cpp">#include <algorithm>
#include <iostream>
#include <type_traits>
#include <vector>
template <typename Iterator, typename Function>
void decorate_sort_undecorate(Iterator begin, Iterator end, Function f) {
using ValueType = typename std::iterator_traits<Iterator>::value_type;
using KeyType = std::invoke_result_t<Function, ValueType>;
using KeyValue = std::pair<KeyType, ValueType>;
std::vector<KeyValue> tmp;
tmp.reserve(std::distance(begin, end));
std::transform(begin, end, std::back_inserter(tmp), [&f](ValueType& v) {
return std::make_pair(f(v), std::move(v));
});
std::sort(tmp.begin(), tmp.end(), [](const KeyValue& a, const KeyValue& b) {
return a.first < b.first;
});
std::transform(tmp.begin(), tmp.end(), begin,
[](KeyValue& p) { return std::move(p.second); });
}
int main() {
std::string test[] = {"Rosetta", "Code", "is", "a",
"programming", "chrestomathy", "site"};
decorate_sort_undecorate(std::begin(test), std::end(test),
[](const std::string& s) { return s.size(); });
for (const std::string& s : test)
std::cout << s << ' ';
std::cout << '\n';
}</syntaxhighlight>
{{out}}
<pre>
a is Code site Rosetta programming chrestomathy
</pre>
Line 288 ⟶ 351:
'''Solution'''
Let us create
[[File:Fōrmulæ - Decorate-sort-undecorate idiom 01.png]]
Line 301 ⟶ 364:
[[File:Fōrmulæ - Decorate-sort-undecorate idiom 04.png]]
'''Schwartzian transform:''' The following is a solution using a "Schwartzian transform" idiom, and it produces identical results:
Line 408 ⟶ 472:
=={{header|J}}==
J's native sort primitive always sorts on a key (which might be the list itself), such that each element of the key is calculated only once. This corresponds to APL's grade up primitive (though comparing dates on this approach vs. lisp's approach seems problematic due to deficiencies in historical evidence).
Line 422 ⟶ 485:
chrestomathy
</syntaxhighlight>
=={{header|Java}}==
<syntaxhighlight lang="java">
import java.util.AbstractMap;
import java.util.List;
import java.util.function.Function;
import java.util.stream.Collectors;
public final class DecorateSortUndecorateIdiom {
public static void main(String[] args) {
List<String> list = List.of( "Rosetta", "Code", "is", "a", "programming", "chrestomathy", "site" );
System.out.println(schwartzian(list, s -> s.length()));
}
/**
* Return a sorted list using the Schwartzian Transform
* which guarantees minimal use of the key extractor function.
*
* Use this method when the key extractor function is an expensive operation.
*/
private static <T, R extends Comparable<R>> List<T> schwartzian(List<T> list, Function<T, R> function) {
return list.stream().map( s -> new AbstractMap.SimpleEntry<T, R>(s, function.apply(s)) )
.sorted( (one, two) -> one.getValue().compareTo(two.getValue()) )
.map( p -> p.getKey() )
.collect(Collectors.toList());
}
}
</syntaxhighlight>
{{ out }}
<pre>
[a, is, Code, site, Rosetta, programming, chrestomathy]
</pre>
=={{header|JavaScript}}==
Line 673 ⟶ 770:
Of course, it is also possible to define a comparison function to sort by length then alphabetically and use it when sorting.
=={{header|Nu}}==
<syntaxhighlight lang="nu">
def 'sort by key' [keyfunc] {
( each {|v| {k: ($v | do $keyfunc ), v: $v}}
| sort-by k
| each {get v} )
}
"Rosetta Code is a programming chrestomathy site" | split words | sort by key {str length}
</syntaxhighlight>
{{out}}
<pre>
╭───┬──────────────╮
│ 0 │ a │
│ 1 │ is │
│ 2 │ Code │
│ 3 │ site │
│ 4 │ Rosetta │
│ 5 │ programming │
│ 6 │ chrestomathy │
╰───┴──────────────╯
</pre>
=={{header|Perl}}==
<syntaxhighlight lang="perl">#!/usr/bin/perl
use strict; # https://rosettacode.org/wiki/Decorate-sort-undecorate_idiom
use warnings;
use List::AllUtils qw( nsort_by );
my @list = ("Rosetta", "Code", "is", "a", "programming", "chrestomathy", "site");
print "@list\n";
my @sortedlist = nsort_by { length } @list;
print "@sortedlist\n";</syntaxhighlight>
{{out}}
<pre>
Rosetta Code is a programming chrestomathy site
a is Code site Rosetta programming chrestomathy
</pre>
=={{header|Phix}}==
Line 894 ⟶ 1,032:
cached: ["a", "is", "Code", "site", "Rosetta", "programming", "chrestomathy"]
transform: ["a", "is", "Code", "site", "Rosetta", "programming", "chrestomathy"]
</pre>
=={{header|Sidef}}==
<syntaxhighlight lang="ruby">var str = "Rosetta Code is a programming chrestomathy site"
# Built-in
say str.split.sort_by{.len}
# Same thing explicitly
say str.split.map {|w| [w, w.len] }.sort{|a,b| a[1] <=> b[1] }.map { _[0] }
# Sort by word length, then lexical:
var str2 = str+" seven extra words added to this demo"
say str2.split.sort_by{|word| [word.len, word] }</syntaxhighlight>
{{out}}
<pre>
["a", "is", "Code", "site", "Rosetta", "programming", "chrestomathy"]
["a", "is", "Code", "site", "Rosetta", "programming", "chrestomathy"]
["a", "is", "to", "Code", "demo", "site", "this", "added", "extra", "seven", "words", "Rosetta", "programming", "chrestomathy"]
</pre>
Line 901 ⟶ 1,058:
It's not specified how words of equal length are to be sorted. The standard sort() method used here (quicksort under the hood) is unstable and so the sort order for such words is not guaranteed.
<syntaxhighlight lang="
System.print(a.map { |e| [e, f.call(e)] } // decorate
.toList
| |||