Decorate-sort-undecorate idiom: Difference between revisions
Thundergnat (talk | contribs) m →{{header|Raku}}: Add a Raku example |
More than 5 solutions, promoted to non-draft task |
||
Line 1: | Line 1: | ||
{{ |
{{task}} |
||
;Introduction |
;Introduction |
||
Line 31: | Line 31: | ||
;The Schwartzian transform |
;The Schwartzian transform |
||
Randal L. Schwartz wrote an implementation of the decorate-order-undecorate |
Randal L. Schwartz wrote an implementation of the decorate-order-undecorate idiom in Perl in 1994, which gained much popularity in the Perl community. It was named [[wp:Schwartzian transform|"Schwartzian transform"]]. Today the terms decorate-order-undecorate and the Schwartzian transform are used interchangeably, even outside the Perl community. |
||
The [[wp:Schwartzian transform|Wikipedia page]] states that a solution can be called a "Schwartzian transform" only if it does not use named temporary lists or arrays. The Lisp solution and even the solution shown by Schwartz actually use intermediate lists, but these lists do not have explicit names, instead they use a functional composition of map-sort-map operations. |
The [[wp:Schwartzian transform|Wikipedia page]] states that a solution can be called a "Schwartzian transform" only if it does not use named temporary lists or arrays. The Lisp solution and even the solution shown by Schwartz actually use intermediate lists, but these lists do not have explicit names, instead they use a functional composition of map-sort-map operations. |
Revision as of 15:12, 28 July 2023
![Task](http://static.miraheze.org/rosettacodewiki/thumb/b/ba/Rcode-button-task-crushed.png/64px-Rcode-button-task-crushed.png)
You are encouraged to solve this task according to the task description, using any language you may know.
- Introduction
Suppose you have to sort a list of strings based on a property of each, called "the key", i.e. their lenghts. The most popular solution would require the use of a sorting algorithm with a custom comparator.
Now suppose that key computation is an expensive operation, for example, it might involve intensive reading of files, databases, or exchanging information over a network. In such a case, using a sorting algorithm with a custom comparator is not optimal, because the key is computed multiple times for each element in the array, once each time the element needs to be compared to another (and also requires the calculation of the key for that other).
- The decorate-sort-undecorate idiom
One solution of the problem is called the "decorate-sort-undecorate" idiom, pattern or technique. It was originated and named by the Lisp community.
Suppose we want to sort the following list of words according to their lengths (the length was chosen for illustrative purposes, it is not precisely an "expensive" operation).
{"Rosetta", "Code", "is", "a", "programming", "chrestomathy", "site"}
According to the decorate-sort-decorate idiom, we have to "decorate" each element with its key, so each element of the original list becomes a pair. Notice that the key is calculated once (and only once) for each element in the list:
{{"Rosetta", 7}, {"Code", 4}, {"is", 2}, {"a", 1}, {"programming", 11}, {"chrestomathy", 12}, {"site", 4}}
The list is then sorted according to the second element of each pair (the key), perhaps using a custom comparator:
{{"a", 1}, {"is", 2}, {"site", 4}, {"Code", 4}, {"Rosetta", 7}, {"programming", 11}, {"chrestomathy", 12}}
And finally, the list must be undecorated, we have to remove the second element of each pair (the key):
{"a", "is", "site", "Code", "Rosetta", "programming", "chrestomathy"}
So, the decoration acts as a form of memoization.
- The Schwartzian transform
Randal L. Schwartz wrote an implementation of the decorate-order-undecorate idiom in Perl in 1994, which gained much popularity in the Perl community. It was named "Schwartzian transform". Today the terms decorate-order-undecorate and the Schwartzian transform are used interchangeably, even outside the Perl community.
The Wikipedia page states that a solution can be called a "Schwartzian transform" only if it does not use named temporary lists or arrays. The Lisp solution and even the solution shown by Schwartz actually use intermediate lists, but these lists do not have explicit names, instead they use a functional composition of map-sort-map operations.
- Task
Write in your programming language, a function, procedure, method, routine, etc. to sort a list of words by length (the key function), using the decorate-sort-undecorate idiom.
- Bonus 1. If your solution can accept the key function as a callback.
- Bonus 2. If your solution is also a "Schwartzian transform", this is, it does not use named temporary lists/arrays.
You can, at your choice, show two solutions, the first using intermediate named lists/arrays, and the second one not using them (a Schwartzian transform)(if applicable). The first solution is sometimes more valuable, because the use of named entities makes the code clearer.
- References
- Wikipedia: Schwartzian transform
ALGOL 68
Algol 68 doesn't have standard mapping operators, but it is easy enough to construct some, as shown here.
Note, Algol 68 doesn't have procedure overloading but does have operator overloading.
If decorating other than STRINGs with INTs was required, different MODEs and OPs would be needed. As the MODE of the decorated result would be implied by the MODE yielded by the decorating procedure, the same names could be used for the DECORATE, UNDECORATE and SORT operators, only the name of the decorated MODE would be different.
BEGIN # Schwartzian transform - decorate a list of strings, sort them and #
# undecorate them #
# being strongly typed, Algol 68 would require different modes for each #
# possible decoration - here we decorate a row of strings with an #
# integer #
# mode to hold a decorated string #
MODE STRINGWITHINT = STRUCT( STRING v, INT d );
# decorates a with INT values using the dp procedure #
PRIO DECORATE = 1; # DECORATE is dyadic so need a priority: use lowest #
OP DECORATE = ( []STRING a, PROC( STRING )INT dp )[]STRINGWITHINT:
BEGIN
REF[]STRINGWITHINT result = HEAP[ LWB a : UPB a ]STRINGWITHINT;
FOR i FROM LWB a TO UPB a DO
result[ i ] := STRINGWITHINT( a[ i ], dp( a[ i ] ) )
OD;
result
END # DECORATE # ;
# returns a undecorated #
OP UNDECORATE = ( []STRINGWITHINT a )[]STRING:
BEGIN
REF[]STRING result = HEAP[ LWB a : UPB a ]STRING;
FOR i FROM LWB a TO UPB a DO
result[ i ] := v OF a[ i ]
OD;
result
END # UNDECORATE # ;
# returns TRUE if a < b #
OP < = ( STRINGWITHINT a, b )BOOL:
d OF a < d OF b OR ( d OF a = d OF b AND v OF a < v OF b );
# returns TRUE if a > b #
OP > = ( STRINGWITHINT a, b )BOOL:
d OF a > d OF b OR ( d OF a = d OF b AND v OF a > v OF b );
# sorts a into order of each elements d and v #
OP SORT = ( []STRINGWITHINT a )[]STRINGWITHINT:
BEGIN
# in-place quick sort an array of STRINGWITHINTs from element lb #
# to element ub #
PROC quicksort = ( REF[]STRINGWITHINT a, INT lb, ub )REF[]STRINGWITHINT:
IF ub <= lb
THEN
# empty array or only 1 element #
a
ELSE
# more than one element, so must sort #
INT left := lb;
INT right := ub;
# choosing the middle element of the array as the pivot #
STRINGWITHINT pivot := a[ left + ( ( right + 1 ) - left ) OVER 2 ];
WHILE
WHILE IF left <= ub THEN a[ left ] < pivot ELSE FALSE FI
DO
left +:= 1
OD;
WHILE IF right >= lb THEN a[ right ] > pivot ELSE FALSE FI
DO
right -:= 1
OD;
left <= right
DO
STRINGWITHINT t := a[ left ];
a[ left ] := a[ right ];
a[ right ] := t;
left +:= 1;
right -:= 1
OD;
quicksort( a, lb, right );
quicksort( a, left, ub );
a
FI # quicksort # ;
quicksort( HEAP[ LWB a : UPB a ]STRINGWITHINT := a, LWB a, UPB a )
END # SORT # ;
# prints the elements of a enclosed in quotes with separating commas #
OP SHOWQUOTED = ( []STRING a )VOID:
BEGIN
print( ( "[" ) );
STRING separator := " ";
FOR i FROM LWB a TO UPB a DO
print( ( separator, """", a[ i ], """" ) );
separator := ", "
OD;
print( ( " ]" ) )
END # SHOWQUOTED # ;
# task test case #
SHOWQUOTED UNDECORATE SORT ( []STRING( "Rosetta", "Code", "is", "a", "programming", "chrestomathy", "site" )
DECORATE ( ( STRING v )INT: ( UPB v - LWB v ) + 1 )
)
END
- Output:
[ "a", "is", "Code", "site", "Rosetta", "programming", "chrestomathy" ]
Fōrmulæ
Fōrmulæ programs are not textual, visualization/edition of programs is done showing/manipulating structures but not text. Moreover, there can be multiple visual representations of the same program. Even though it is possible to have textual representation —i.e. XML, JSON— they are intended for storage and transfer purposes more than visualization and edition.
Programs in Fōrmulæ are created/edited online in its website.
In this page you can see and run the program(s) related to this task and their results. You can also change either the programs or the parameters they are called with, for experimentation, but remember that these programs were created with the main purpose of showing a clear solution of the task, and they generally lack any kind of validation.
Solution
Let us create a list for testing:
Decorate-sort-undecorate: The following is a solution using a decorate-sort-undecorate idiom:
Test case
Schwartzian transform: The following is a solution using a "Schwartzian transform" idiom, and it produces identical results:
JavaScript
function schwartzian(array, keyFn) {
return array
.map((e) => [e, keyFn(e)])
.sort((a, b) => a[1] - b[1])
.map((e) => e[0]);
}
const example = [
"Rosetta",
"Code",
"is",
"a",
"programming",
"chrestomathy",
"site",
];
console.log(schwartzian(example, (e) => e.length));
- Output:
[ 'a', 'is', 'Code', 'site', 'Rosetta', 'programming', 'chrestomathy' ]
Note that Array.prototype.sort()
takes an optional compare function that should return a negative integer, a positive integer or zero, depending on whether a
is less than, greater than or equal to b
. As is, the above implementation of schwartzian()
would fail if keyFn
returned a string, for example.
We could generalize schwartzian()
to fallback to a comparison of the string representation of a
and b
, if they don't support the subtraction operator, and allow calling functions provide a custom compare function.
function schwartzian(array, keyFn, compareFn) {
const defaultCompareFn = (a, b) =>
a[1] - b[1] || String(a[1]).localeCompare(String(b[1]));
return array
.map((e) => [e, keyFn(e)])
.sort(compareFn || defaultCompareFn)
.map((e) => e[0]);
}
const example = [
"Rosetta",
"Code",
"is",
"a",
"programming",
"chrestomathy",
"site",
];
console.log(schwartzian(example, (e) => e.length));
// keyFn is the string in reverse
console.log(schwartzian(example, (e) => Array.from(e).reverse().join("")));
- Output:
[ 'a', 'is', 'Code', 'site', 'Rosetta', 'programming', 'chrestomathy' ] [ 'a', 'Rosetta', 'Code', 'site', 'programming', 'is', 'chrestomathy' ]
jq
Also works with both jaq and gojq, the Rust and Go implementations of jq
jq has a built-in function, `sort_by(decorator)`, which in effect allows a decorator function to be specified, so that for the task at hand, one could simply write `sort_by(length)`, as illustrated below.
In the following, we also define a function (named `sort_by_decorator(decorator)`) that implements the decorate-sort-undecorate technique by "decorating" the list items with the specified decorator.
def sort_by_decorator(decorator):
map([decorator, .]) # decorate
| sort_by(.[0]) # sort by decorator
| map(.[1]) # undecorate
;
# Illustration
["Rosetta", "Code", "is", "a", "programming", "chrestomathy", "site"]
| sort_by(length), sort_by_decorator(length)
- Output:
["a","is","Code","site","Rosetta","programming","chrestomathy"] ["a","is","Code","site","Rosetta","programming","chrestomathy"]
Julia
julia> schwartzian(arr, f) = map(t -> t[1], sort!(map(v -> (v, f(v)), arr), by = t -> t[2])) schwartzian (generic function with 1 method) julia> schwartzian(["Rosetta", "Code", "is", "a", "programming", "chrestomathy", "site"], length) 7-element Vector{String}: "a" "is" "Code" "site" "Rosetta" "programming" "chrestomathy"
Python
def schwartzian(arr, f):
return [t[0] for t in sorted([(v, f(v)) for v in arr], key=lambda t: t[1])]
TEST = ["Rosetta", "Code", "is", "a", "programming", "chrestomathy", "site"]
print(TEST, "=>", schwartzian(TEST, len))
- Output:
['Rosetta', 'Code', 'is', 'a', 'programming', 'chrestomathy', 'site'] => ['a', 'is', 'Code', 'site', 'Rosetta', 'programming', 'chrestomathy']
Raku
It is somewhat rare to do, or even need to do an explicit schwartzian transform in Raku. You can pass a transform function to the sort operator, and it will use it to do its comparisons. As long as the transform is arity one (only takes one value,) the sort will automatically perform a schwartzian transform transparently, behind the scenes.
Here the transform .chars
is arity one, so a schwartzian transform is performed automatically by the compiler.
# automatic schwartzian transform
dd <Rosetta Code is a programming chrestomathy site>.sort: *.chars;
# explicit schwartzian transform
dd <Rosetta Code is a programming chrestomathy site>.map({$_=>.chars}).sort({.value}).map({.key});
- Output:
( dd
is the built in "data-dumper" function; a verbose and explicit representation of an objects contents.)
("a", "is", "Code", "site", "Rosetta", "programming", "chrestomathy").Seq ("a", "is", "Code", "site", "Rosetta", "programming", "chrestomathy").Seq
More complicated transforms may require an explicit schwartzian transform routine. An example of where an explicit transform is desirable is the schwartzian()
routine in the Raku entry for the P-value_correction task.
Wren
Wren doesn't normally print string lists in "quoted" form though I've added the quotes here to be consistent with the other solutions.
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.
var schwartzian = Fn.new { |a, f|
System.print(a.map { |e| [e, f.call(e)] } // decorate
.toList
.sort { |p, q| p[1] < q[1] } // sort
.map { |p| "\"%(p[0])\"" } // undecorate
.toList)
}
var words = ["Rosetta", "Code", "is", "a", "programming", "chrestomathy", "site"]
var length = Fn.new { |s| s.count }
schwartzian.call(words, length)
- Output:
["a", "is", "site", "Code", "Rosetta", "programming", "chrestomathy"]