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
    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) {
   List<String> LminusH = new ArrayList<String>(input);
   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>();
  return output;


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:

start(L) ->

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

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

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

g(X,[H|T],Pid) ->

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

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

Anonymous said...

Scala can give you a version pretty close to Erlang's see :

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