Rosetta Code

Decorate-sort-undecorate idiom: Difference between revisions

Page Discussion

Decorate-sort-undecorate idiom (view source)

Revision as of 18:02, 11 March 2024

5,293 bytes added ,  3 months ago
m
→‎{{header|Fōrmulæ}}
 
(21 intermediate revisions by 13 users not shown)
Line 1:
{{task}}
 
[[Category:Sorting]]
 
;Introduction
Line 212 ⟶ 214:
</pre>
 
=={{header|FactorC sharp|C#}}==
Linq makes this very easy. We can do this using 2 different syntaxes:
{{works with|Factor 0.99 build 2207}}
<syntaxhighlight lang="csharp">
The easiest way is to define your key function as a memoized word. Memoized words store input/output pairs and simply fetch the outputs of inputs they've seen before. Then using the usual <code>sort-by</code> combinator won't recalculate any extraneous lengths.
public static IEnumerable<T> Schwartzian1<T, TKey>(IEnumerable<T> source, Func<T, TKey> decorator) =>
<syntaxhighlight lang="factor">
source.Select(item => (item, key: decorator(item)))
USING: prettyprint sequences sorting ;
.OrderBy(tuple => tuple.key)
.Select(tuple => tuple.item);
 
public static IEnumerable<T> Schwartzian2<T, TKey>(IEnumerable<T> source, Func<T, TKey> decorator) =>
MEMO: length* ( seq -- n ) length ;
from item in source
let key = decorator(item)
orderby key
select item;
 
//Call:
{ "Rosetta" "Code" "is" "a" "programming" "chrestomathy" "site" }
string[] array = {"Rosetta", "Code", "is", "a", "programming", "chrestomathy", "site"};
[ length* ] sort-by .
Console.WriteLine(string.Join(" ", Schwartzian1(array, i => i.Length)));
</syntaxhighlight>
{{out}}
<pre>
a is Code site Rosetta programming chrestomathy
</pre>
 
=={{header|C++}}==
A more direct implementation would be:
<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>
 
=={{header|Factor}}==
{{works with|Factor|0.99}}
<code>map-sort</code> employs the decorate-sort-undecorate idiom, while <code>sort-by</code> does not.
<syntaxhighlight lang="factor">
USING: assocs prettyprint sequences sorting.extras ;
 
{ "Rosetta" "Code" "is" "a" "programming" "chrestomathy" "site" }
[ length ] zipmap-withsort .
[ last ] sort-by
keys .
</syntaxhighlight>
{{out}}
Line 300 ⟶ 351:
'''Solution'''
 
Let us create aan listarray for testing:
 
[[File:Fōrmulæ - Decorate-sort-undecorate idiom 01.png]]
Line 313 ⟶ 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 418 ⟶ 470:
"programming"
"chrestomathy"</pre>
 
=={{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).
 
Thus, for example:
 
<syntaxhighlight lang=J> >(/: #@>) ;:'Rosetta Code is a programming chrestomathy site'
a
is
Code
site
Rosetta
programming
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 596 ⟶ 697:
 
=={{header|Kotlin}}==
Kotlin already has a `sortedWith` function that takes a custom comparator, so there is no need to write such a function; however, one is shown here as a code example.
<syntaxhighlight lang="kotlin">
fun main() {
val list = listOf("Rosetta", "Code", "is", "a", "programming", "chrestomathy", "site")
println(sorted(list, .sortedBySchwartzian(String::length))
}
 
/**
fun <T, C: Comparable<C>> sorted(list: Collection<T>, keyFn: (T) -> C): List<T> =
* Returns a sorted list using the Schwartzian Transform which guarantees minimal use of the
list
* key extractor function. Use when the key extractor function is an expensive operation.
.map { it to keyFn(it) }
*/
fun <T, R: Comparable<R>> Collection<T>.sortedBySchwartzian(keyFn: (T) -> R): List<T> =
this.map { it to keyFn(it) }
.sortedBy { it.second }
.map { it.first }
Line 643 ⟶ 746:
<pre>a is site Code Rosetta programming chrestomathy
chrestomathy programming Rosetta Code site is a</pre>
 
{{incorrect|Lua|recalculates length on every comparison}}
However, for this same reason, there is no point doing the decorate, sort, undecorate in practice. You can simply do this:
<syntaxhighlight lang="lua">function lengthOrder (a, b)
return #a < #b
end
 
local list = {"Rosetta", "Code", "is", "a", "programming", "chrestomathy", "site"}
table.sort(list, lengthOrder)
print(unpack(list))</syntaxhighlight>
{{out}}
<pre>a is site Code Rosetta programming chrestomathy</pre>
 
=={{header|Nim}}==
Line 679 ⟶ 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 775 ⟶ 907:
programming
chrestomathy</pre>
 
=={{header|Quackery}}==
 
<syntaxhighlight lang="Quackery"> [ ]'[ temp put
[] swap witheach
[ dup temp share do
dip nested join
nested join ]
temp release ] is decoratewith ( [ --> [ )
 
[ [] swap witheach
[ 0 peek nested join ] ] is undecorate ( [ --> [ )
 
$ "Rosetta Code is a programming chrestomathy site" nest$
 
decoratewith size
sortwith [ dip [ 1 peek ] 1 peek > ]
undecorate
witheach [ echo$ sp ]</syntaxhighlight>
 
{{out}}
 
<pre>a is Code site Rosetta programming chrestomathy</pre>
 
=={{header|Raku}}==
Line 877 ⟶ 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 884 ⟶ 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="ecmascriptwren">var schwartzian = Fn.new { |a, f|
System.print(a.map { |e| [e, f.call(e)] } // decorate
.toList
Laurence
2,120

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/347754...361736"