List Comprehensions

Introduction

List comprehensions are a syntactic feature of functional programming languages like Miranda, Haskell, and Erlang which were later copied into Python. You can search the web for "list comprehensions" or "generator expressions" to learn more. Basically list comprehensions are for getting a series of solutions to a problem.

in SC these are just a syntax macro for a longer expression. read this as "all [x,y] for x in 1..5, y in 1..x, such that x+y is prime":all {:[x,y], x <- (1..5), y <- (1..x), (x+y).isPrime }

all {:[x,y], x <- (1..5), y <- (1..x), (x+y).isPrime }

returns:[ [ 1, 1 ], [ 2, 1 ], [ 3, 2 ], [ 4, 1 ], [ 4, 3 ], [ 5, 2 ] ]

xxxxxxxxxx

[ [ 1, 1 ], [ 2, 1 ], [ 3, 2 ], [ 4, 1 ], [ 4, 3 ], [ 5, 2 ] ]

the list comprehension above is equivalent to the following code:all(Routine.new({ (1..5).do {|x| (1..x).do {|y| if ((x+y).isPrime) {[x,y].yield} }}}));

xxxxxxxxxx

all(Routine.new({ (1..5).do {|x| (1..x).do {|y| if ((x+y).isPrime) {[x,y].yield} }}}));

..but much more concise and much easier to keep in your head than writing it out.

In the list comprehension compiler, simple series like (1..5) and (1..x) are treated as special cases and implemented as loops rather than making a collection.

A list comprehension in SC is really a Routine. You can use the all message to collect all of the Routine's results into a list.

A few examples

all {: x/(x+1), x <- (1..5) }

​

[ 0.5, 0.66666666666667, 0.75, 0.8, 0.83333333333333 ]

all {:[x,y], x <- (1..3), y <- [\a,\b,\c] } [ [ 1, a ], [ 1, b ], [ 1, c ], [ 2, a ], [ 2, b ], [ 2, c ], [ 3, a ], [ 3, b ], [ 3, c ] ]

xxxxxxxxxx

all {:[x,y], x <- (1..3), y <- [\a,\b,\c] }

​

[ [ 1, a ], [ 1, b ], [ 1, c ], [ 2, a ], [ 2, b ], [ 2, c ], [ 3, a ], [ 3, b ], [ 3, c ] ]

all {:[x,y], x <- (0..3), y <- (x..0) } [ [ 0, 0 ], [ 1, 1 ], [ 1, 0 ], [ 2, 2 ], [ 2, 1 ], [ 2, 0 ], [ 3, 3 ], [ 3, 2 ], [ 3, 1 ], [ 3, 0 ] ]

xxxxxxxxxx

all {:[x,y], x <- (0..3), y <- (x..0) }

​

[ [ 0, 0 ], [ 1, 1 ], [ 1, 0 ], [ 2, 2 ], [ 2, 1 ], [ 2, 0 ], [ 3, 3 ], [ 3, 2 ], [ 3, 1 ], [ 3, 0 ] ]

all {:y, x <- (1..4), y <- (x..1) } [ 1, 2, 1, 3, 2, 1, 4, 3, 2, 1 ]

xxxxxxxxxx

all {:y, x <- (1..4), y <- (x..1) }

​

[ 1, 2, 1, 3, 2, 1, 4, 3, 2, 1 ]

xxxxxxxxxx

(

var intervals;

// a function to generate intervals between all pairs of notes in a chord voicing

intervals = {|chord|

    all {: chord[i+gap] - chord[i],

        gap <- (1 .. chord.lastIndex),

        i <- (0 .. chord.lastIndex - gap)

    }

};

​

intervals.([0,4,7,10]).postln;

intervals.([0,1,3,7]).postln;

)

​

[ 4, 3, 3, 7, 6, 10 ]

[ 1, 2, 4, 3, 6, 7 ]

xxxxxxxxxx

all {:[y, z], x<-(0..30), var y = x.nthPrime, var z = 2 ** y - 1, z.asInteger.isPrime.not  }

[ [ 11, 2047 ], [ 23, 8388607 ], [ 29, 536870911 ] ] // mersenne numbers which are no primes

Qualifier Clauses

