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.

10 comments:

BioGeek said...

In Python, the end point in the range function is never part of the generated list. So shouldn't in te solution to example 3 all the range(0,9)'s be replaced with range(0,10)?

Luis Diego Fallas said...

Thanks Biogeek, that's correct.

The Scala and Boo examples have the same problem.

Felix said...

The third Erlang example can be made a bit more elegant with
A <- lists:seq(0,9)

Paddy3118 said...

In Python, the return statement should be indented if it is on a separate line.
The ranges should all read range(10), as that is the idiomatic way to generate the integers zero to nine.

A bit of a niggle but I would usually combine both the if statements into one and use:

if (a != 0 ) and
((a*1000 + b*100 + c*10 + d)*4) ==
(d*1000 + c*100 + b*10 + a)]

A great article though, thanks.
- Paddy.

Paddy3118 said...

The Wikipedia entry on list comprehensions has been re-arranged. You might like to read the Talk page as well as the updated entry.

P.S. How did you create that mathematical set notation diagram with the set comprehension shown broken into its syntactical parts? I could use something like that for the Wikipedia entry.

- Paddy.

Paddy3118 said...

-

Luis Diego Fallas said...

Thanks!

The formula was created using the OpenOffice formula editor. In order to annotate a section of a formula the 'underbrace' keyword is used.

For example:

x underbrace variable = 1 underbrace value

Shows "x = 1" with the word "variable" below the 'x' and the word 'value' below the '1'.

Another example is available here.

Hope this helps.

Anonymous said...

For a Groovy solution see here: http://www.ist-dresden.de/blog/?p=11

Anonymous said...

Your filter x > 4 became x > 1 on the second line

Paddy3118 said...

Slightly different Python solution to the last task:

>>> from itertools import product
>>> [ (a,b,c,d)
for a,b,c,d in product(*[range(10)]*4)
if a != 0
if ((a*1000 + b*100 + c*10 + d)*4) ==
(d*1000 + c*100 + b*10 + a)]
[(2, 1, 7, 8)]
>>>