Sunday, February 18, 2007

List comprehensions across languages

According to Wikipedia a list comprehension is a language construct that lets you specify the contents of a list based on the set builder notation which used in mathematics to describe the members of a set.

For example in order to describe "the set of all natural numbers greater than 4 and lower than 10" using this notation we say:



A list comprehension expression is composed of the following elements:



Where:
  • set member describes each element of the set. .
  • generator generate values to be included in the set. More than one generator can be used. In the case, all possible combinations are tested.
  • filter expressions filter generated values.
In this post I'm going to show examples written in several languages that have a construct similar to list comprehensions. Three examples are used:

1. Get all even numbers from a list

A simple example that filters the contents of a list of integers to get all the even numbers.

2. Get all the files that are greater than some given size

An example to show how list comprehensions can be used to work on elements other than numbers.

3. Solve the 4(ABCD) = DCBA puzzle

An example to show the use of several generators. This puzzle consists in finding the values of digits A,B,C,D given that ABCD*4 = DCBA where ABCD and DCBA are 4-digit numbers.


And now the code...


Haskell

The syntax of list comprehensions in Haskell can be considered syntactic sugar for the List Monad.

Syntax is described here.

Example 1:


getEvenNumbers aList =
[ x | x >- aList, x `mod` 2 = 0]


Example 2:


import Directory
import Monad
import IO

...

getFilesGreaterThan size directory =
do
contents <- getDirectoryContents directory
files <- filterM doesFileExist $ map ((++) directory) contents
filesWithSize <- mapM fsize files
return [fname | (fname,fsize) <- filesWithSize, fsize >= size]
where
fsize f =
do {fd <- openFile f ReadMode;
size <- hFileSize fd;
hClose fd;
return (f,size)}



Example 3:


solveABCDProblem =
[ (a,b,c,d) |
a <-[0..9],
b <-[0..9],
c <-[0..9],
d <-[0..9],
a /= 0,
(1000*a + 100*b + 10*c + d)*4 ==
(1000*d + 100*c + 10*b + a)]


F#

F# sequence comprehensions syntax is described here . One nice feature of F# sequence comprehensions is that not only lists can be used in generators, but any object implementing IEnumerable . Also the result of a sequence comprehension an IEnumerable.

Example 1:


let GetEvenNumbers (l) =
{ for i in l
when i % 2 = 0 -> i }


Example 2:


let GetFilesGreaterThan( size ,directory) =
let dInfo = (new System.IO.DirectoryInfo(directory))
in { for f in dInfo.GetFiles()
when (f.Length >= size) -> f }


Example 3:


let SolveProblem() =
{ for a in 0 .. 9
for b in 0 .. 9
for c in 0 .. 9
for d in 0 .. 9
when (1000*a + 100*b + 10*c + d)*4 =
(1000*d + 100*c + 10*b + a) -> (a,b,c,d) }



Scala

Scala has the concept of sequence comprehensions which works with several kinds of collections.

Example 1:

def getEvenNumbers(l : List[int]) =
for { val i <- l
i % 2 == 0 }
yield i

Example 2:

def getFilesGreaterThan(size : int, folder : String) = {
val folderD = new java.io.File(folder)
for{ val f <- folderD.listFiles()
f.isFile()
f.length() >= size
} yield f.getName()
}

Example 3:

def solveProblem() =
for {
val a <- List.range(0,9)
val b <- List.range(0,9)
val c <- List.range(0,9)
val d <- List.range(0,9)
a != 0
(a*1000 + b*100 + c*10 + d)*4 == (d*1000 + c*100 + b*10 + a)
} yield List(a,b,c,d)



Erlang

Erlang's list comprehensions are described here .


Example 1:

get_even_numbers(L) -> [X || X <- L, (X rem 2) == 0].

Example 2:

get_files_greater_than(Size,Directory) ->
[Fn || Fn <- filelib:wildcard(lists:append(Directory,"*")),
not filelib:is_dir(Fn),
filelib:file_size(Fn) > Size].

Example 3:

solve_problem() ->
[{A,B,C,D} ||
A <- [0,1,2,3,4,5,6,7,8,9],
B <- [0,1,2,3,4,5,6,7,8,9],
C <- [0,1,2,3,4,5,6,7,8,9],
D <- [0,1,2,3,4,5,6,7,8,9],
A /= 0,
(1000*A + 100*B + 10*C + D)*4 == (1000*D + 100*C + 10*B + A) ].




Python

Python list comprehension syntax is described here.

Example 1:

def getEvenNumbers(l):
return [x for x in l if x % 2 == 0]

Example 2:

def listFilesGreaterThan(size,directory):
return [fileName
for fileName in os.listdir(directory)
if os.path.isfile(os.path.join(directory,fileName))
if os.path.getsize(os.path.join(directory,fileName)) > size]

Example 3:

def solveProblem():
return [ (a,b,c,d)
for a in range(0,9)
for b in range(0,9)
for c in range(0,9)
for d in range(0,9)
if a != 0
if ((a*1000 + b*100 + c*10 + d)*4) ==
(d*1000 + c*100 + b*10 + a)]



