comprehensions

A comprehension builds a set from generators and predicates. It is useful for concise construction, filtering, and relational joins over data. Mech several comprehension forms including matrix, set, and table comprehensions.

Syntax

A set comprehension has the form:

{yield-expression | clause-1, clause-2, ..., clause-n}

Matrix comprehensions have a similar form but use square brackets and yield a matrix instead of a set:

[yield-expression | clause-1, clause-2, ..., clause-n]

Common clause forms:

Generator: pattern <- source
Predicate: condition

Semantics

Generators introduce variables and iterate values from a source collection.
Predicates filter candidate bindings.
Later clauses can use variables introduced by earlier clauses.
Reused variables across generators naturally express join-like relationships.
The result is a set, so duplicates are removed.

Basic Examples

Squares

ex 3.1

A:={1, 2, 3, 4, 5}{x*x | x <- A}

Filtering Evens

ex 3.2

A:={1, 2, 3, 4, 5, 6, 7, 8, 9, 10}{x | x <- A, (x%2)⩵0}

Set Intersection Pattern

ex 3.3

A:={1, 2, 3, 4, 5, 6, 7, 8, 9, 10}B:={2, 3, 5, 7, 11, 13}{x | x <- A, x <- B}

Relational-Style Comprehensions

Free variables across generators express join-like relationships.

Friends of Friends

For example, to find "friends of friends" in a social graph represented as pairs of friends:

ex 4.1

pairs:={(1,2), (1,3), (2,8), (3,5), (3,9)}user:=1{fof | ( u, f ) <- pairs, ( f, fof ) <- pairs, u⩵user}

Pythagorean Triples

Here's a more complex example that finds all Pythagorean triples, which are sets of three positive integers (a, b, c) such that a^2 + b^2 = c^2, with each integer less than or equal to a specified limit n. The comprehension uses two generators to iterate over possible values of a, b, and c, and a predicate to filter for valid triples:

ex 4.2

n:=13{(a,b,c) | a <- 1..=n, b <- a..=n, c <- b..=n, (a*a+b*b)⩵(c*c)}