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