Thursday, February 24, 2011

Scala vs Erlang vs Java permutations

Erlang permutations is ... terse:
perms([]) -> [[]];
perms(L) -> [[H|T] || H <- L, T <- perms(L--[H])].
I have entire post about this terse little gem, including the Java equivalent (rather less terse!); see Erlang: so awesome it makes my brain bleed.

It seemed rather reasonable to try this in Scala. It's a functional programming language with list comprehensions so surely it will be pretty terse! My first draft as a Scala newb:
def perms[T](L: List[T]):List[List[T]] = L match {
   //permutations of a single element is simply a list containing a list with that element
   case head :: Nil => List(List(head))
   case head :: tail => {          
    //not quite sure how to dodge use of the result var to accumulate results :(
    var result = List[List[T]]()
    for (head <- L; tail <- perms(L-head))  
     result = (head :: tail) :: result
    result
   }
    case Nil => List[List[T]]()
  }
Much nicer than the Java version but it doesn't hold a candle to Erlang for terse! It does however have the marked benefit of being vastly easier to read and comprehend ;) I wish I knew how to get rid of the result var :(

For reference, the Java equivalent (written to clearly express what is happening more than to be as lean as possible):
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
 
 
public class Perms {
 public static void main(String[] argv) {
  System.out.println(perms(Arrays.asList("A", "B", "C")));
 }
 
 public static List<List<String>> perms(List<String> input) {
  List<List<String>> output = new ArrayList<List<String>>();
  for (String H : input) {
   //L--[H]
   List<String> LminusH = new ArrayList<String>(input);
   LminusH.remove(H);   
   
   if (LminusH.isEmpty()) {
    //[H|T] when T is empty
    output.add(new ArrayList<String>(Arrays.asList(H)));
   } else {
    for (List<String> T : perms(LminusH)) {    
     //a list made up of [H|T]
     List<String> HT = new ArrayList<String>();
     HT.add(H);
     HT.addAll(T);
     output.add(HT);
    }
   }
  }
  return output;
 }
}

3 comments:

Unknown said...

I'm just learning Erlang and I've just written a concurrent version of perms which although longer and less elegant seems much faster. Try it with a 10 element list. I get the feeling it's linear (provided we have enough processes). Try:
perms:start([a,b,c,d,e,f,g,h,i,j]). with the following program:
-module(perms).
-export([perms/2,addAll/2,start/1,printAll/0,f/2]).


start(L) ->
Pid1=spawn(perms,printAll,[]),
perms(L,Pid1).

perms([],Pid) -> Pid![];
perms([H|T],Pid) ->
Pid1 = spawn(perms,f,[H,Pid]),
perms(T,Pid1).

f(H,Pid) -> receive
L -> g(H,L,Pid),
f(H,Pid)
end.

g(H,[],Pid) -> Pid![H];

g(X,[H|T],Pid) ->
Pid![X|[H|T]],
Pid1=spawn(perms,addAll,[H,Pid]),
g(X,T,Pid1).

addAll(H,Pid) ->
receive
L ->Pid![H|L],
addAll(H,Pid)
end.

printAll()->
receive
L -> io:format("~w.~n",[L]),
printAll()
end.

Anonymous said...

Scala can give you a version pretty close to Erlang's see : http://stackoverflow.com/questions/5056790/scala-permutation-of-factorials

Knurd said...

I strongly disagree with "vastly easier to read and comprehend" with respect to Scala.

The only key difference I notice the Scala and Erlang snippets is that Erlang employs fewer glyphs than Scala to express the same logic. I find this much easier to read and comprehend and, with respect to language constructs, I question anyone's reasoning why a verbose expression (and even a wall of text) is easier to comprehend than a terse one.

Maybe this is just how my brain works, but the more glyphs per atomic unit of information or reasoning, the harder I find it to read and comprehend what's going on.

Perhaps I should set Scala aside and learn Erlang, it looks to be incredibly succinct at what it does.

Post a Comment