List Comprehensions:
Filter:
Guides | Language | Collections

List Comprehensions

list comprehensions and generator expressions

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":

returns:

the list comprehension above is equivalent to the following code:

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

Qualifier Clauses

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

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

generator clause

The basic clause is the generator clause. Its syntax is

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.

multiple generators act like nested loops.

generators can depend on previous values.

guard clause

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

The guard acts as a filter on the results and constrains the search.

x.odd is the guard and causes all even numbers to be skipped.

you can have multiple guards.

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.

Unlike the generator clause, the name is bound to a single value, it doesn't iterate.

side effect clause

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

termination clause

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

using a guard

using a termination clause. this one stops searching, so does less work than the above.

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?

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 he should be searched first, then cooper, etc.

Grammar

Here is the BNF grammar for list comprehensions in SC.

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
guard
binding
side effect
termination