Nemerle

Nemerle list comprehensions are described here.

Example 1:

public GetEvenNumbers(l : list[int]) : list[int] {
$[x | x in l, x % 2 == 0]
}

Example 2:

public GetFilesGreaterThan(size : int, directory: string) : list[string] {
def dInfo = DirectoryInfo(directory);
$[f.Name | f in dInfo.GetFiles(), f.Length >= size]
}

Example 3:

public SolveProblem() : list[int*int*int*int]{
$[(a,b,c,d) |
a in [0..9],
b in [0..9],
c in [0..9],
d in [0..9],
a != 0,
(1000*a + 100*b + 10*c + d)*4 == (1000*d + 100*c + 10*b + a) ]
}



Boo

Because of its influence in the language, list generators in Boo are very similar to list comprehensions in Python.

Example 1:

def getEvenNumbers(l):
return [x for x as int in l if x % 2 == 0]

Example 2:

def getFilesGreaterThan(size as int,directory as string):
dInfo = DirectoryInfo(directory)
return [f.Name for f in dInfo.GetFiles() if f.Length > size]

Example 3:

def solveProblem():
return [(a,b,c,d)
for a in range(0,9)
for b in range(0,9)
for c in range(0,9)
for d in range(0,9)
if a != 0 and ((1000*a + 100*b + 10*c + d)*4) == (1000*d + 100*c + 10*b + a)]


Visual Basic 9 (LINQ)

The LINQ feature of VB 9 allows the creation of expressions similar to list comprehesions. A nice feature of LINQ is that it operates with any object that implements IEnumerable<T> and also returns an IEnumerable<T> .

Example 1:

Public Shared Function GetEvenNumbers(ByVal l as List(Of Integer)) as List(Of Integer)
Return New List(Of Integer) ( _
From x in l _
Where (x Mod 2) = 0 _
Select x )
End Function

Example 2:

Public Shared Function GetFilesGreaterThan(ByVal size As Integer,directory As String) As List(Of FileInfo)
Dim dirInfo = new DirectoryInfo(directory)

return new List(Of FileInfo) (From f in dirInfo.GetFiles() _
Where f.Length >= size _
Select f)
End Function:


Example 3:

Public Shared Sub SolveProblem()
Dim results = _
From a in Range(0,9), _
b in Range(0,9), _
c in Range(0,9), _
d in Range(0,9) _
Where (1000*a + 100*b + 10*c + d)*4 = _
(1000*d + 100*c + 10*b + a) AndAlso _
a <> 0 _
Select New { A := a,B := b,C := c,D := d }
For Each result in results
Console.WriteLine("A={0} B={1} C={2} D={3}",result.A,result.B,result.C,result.D)
Next

End Sub


Public Shared Function Range(i as Integer,n as Integer) as List(Of Integer)
Dim result as new List(Of Integer)()
For i = i To n
result.Add(i)
Next
Return result
End Function


C# 3.0 (LINQ)

As with VB, the LINQ feature of C# 3.0 allows the creation of expressions similar to list comprehesions.

Example 1:

static List<int> GetEvenNumbers(List<int> l)
{
return new List<int>( from x in l
where x % 2 == 0
select x);
}

Example 2:

static List<FileInfo> GetFilesGreaterThan(int size,string directory)
{
DirectoryInfo dirInfo = new DirectoryInfo(directory);

return new List (
from f in dirInfo.GetFiles()
where f.Length >= size
select f
);
}



Example 3:

static void SolveProblem()
{
var results =
from a in range(0,9)
from b in range(0,9)
from c in range(0,9)
from d in range(0,9)
where (1000*a + 100*b + 10*c + d)*4 ==
(1000*d + 100*c + 10*b + a) &&
a != 0
select new {
A=a,B=b,C=c,D=d
};


foreach(var result in results) {
Console.WriteLine("A={0} B={1} C={2} D={3}",
result.A,result.B,result.C,result.D);
}
}

static IEnumerable<int> range(int s,int n)
{
for(int i = s ;i <= n;i++) {
yield return i;
}
}




Powershell

Although not explicitly having a list comprehension feature, it's interesting to use Powershell pipeline to get a similar funcionality.

Example 1:

Function GetEvenNumbers($l) {
$l | ? {$_ % 2 -eq 0}
}

Example 2:

function GetFilesGreaterThan($size, $folder) {
get-childitem $folder | ? { $_.Length -gt $size}
}

Example 3:

Function SolveProblem() {
(0..9) | % { $a=$_ ;(0..9) |
% {$b = $_ ; (0..9) |
% {$c = $_ ; (0..9) |
% {$d = $_ ; @{a=$a;b=$b;c=$c;d=$d}} } } } |
? { ((1000*$_.a + 100*$_.b + 10*$_.c + $_.d )*4) -eq
(1000*$_.d + 100*$_.c + 10*$_.b + $_.a )} |
% { write-host $_.a $_.b $_.c $_.d}
}


Others

Some other languages with list comprehensions where not covered by this post. Among this languages is Fortress(waiting for reference implementation to support this) and Perl 6 . Future posts will cover this languages.