Permutations in pure functional ActionScript

2 04 2011

I have been working with ActionScript3 and Flex to do apps for Android. I have never used this languages before, so in the beginning I was with my hart open to understand this languages, specially ActionScript3, the only thing I knew about ActionScript is that is used a lot for flash animations and that was it.

At a first glance ActionScript3 seemed to me to be a standard object oriented language, but after I grasp a little bit more and I found that the version 3 has a lot of functional flavor in it.
I started to find more and more examples of it: definition of high-order functions, map, filter and so…

I have to say that I deeply continue to prefer the Haskell notation with concern to high order and the 2 functions, but the point of ActionScript3 was never be totally functional, but incorporate some features of it.

So, outside of work I remember the beautiful definition of permutations in Haskell and I start try to implement the same algorithm in ActionScript3.

perms xs = [x:ps | x <- xs, ps <- perms (xs\\[x])]

For the non Haskell programmers I will explain: We receive the list xs and here use the list comprehension notation, basically we can translate a list comprehension in the form:
[f~x | x \leftarrow list] as a map function this way map~f~list. So, that’s basically the first part of our definition. The second one [x:ps | x \leftarrow list, ps \leftarrow perms(list_2)] is the cartesian product of the two lists.
Finally the definition of the function xs//[x] is simply the exclusion of the element x from the list xs.

So, I first came out with this solution:

public static function perms(xs:Array):Array {
    if(xs.length == 0) {
        return [[]];
    }   
    return xs.map(
        function(x:*,index:uint,array:Array):* {
            var ret:Array = new Array();
            var p:Array = perms( exclude(xs,x) );
            for(var j:uint=0 ; p[j] ; j++) {
                var ps:Array = p[j] as Array;
                ps.unshift(x);
                ret.push(ps);
            }   
            return ret;
        }   
    );  
}

public static function exclude(xs:Array, elem:*):Array {
    return xs.filter(
        function(item:*,index:uint,array:Array):Boolean { return item != elem; }
    );  
}

I had to define the exclude function, because it does not exist in ActionScript3 and I understand that.
The code is not as pretty as you expect to be in Haskell or other functional language, but is pretty much the same, as you ca see in the following definition, where I only use map.

public static function permss(xs:Array):Array {
    if(xs.length == 0) {
        return [[]];
    }
    return xs.map(
        function(x:*,index:uint,array:Array):* {
            var p:Array = permss( exclude(xs,x) );
            return p.map(
                function(y:*,_:uint,__:Array):* {
                    var ps:Array = y as Array;
                    ps.unshift(x);
                    return ps;
                }
            );
        }
    );
}
public static function exclude(xs:Array, elem:*):Array {
    return xs.filter(
        function(item:*,index:uint,array:Array):Boolean { return item != elem; }
    );
}







Follow

Get every new post delivered to your Inbox.

Join 185 other followers