# List comprehensions

List comprehensions
You are encouraged to solve this task according to the task description, using any language you may know.

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:

1. They should be distinct from (nested) for loops within the syntax of the language.
2. They should return either a list or an iterator (something that returns successive members of a collection, in order).
3. 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(A,N),
C <- lists:seq(B,N),
A+B+C =< N,
A*A+B*B == C*C ].
```

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

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

pyth n = do

``` x <- [1..n]
y <- [x..n]
z <- [y..n]
guard \$ x^2 + y^2 == z^2
return (x,y,z)</lang>
```

## 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>
```

A Python generator comprehension (note the outer round brackets), returns an iterator over the same result rather than an explicit list:

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

## Ruby

A couple of ways, neither feel particularly elegant. Ruby's OO style really enforces writing left-to-right. <lang ruby># using a storage array a=[]; (1..n).each {|x| (1..n).each {|y| (1..n).each {|z| a << [x,y,z] if x**2 + y**2 == z**2}}}; a

1. no temp array, but a lot of housework to flatten and remove nils

(1..n).collect {|x| (1..n).collect {|y| (1..n).collect {|z| [x,y,z] if x**2 + y**2 == z**2}}}.reduce(:+).reduce(:+).compact</lang>

## Tcl

Tcl does not have list comprehensions built-in to the language, but they can be constructed. <lang tcl>package require Tcl 8.5

1. from http://wiki.tcl.tk/12574

proc lcomp {expression args} {

```   # Check the number of arguments.
if {[llength \$args] < 2} {
error "wrong # args: should be \"lcomp expression var1 list1\
?... varN listN? ?condition?\""
}
```
```   # Extract condition from \$args, or use default.
if {[llength \$args] % 2 == 1} {
set condition [lindex \$args end]
set args [lrange \$args 0 end-1]
} else {
set condition 1
}
```
```   # Collect all var/list pairs and store in reverse order.
set varlst [list]
foreach {var lst} \$args {
set varlst [concat [list \$var] [list \$lst] \$varlst]
}
```
```   # Actual command to be executed, repeatedly.
set script {lappend result [subst \$expression]}
```
```   # If necessary, make \$script conditional.
if {\$condition ne "1"} {
set script [list if \$condition \$script]
}
```
```   # Apply layers of foreach constructs around \$script.
foreach {var lst} \$varlst {
set script [list foreach \$var \$lst \$script]
}
```
```   # Do it!
set result [list]
{*}\$script ;# Change to "eval \$script" if using Tcl 8.4 or older.
return \$result
```

}

set range {1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20} puts [lcomp {\$x \$y \$z} x \$range y \$range z \$range {\$x < \$y && \$x**2 + \$y**2 == \$z**2}]</lang>

`{3 4 5} {5 12 13} {6 8 10} {8 15 17} {9 12 15} {12 16 20}`