List comprehensions

A list comprehension is a special syntax in some programming languages to describe lists. It is similar to the way mathematicians describe sets, with a set comprehension, hence the name.

Some attributes of a list comprehension are that:

They should be distinct from (nested) for loops within the syntax of the language.
They should return either a list or an iterator (something that returns successive members of a collection, in order).
The syntax has parts corresponding to that of set-builder notation.

Write a list comprehension that builds the list of all Pythagorean triples with elements between 1 and n. If the language has multiple ways for expressing such a construct (for example, direct list comprehensions and generators), write one example for each.

ALGOL 68

ALGOL 68 does not have list comprehension, however it is sometimes reasonably generous about where a flex array is declared. And with the addition of an append operator "+:=" for lists they can be similarly manipulated.

Translation of: Python

Works with: ALGOL 68 version Standard - no extensions to language used

Works with: ALGOL 68G version Any - tested with release mk15-0.8b.fc9.i386

Works with: ELLA ALGOL 68 version Any (with appropriate job cards) - tested with release 1.8.8d.fc9.i386

<lang algol>MODE XYZ = STRUCT(INT x,y,z);

OP +:= = (REF FLEX[]XYZ lhs, XYZ rhs)FLEX[]XYZ: (

 [UPB lhs+1]XYZ out;
 out[:UPB lhs] := lhs;
 out[UPB out] := rhs;
 lhs := out

);

INT n = 20; print (([]XYZ(

 FLEX[0]XYZ xyz;
 FOR x TO n DO FOR y FROM x+1 TO n DO FOR z FROM y+1 TO n DO IF x*x + y*y = z*z THEN xyz +:= XYZ(x,y,z) FI OD OD OD;
 xyz), new line

))</lang> Output:

         +3         +4         +5         +5        +12        +13         +6         +8        +10         +8        +15        +17         +9        +12        +15        +12        +16        +20

Clojure

 (for [x (range 1 21) y (range x 21) z (range y 21) :when (= (+ (* x x) (* y y)) (* z z))] [x y z])

Common Lisp

Common Lisp doesn't have list comprehensions built in, but we can implement them easily with the help of the iterate package.

<lang lisp>(defun nest (l)

 (if (cdr l)
   `(,@(car l) ,(nest (cdr l)))
   (car l)))

(defun desugar-listc-form (form)

 (if (string= (car form) 'for)
   `(iter ,form)
   form))

(defmacro listc (expr &body (form . forms) &aux (outer (gensym)))

 (nest
   `((iter ,outer ,form)
     ,@(mapcar #'desugar-listc-form forms)
     (in ,outer (collect ,expr)))))</lang>

We can then define a function to compute Pythagorean triples as follows:

<lang lisp>(defun pythagorean-triples (n)

 (listc (list x y z)
   (for x from 1 to n)
   (for y from x to n)
   (for z from y to n)
   (when (= (+ (expt x 2) (expt y 2)) (expt z 2)))))</lang>

E

pragma.enable("accumulator") # considered experimental

accum [] for x in 1..n { for y in x..n { for z in y..n { if (x**2 + y**2 <=> z**2) { _.with([x,y,z]) } } } }

Erlang

 pythag(N) ->
     [ {A,B,C} ||
         A <- lists:seq(1,N),
         B <- lists:seq(1,N),
         C <- lists:seq(1,N),
         A+B+C =< N,
         A*A+B*B == C*C
     ].

Haskell

pyth n = [(x,y,z) | x <- [1..n], y <- [x..n], z <- [y..n], x^2 + y^2 == z^2]

Since lists are Monads, one can alternatively also use the do-notation (which is practical if the comprehension is large):

 import Control.Monad

 pyth n = do
   x <- [1..n]
   y <- [x..n]
   z <- [y..n]
   guard $ x^2 + y^2 == z^2
   return (x,y,z)

Mathematica

Select[Tuples[Range[n], 3], #1[[1]]^2 + #1[[2]]^2 == #1[[3]]^2 &]

Python

List comprehension:

<lang python>[(x,y,z) for x in xrange(1,n+1) for y in xrange(x,n+1) for z in xrange(y,n+1) if x**2 + y**2 == z**2]</lang>

Generator comprehension (note the outer round brackets):

<lang python>((x,y,z) for x in xrange(1,n+1) for y in xrange(x,n+1) for z in xrange(y,n+1) if x**2 + y**2 == z**2)</lang>

Generator function:

<lang python>def gentriples(n):
  for x in xrange(1,n+1):
    for y in xrange(x,n+1):
      for z in xrange(y,n+1):
        if x**2 + y**2 == z**2:
          yield (x,y,z)</lang>