A list comprehension begins with {: and contains a body followed by several qualifier clauses separated by commas.{: body , qualifiers }

xxxxxxxxxx

{: body , qualifiers }

There are several types of qualifier clauses that can appear after the body.

generator clause

The basic clause is the generator clause. Its syntax isname <- expr

xxxxxxxxxx

name <- expr

The expression should be something that can respond meaningfully to 'do' such as a collection or a stream. The name takes on each value of the expression. The name is a local variable whose scope extends to all clauses to the right. The name is also in scope in the body.all {: x, x <- (1..3) } [ 1, 2, 3 ]

xxxxxxxxxx

all {: x, x <- (1..3) }

​

[ 1, 2, 3 ]

all {: x, x <- [\a, \b, \c] } [ a, b, c ]

xxxxxxxxxx

all {: x, x <- [\a, \b, \c] }

​

[ a, b, c ]

all {: x, x <- (1!3)++(2!2)++3 } [ 1, 1, 1, 2, 2, 3 ]

xxxxxxxxxx

all {: x, x <- (1!3)++(2!2)++3 }

​

[ 1, 1, 1, 2, 2, 3 ]

multiple generators act like nested loops.all {: [x,y], x <- (1..2), y <- (10,20..30) } [ [ 1, 10 ], [ 1, 20 ], [ 1, 30 ], [ 2, 10 ], [ 2, 20 ], [ 2, 30 ] ]

xxxxxxxxxx

all {: [x,y], x <- (1..2), y <- (10,20..30) }

​

[ [ 1, 10 ], [ 1, 20 ], [ 1, 30 ], [ 2, 10 ], [ 2, 20 ], [ 2, 30 ] ]

generators can depend on previous values.all {: x, x <- (1..3), y <- (1..x) } [ 1, 2, 2, 3, 3, 3 ]

xxxxxxxxxx

all {: x, x <- (1..3), y <- (1..x) }

​

[ 1, 2, 2, 3, 3, 3 ]

all {: x, x <- (1..3), y <- (1..4-x) } [ 1, 1, 1, 2, 2, 3 ]

xxxxxxxxxx

all {: x, x <- (1..3), y <- (1..4-x) }

​

[ 1, 1, 1, 2, 2, 3 ]

guard clause

A guard clause is simply an expression. It should return a boolean value.expr

xxxxxxxxxx

expr

The guard acts as a filter on the results and constrains the search.all {: x, x <- (0..10), x.odd } [ 1, 3, 5, 7, 9 ]

xxxxxxxxxx

all {: x, x <- (0..10), x.odd }

​

[ 1, 3, 5, 7, 9 ]

x.odd is the guard and causes all even numbers to be skipped.all {: x, x <- (0..30), (x % 5 == 0) || x.isPowerOfTwo } [ 0, 1, 2, 4, 5, 8, 10, 15, 16, 20, 25, 30 ]

xxxxxxxxxx

all {: x, x <- (0..30), (x % 5 == 0) || x.isPowerOfTwo }

​

[ 0, 1, 2, 4, 5, 8, 10, 15, 16, 20, 25, 30 ]

you can have multiple guards.all {: [x,y], x <- (0..10), (x % 5 == 0) || x.isPowerOfTwo, y <- (1..2), (x+y).even } [ [ 0, 2 ], [ 1, 1 ], [ 2, 2 ], [ 4, 2 ], [ 5, 1 ], [ 8, 2 ], [ 10, 2 ] ]

xxxxxxxxxx

all {: [x,y], x <- (0..10), (x % 5 == 0) || x.isPowerOfTwo, y <- (1..2), (x+y).even }

​

[ [ 0, 2 ], [ 1, 1 ], [ 2, 2 ], [ 4, 2 ], [ 5, 1 ], [ 8, 2 ], [ 10, 2 ] ]

var clause

A var clause lets you create a new variable binding that you can use in your expressions. The scope of the name extends to all clauses to the right and in the body.var name = expr

xxxxxxxxxx

var name = expr

Unlike the generator clause, the name is bound to a single value, it doesn't iterate.all {: z, x <- (1..20), var z = (x*x-x) div: 2, z.odd } [ 1, 3, 15, 21, 45, 55, 91, 105, 153, 171 ]

xxxxxxxxxx

all {: z, x <- (1..20), var z = (x*x-x) div: 2, z.odd }

​

[ 1, 3, 15, 21, 45, 55, 91, 105, 153, 171 ]

side effect clause

This clause lets you insert code to do some side effect like printing.\:: expr

xxxxxxxxxx

\:: expr

all {: z, x <- (1..20), var z = (x*x-x) div: 2, :: [x,z].postln, z.even }

xxxxxxxxxx

all {: z, x <- (1..20), var z = (x*x-x) div: 2, :: [x,z].postln, z.even }

termination clause

The termination clause is for stopping further searching for results. Once the expression becomes false, the routine halts.:while expr

xxxxxxxxxx

:while expr

using a guardall {: z, x <- (1..20), var z = (x*x-x) div: 2, :: [x,z].postln, z < 50 }

xxxxxxxxxx

all {: z, x <- (1..20), var z = (x*x-x) div: 2,  :: [x,z].postln, z < 50 }

using a termination clause. this one stops searching, so does less work than the above.all {: z, x <- (1..20), var z = (x*x-x) div: 2, :: [x,z].postln, :while z < 50 }

xxxxxxxxxx

all {: z, x <- (1..20), var z = (x*x-x) div: 2,  :: [x,z].postln, :while z < 50 }

Constrained Search

list comprehensions can solve constrained combinatorial problems like this one:

Baker, Cooper, Fletcher, Miller, and Smith live on different floors of an apartment house that contains only five floors. Baker does not live on the top floor. Cooper does not live on the bottom floor. Fletcher does not live on either the top or the bottom floor. Miller lives on a higher floor than does Cooper. Smith does not live on a floor adjacent to Fletcher's. Fletcher does not live on a floor adjacent to Cooper's. Where does everyone live?( z = {: [baker, cooper, fletcher, miller, smith] , var floors = (1..5), baker <- floors, baker != 5, // Baker does not live on the top floor. // remove baker's floor from the list. // var creates a new scope, so the 'floors' on the left is a new binding. var floors = floors.removing(baker), cooper <- floors, cooper != 1, // Cooper does not live on the bottom floor. var floors = floors.removing(cooper), // remove cooper's floor from the list. fletcher <- floors, (fletcher != 5) && (fletcher != 1) // Fletcher does not live on either top or bottom floor. && (absdif(fletcher, cooper) > 1), // Fletcher does not live on a floor adjacent to Cooper's. var floors = floors.removing(fletcher), // remove fletcher's floor miller <- floors, miller > cooper, // Miller lives on a higher floor than does Cooper. var floors = floors.removing(miller), // remove miller's floor smith <- floors, absdif(fletcher, smith) > 1 // Smith does not live on a floor adjacent to Fletcher's. }; ) z.next; // [3, 2, 4, 5, 1 ] z.next; // nil. only one solution

xxxxxxxxxx

(

z = {: [baker, cooper, fletcher, miller, smith] ,

    var floors = (1..5),

    baker <- floors,  baker != 5,  // Baker does not live on the top floor.

    // remove baker's floor from the list.

    // var creates a new scope, so the 'floors' on the left is a new binding.

    var floors = floors.removing(baker),

    cooper <- floors, cooper != 1, // Cooper does not live on the bottom floor.

    var floors = floors.removing(cooper), // remove cooper's floor from the list.

    fletcher <- floors, (fletcher != 5) && (fletcher != 1) // Fletcher does not live on either top or bottom floor.

        && (absdif(fletcher, cooper) > 1), // Fletcher does not live on a floor adjacent to Cooper's.

    var floors = floors.removing(fletcher), // remove fletcher's floor

    miller <- floors, miller > cooper, // Miller lives on a higher floor than does Cooper.

    var floors = floors.removing(miller), // remove miller's floor

    smith <- floors, absdif(fletcher, smith) > 1  // Smith does not live on a floor adjacent to Fletcher's.

};

)

​

z.next; // [3, 2, 4, 5, 1 ]

z.next; // nil.  only one solution

combinatorial problems can take a lot of time to run. you can reorder the above tests to make it run faster. generally you want to search the most constrained variables first. the most constrained person above is fletcher, so they should be searched first, then cooper, etc.

Grammar

Here is the BNF grammar for list comprehensions in SC.[ ] - optional { } - zero or more <list_compre> ::= "{:" <body> ',' <qualifiers> "}" <body> ::= <exprseq> <exprseq> ::= <expr> { ";" <expr> } <qualifiers> ::= <qualifier> { ',' <qualifiers> } <qualifier> ::= <generator> | <guard> | <binding> | <side_effect> | <termination> <generator> ::= <name> "<-" <exprseq> <guard> ::= <exprseq> <binding> ::= "var" <name> "=" <exprseq> <side_effect> ::= "::" <exprseq> <termination> ::= ":while" <exprseq>

xxxxxxxxxx

[ ] - optional

{ } - zero or more

​

<list_compre> ::= "{:" <body> ',' <qualifiers> "}"

​

<body> ::= <exprseq>

​

<exprseq> ::= <expr> { ";" <expr> }

​

<qualifiers> ::= <qualifier> { ',' <qualifiers> }

​

<qualifier> ::= <generator> | <guard> | <binding> | <side_effect> | <termination>

​

<generator> ::= <name> "<-" <exprseq>

​

<guard> ::= <exprseq>

​

<binding> ::= "var" <name> "=" <exprseq>

​

<side_effect> ::= "::" <exprseq>

​

<termination> ::= ":while" <exprseq>

Code Generation

For each of the above clauses, here is how the code is generated. The body acts as the innermost qualifier. By understanding these translations, you can better understand how scoping and control flow work in list comprehensions.

generator

expr.do {|name| ..next qualifier.. }

xxxxxxxxxx

 

expr.do {|name| ..next qualifier.. }

guard

if (expr) { ..next qualifier.. }

xxxxxxxxxx

 

if (expr) { ..next qualifier.. }

binding

{|name| ..next qualifier.. }.value(expr)

xxxxxxxxxx

 

{|name| ..next qualifier.. }.value(expr)

side effect

expr ; ..next qualifier..

xxxxxxxxxx

 

expr ; ..next qualifier..

termination

if (expr) { ..next qualifier.. }{ nil.alwaysYield }

xxxxxxxxxx

 

if (expr) { ..next qualifier.. }{ nil.alwaysYield }