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;
 }
}

4 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.

Digital said...

Great comparison of permutation generation across Scala, Erlang, and Java! It’s fascinating to see how each language handles the problem with its own strengths, from Scala’s concise syntax to Erlang’s functional approach and Java’s imperative style. Your examples highlight how language paradigms can influence code complexity and performance. It would be interesting to explore the memory usage and execution speed for each approach with larger datasets. Thanks for this insightful breakdown—it’s a valuable resource for anyone comparing these languages!

Digital Marketing Course In Hyderabad

Post a Comment