List Comprehension

Posted By: Jingyi

I have decided to take a look at Erlang to see if we can use it in our products to create scalable, fault-tolerant software.  I am reading the book “Programming Erlang: Software for a Concurrent World”.  Here is an example in the book that uses list comprehension to find all the permutation for a list.

-module(perm).
-export([perm/1]).

perm([]) -> [[]];
perm(L) -> [[H | T] || H <- L, T <- perm(L -- [H])].

If you have Erlang installed, you can start the shell and run the following test:

c(perm).               %% compile the module perm
A = [1, 2, 3].
perm:perm(A).     %% will find all the permutation [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

Now let’s look at the code. Only two lines of code to find all the permutation of a list. The code is so concise and readable. The list comprehension is a very powerful syntax construct to manipulate lists. But it is just a multiple for-loop that has been written in a different way.  If we translate that function to a more familiar format, it would be like…

for each elem in a list
    find all the permutation of a list that doesn't contain elem
    for each permutation that has been found
         add elem in front of the permutation

Now we see the expressive power of functional language. Since python has list comprehension too, I decided to make a python version of permutation. Here is the python code that i came up with.

def perm(l):
   def remove(l, x):
       l.remove(x)
       return l

   if l == []:
       return [[]]
   else:
       return [[x] + y for x in l for y in perm(remove(l[:], x))]
# testing program
if __name__ == "__main__":
   a = [1, 2, 3]
   b = perm(a)
   print(b)       ## will print   [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

I couldn’t find a way to remove an element from a list and return the new list in python (I wish python could offer something like ruby does, [1, 2, 3] - [1] => [2, 3] ). So, I have to write a nested helper method called remove to do that so that I can use it in the list comprehension. If we ignore the helper method, the code is about the same size as in Erlang. However, python’s code is not as readable as Erlang code because it doesn’t support the lisp cons-like operator. But it is not very bad.

After I wrote the python program, I decided to write a C# version of permutation. Here is the code…

public class Permut {
                public static List<List<T>> perm<T>(IEnumerable<T> l) where T : IEquatable<T> { // this where constraint may not be necessary.
                        switch (l.Count()) {
                                case 0: return new List<List<T>> { new List<T>() };
                                case 1: return new List<List<T>> { new List<T> { l.ElementAt(0) } };
                                default:
                                        List<List<T>> ret = new List<List<T>>();
                                        foreach (T elem in l) {
                                                var n = perm(l.Where(e => !e.Equals(elem)));
                                                n.ForEach(e => e.Insert(0, elem));
                                                ret.AddRange(n);
                                        }
                                        return ret;
                        }
                }
        }
    // testing program
int[] arr = {1, 2, 3};
     var ret = Permut.perm(arr);  // ret will be [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

Apparently, C# code is a lot longer and harder to understand. I may be able to simplify a little bit the above code, but not too much. I have to use generic to accomplish the duck typing effect, which introduce a lot of complexity.

In summary, list comprehension is a very powerful, interesting syntax construct. A lot of languages such as F#, Haskell, Scala have this feature. For a static language developer, I think it would be an unfamiliar interesting feature.

Jingyi Wang is a developer for Fellowship Technologies. He has been with Fellowship Tech since August of 2005. He is passionate about improving himself and is always striving to write better code than the day before.

Posted In: Tips,

Comments:
No one has commented yet. Be the first!
Commenting is not available in this channel entry.

Categories:

Previous Posts:


Subscribe to the RSS feed!