just a nice recursive snippet of code

[S.A. Asselbergs]

Hi All,
I just found out i can use any P->R function which I may like be recursive to adjust it a bit so it behaves like P->R->R and then just a simple piece of code that can turn it into a recursive function.
In my example I just made an ordinary counter. But of course, I bet it can be tinkered into handling curried(i mean partial functions) as a way more flexible means than P->R->R. I just like this code, maybe some newbe actually likes my little piece of code as well. I think it is pretty useful as a pattern. Anyways, just to share with anyone interested...


//FunctionExtentions.hx
@:callable
abstract RecursiveFunction1<P, R>(P -> R -> R){
public inline function new<P, R>(parameter:P -> R ->R){       
    this = parameter;
}

typedef RecursiveFunction2<P,R> = P->R->R

class FunctionExtentions{   
    public static function recursion1<P,R>(operation:RecursiveFunction1<P,R>, parameter:P, condition:R->Bool, result:R){
        trace('recursion1: $result');
        if (condition(operation(parameter, result))){
            return recursion1(operation, parameter, condition, operation(parameter, result));
        }
        return result;           
    }
    public static function recursion2<P,R>(operation:RecursiveFunction2<P,R>, parameter:P, condition:R->Bool, result:R){
        trace('recursion2: $result');
        if (condition(operation(parameter, result))){
            return recursion2(operation, parameter, condition, operation(parameter, result));
        }
        return result;           
    }   
}

//Main.hx
using FunctionExtentions;
// for example somewhere in static function main()
var rc = new RecursiveFunction1(function(p:Int, r:Int):Int{ return p + r; });
var f = function(p:Int, r:Int):Int{ return p + r; }
   
       
 rc.recursion1(1, function(r:Int):Bool{return r <= 10; }, 1);
 f.recursion2(1, function(r:Int):Bool{return r <= 10; }, 1);

[Mark Knol]

Neat!

I converted it to a try-haxe snippet: http://try.haxe.org/#42994

I wonder if it can be changed in a way so you don't need the two methods (recursion1 and recursion2).

[S.A. Asselbergs]

Hi mark,
The only difference is one uses a typdef, so you can directly use recursion on any function this way:

    typedef RecursiveFunction<P,R> = P->R->R
    public static function recursion<P,R>(operation:RecursiveFunction<P,R>, parameter:P, condition:R->Bool, result:R){
        trace('recursion: $result');
        if (condition(operation(parameter, result))){
            return recursion(operation, parameter, condition, operation(parameter, result));
        }
        return result;          
    }   

    class Foo{
        // any function that has its last argument of the same type, can be changed into a recursive function just by using
        // my pattern, if you have more parameters in your function, its easy to adapt my pattern, i show you beaneath later on
        public static function youCanEnableRecursionOnThisFunction(someString:String, someXml:Xml):Xml{
           //some code
        } 
        public function youCanEnableRecursionOnThisFunctionToo(someString:String, SomeXml:Xml):Xml {
           //some code
        }     
    }
    //or in main:
    var blaat=function(a:Int, b:Array<String>):Array<String>{
             //some code
              }
   


    // doing the recursion thing:
    var funct1=Foo.youCanEnableRecursionOnThisFunction.recursion(
    // your parameter,
    // conditionFunction: where false ends recursion and returns value,
    // the starting value of a parameter that is used to store your result in and is changed by each recursion until it can be returned as the end result of all recursion
    );
    var instance=new Foo();
    var funct2=instance.youCanEnableRecursionOnThisFunctionToo.recursion(/* put in your arguments here: parameter:String, condition:XML->Bool, result:Xml*/)
   
    blaat.recursion(/*put in your arguments here: parameter:Int, condition:Array<String>->Bool, result:Array<String>*/)

The other function uses an abstract. The interesting part of it, is that you can then choose to extend the functionality of ay function itself
by adding functions to the abstract (there you can use properties etc) or by "using" some static method that has its first parameter of type of that abstract
And interesting about abstract is that you can inline a lot as well.

    public static function recursion<P,R>(operation:RecursiveFunction<P,R>, parameter:P, condition:R->Bool, result:R){
        trace('recursion: $result');
        if (condition(operation(parameter, result))){
            return recursion(operation, parameter, condition, operation(parameter, result));
        }
        return result;          
    }   
   @:callable //only works if you add @:callable

   abstract RecursiveFunction1<P, R>(P -> R -> R){
   public inline function new<P, R>(parameter:P -> R ->R){      
       this = parameter;
   }

but the difference is that you need to instantiate it first before using it.
   var func3 = new RecursiveFunction(function(p:Int, r:Int):Int{ return p + r; });
   func3.recursion(1, function(r:Int):Bool{return r <= 10; }, 1);


Ok so what if you have a several functions that have 3 parameters
for example

   var f = function(p1:Json, p2:String, p3: Int, r:Xml):Xml{ /* your code*/ }
We can describe this function like this
   (Json->String->Int->Xml)->Xml
Which we can describe by Genrics like this
   (P1->P2->P3->R)->R

so to extending it with "using" it goes like this:

    public static function recursion<P1, P2, P3,R>(operation:RecursiveFunction<P,R>, p1:P1, p2:P2, p3:P3, condition:R->Bool, result:R){
        trace('recursion: $result');
        if (condition(operation(p1,p2,p3, result))){
            return recursion(operation, parameter, condition, operation(parameter, result));
        }
        return result;          
    }   

that simple,
or what if your conditions= to test if recursion is complete you need to compare 2 or more of those parameters (which maybe the case for example when recursing through xml):

    public static function recursion<P1, P2, P3,R>(operation:RecursiveFunction<P,R>, p1:P1, p2:P2, p3:P3, condition:R->P1->P2->Bool, result:R){
        trace('recursion: $result');
        if (condition(operation(p1,p2,p3, result),p1, p2)){
            return recursion(operation, parameter, condition, operation(parameter, result));
        }
        return result;          
    }      






Op vrijdag 14 oktober 2016 10:01:44 UTC+2 schreef Mark Knol:

[S.A. Asselbergs]

I have converted so now enum and abstract work with same recursion function:
http://try.haxe.org/#102f8

Op vrijdag 14 oktober 2016 10:01:44 UTC+2 schreef Mark Knol:

Neat!

[S.A. Asselbergs]

Now i also have inlined everything as well: http://try.haxe.org/#102f8

using Test.FunctionExtentions;

class Test {
    static function main() {

        var func = function(p, r):Int return p + r;
        var recursive = new RecursiveFunction1(func);

        // using abstract. returns result of recursion
           var result1 = recursive.recursion(1, function(r) return r <= 10, 1);
       
         // using function. returns result of recursion
           var result2 = func.recursion(1, function(r) return r <= 10, 1);
       
        trace(result1);
        trace(result2);
    }
}

@:callable
abstract RecursiveFunction1<P, R>(P -> R -> R) from P -> R -> R to P -> R -> R{

    public inline function new<P, R>(parameter:P->R->R) {       
        this = parameter;
    }

    @:to
    public inline function toFunction():P -> R -> R{
        return this;
    }
    @:from
    public static inline function fromFunction<P,R>(funct:P -> R -> R):RecursiveFunction1<P, R>{
        return new RecursiveFunction1<P,R>(funct);
    }
}

typedef RecursiveFunction2<P,R> = P->R->R;
//  static function test<T:(Iterable<String>, Measurable)>(a:T) {
class FunctionExtentions {   
    public static inline function recursion<P,R>(operation:P->R->R, parameter:P, condition:R->Bool, result:R) {
        trace('recursion: $result');
        if (condition(operation(parameter, result))){
            return recursion(operation, parameter, condition, operation(parameter, result));
        }
        return result;           
    }
}


 it generates some neat code in js:

Test.main = function() {
    var func = function(p,r) {
        return p + r;
    };
    var recursive = func;
    var tmp;
    console.log("recursion: " + "1");
    var tmp2;
    var r1 = recursive(1,1);
    tmp2 = r1 <= 10;
    if(tmp2) tmp = FunctionExtentions.recursion(recursive,1,function(r2) {
        return r2 <= 10;
    },recursive(1,1)); else tmp = 1;
    var result1 = tmp;
    var tmp1;
    console.log("recursion: " + "1");
    var tmp3;
    var r3 = func(1,1);
    tmp3 = r3 <= 10;
    if(tmp3) tmp1 = FunctionExtentions.recursion(func,1,function(r4) {
        return r4 <= 10;
    },func(1,1)); else tmp1 = 1;
    var result2 = tmp1;
    console.log(result1);
    console.log(result2);
};
var FunctionExtentions = function() { };
FunctionExtentions.__name__ = true;
FunctionExtentions.recursion = function(operation,parameter,condition,result) {
    console.log("recursion: " + Std.string(result));
    if(condition(operation(parameter,result))) return FunctionExtentions.recursion(operation,parameter,condition,operation(parameter,result));
    return result;
};
Op vrijdag 14 oktober 2016 12:31:10 UTC+2 schreef S.A. Asselbergs:

[S.A. Asselbergs]

I edited a bit more: http://try.haxe.org/#FDB0f

Op vrijdag 14 oktober 2016 12:42:37 UTC+2 schreef S.A. Asselbergs:

[Laurence Taylor]

This is a Y-Combinator, or something similarm right?

regards,

Laurence

--
To post to this group haxe...@googlegroups.com
http://groups.google.com/group/haxelang?hl=en
---
You received this message because you are subscribed to the Google Groups "Haxe" group.
For more options, visit https://groups.google.com/d/optout.

[Simon Krajewski]

Am 14.10.2016 um 12:47 schrieb S.A. Asselbergs:
> I edited a bit more: http://try.haxe.org/#FDB0f

I wonder if that should compile given the recursive inline function. I
remember that at some point this would give an error, but it doesn't do
that anymore. The problem is that this blows up at run-time if the
inline function is made @:extern.

On a positive note, the generated JavaScript looks much better on a more
recent Haxe version: http://try-haxe.mrcdk.com/#bF852

Simon

[S.A. Asselbergs]

Hi Laurence,
I never heard of Y-Combinator until you mentioned. It's a bit less advanced than Y-Combinator, but because of that I think a bit more efficient and easier to grasp and implement, since haxe is a stric, strongly typed imperative programming language. Y-Combinators lend themselves better to declarative languages (functional languages). This pattern happened when I sat down and try to figure how I could patternise recursion, and it works and reads very well.

Op vrijdag 14 oktober 2016 13:57:10 UTC+2 schreef Laurence Taylor:

[S.A. Asselbergs]

It's gets even better. I am busy with haxe C#, a relative young target. Guess what? It compiles beautifully :-)
That said, because C# is a young target you dont want to look at the generated code (no you really dont want). But I am having such a ball with haxe C# :-)

Op vrijdag 14 oktober 2016 14:42:06 UTC+2 schreef Simon Krajewski:

[Laurence Taylor]

I think the last step is to make recursion a parameter rather than a class / instance member, and call that function y.

I think there is some stuff around ML and F# which shows how to do the Y combinator in an eagerly evaluated language.

good luck,
Laurence

p.s no, I don't understand the y combinator right now.

​

--

[Cambiata]

But I am having such a ball with haxe C# :-)

Please excuse an curious off-topic question, S. A: What are you developing with Haxe C#?

/ Jonas

[S.A. Asselbergs]

hahaha curious people always put a smile on my face. I am using the xml and json of the Unity manual to generate real code stubs and externs. I want to make a scripting mod (with haxe C#) for Besiege (a very very cool physics building game). Besiege is made with unity, and there is already a modloader that does the bytcode hacking. The scripting language will be python 3.5 (i found iron python for that role)

--

To post to this group haxe...@googlegroups.com
http://groups.google.com/group/haxelang?hl=en
---

You received this message because you are subscribed to a topic in the Google Groups "Haxe" group.

[S.A. Asselbergs]

sorry code stubs and externs to interface with unity