lambda recursion
ddcovery
antoniocabreraperez at gmail.com
Fri Nov 27 16:40:43 UTC 2020
I want to express in D the known Haskell qsort 3 lines code (it
is not a quick sort, but an example of how functional programming
is expressive).
This is the "javascript" version I use as reference:
const sorted = ( [pivot, …others] ) => pivot===void 0 ? [ ] :
[
… sorted( others.filter( n=> n<pivot ) ),
pivot,
… sorted( others.filter( n=> n>=pivot ) )
];
This is a possible D implementation:
void main()
{
import std.stdio, std.algorithm, std.range;
int[] delegate(int[]) qs;
qs = (int[] items) => items.length==0 ? items :
chain(
qs(items[1..$].filter!(i=> i<items[0] ).array),
items[0..1],
qs(items[1..$].filter!(i=> i >= items[0]).array)
).array;
auto result = qs([10,9,5,4,8,7,-20]);
assert( result.equal([-20,4,5,7,8,9,10]) );
writeln("Result:", result );
}
First problem I found is "qs" must be splitted in 2 expressions:
declaration and assignation, because declaration is not
"effective" until all expression is compiled (compiler says qs
doesn't exist when compiling the lambda body) .
* Is there any way to reduce the code(using lambdas) to one
expression only?
int[] delegate(int[]) qs = (int[] items) => items.length==0
.....
Or better
auto qs = (int[] items) => items.length==0 ? ...
* Can the lambda be transformed to a template (using T instead
"int") but avoiding function/return syntax?
This is an example using function
template qs(T){
T[] qs( T[] items ){
return items.length==0
? items
: chain(
qs(items[1..$].filter!(i=> i<items[0] ).array),
items[0..1],
qs(items[1..$].filter!(i=> i >= items[0]).array)
).array;
}
}
* I'm trying to use "ranges" to avoid the "array" conversion. Do
you figure out a way to express the lambda params and return as a
Range to avoid converting to array?
More information about the Digitalmars-d-learn
mailing list