List comprehensions: Difference between revisions
(added javascript) |
m (tested in spidermonkey 1.8) |
||
Line 38: | Line 38: | ||
))</lang> |
))</lang> |
||
Output: |
Output: |
||
<div style="width:full;overflow:scroll"><pre> |
|||
⚫ | |||
+3 +4 +5 +5 +12 +13 +6 +8 +10 +8 +15 +17 +9 +12 +15 +12 +16 +20 |
+3 +4 +5 +5 +12 +13 +6 +8 +10 +8 +15 +17 +9 +12 +15 +12 +16 +20 |
||
</pre> |
</pre></div> |
||
=={{header|Clojure}}== |
=={{header|Clojure}}== |
||
Line 112: | Line 112: | ||
=={{header|JavaScript}}== |
=={{header|JavaScript}}== |
||
{{works with|JavaScript|1.7+ (Firefox 2+)}} |
{{works with|JavaScript|1.7+ (Firefox 2+)}} {{works with|SpiderMonkey|1.7}} |
||
See [https://developer.mozilla.org/en/New_in_JavaScript_1.7#Array_comprehensions here] for more details |
See [https://developer.mozilla.org/en/New_in_JavaScript_1.7#Array_comprehensions here] for more details |
||
⚫ | |||
(not tested yet) |
|||
⚫ | |||
function range(begin, end) { |
|||
for (let i = begin; i < end; ++i) { |
for (let i = begin; i < end; ++i) { |
||
yield i; |
yield i; |
||
Line 124: | Line 122: | ||
function triples(n) { |
function triples(n) { |
||
return [[x,y,z] for each (x in range( |
return [[x,y,z] for each (x in range(1,n+1)) for each (y in range(x,n+1)) for each (z in range(y,n+1)) if (x*x + y*y == z*z)] |
||
} |
} |
||
</script></lang> |
|||
for each (var triple in triples(20)) |
|||
print(triple);</script></lang></div> |
|||
outputs: |
|||
⚫ | |||
5,12,13 |
|||
6,8,10 |
|||
8,15,17 |
|||
9,12,15 |
|||
12,16,20</pre> |
|||
=={{header|Mathematica}}== |
=={{header|Mathematica}}== |
||
Line 176: | Line 183: | ||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
A couple of ways, neither feel particularly elegant. Ruby's OO style really enforces writing left-to-right. |
A couple of ways, neither feel particularly elegant. Ruby's OO style really enforces writing left-to-right. |
||
<lang ruby># using a storage array |
<div style="width:full;overflow:scroll"><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 |
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 |
||
# no temp array, but a lot of housework to flatten and remove nils |
# 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> |
(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></div> |
||
=={{header|Tcl}}== |
=={{header|Tcl}}== |
Revision as of 11:26, 8 October 2009
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:
- 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.
<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 ].
Haskell
<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):
<lang haskell>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)</lang>
J
<lang J>(#~ (2&{ = 1&{ +&.:*: 0&{)@|:)@(1+3&# #: i.@^&3)</lang>
The idiom here has two major elements:
First, you need a statement indicating the values of interest. In this case, (1+3&# #: i.@^&3) which when used as a function of n specifies a list of triples each in the range 1..n.
Second, you need a statement of the form (#~ B) where B returns true for the desired members, and false for the undesired members.
JavaScript
See here for more details
for (let i = begin; i < end; ++i) { yield i; }
}
function triples(n) {
return [[x,y,z] for each (x in range(1,n+1)) for each (y in range(x,n+1)) for each (z in range(y,n+1)) if (x*x + y*y == z*z)]
}
for each (var triple in triples(20))
print(triple);</script></lang>outputs:
3,4,5 5,12,13 6,8,10 8,15,17 9,12,15 12,16,20
Mathematica
Select[Tuples[Range[n], 3], #1[[1]]^2 + #1[[2]]^2 == #1[[3]]^2 &]
OCaml
OCaml Batteries Included has uniform comprehension syntax for lists, arrays, enumerations (like streams), lazy lists (like lists but evaluated on-demand), sets, hashtables, etc.
Comprehension are of the form
[? expression | x <- enumeration ; condition; condition ; ...]
For instance, <lang ocaml># [? 2 * x | x <- 0 -- max_int ; x * x > 3];; - : int Enum.t = <abstr></lang> or, to compute a list, <lang ocaml># [? List: 2 * x | x <- 0 -- 100 ; x * x > 3];; - : int list = [2; 4; 6; 8; 10]</lang> or, to compute a set, <lang ocaml># [? PSet: 2 * x | x <- 0 -- 100 ; x * x > 3];; - : int PSet.t = <abstr></lang>
etc..
Perl
Perl 5 does not have built-in list comprehension syntax. The closest approach are the list map
and grep
(elsewhere often known as filter) operators:
<lang perl>sub triples ($) {
my ($n) = @_; map { my $x = $_; map { my $y = $_; map { [$x, $y, $_] } grep { $x**2 + $y**2 == $_**2 } 1..$n } 1..$n } 1..$n;
}</lang>
map
binds $_
to each element of the input list and collects the results from the block. grep
returns every element of the input list for which the block returns true. The ..
operator generates a list of numbers in a specific range.
<lang perl>for my $t (triples(10)) {
print "@$t\n";
}</lang>
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.
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
- no temp array, but a lot of housework to flatten and remove nils
Tcl
Tcl does not have list comprehensions built-in to the language, but they can be constructed. <lang tcl>package require Tcl 8.5
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}
TI-89 BASIC
TI-89 BASIC does not have a true list comprehension, but it has the seq() operator which can be used for some similar purposes.
{1, 2, 3, 4} → a seq(a[i]^2, i, 1, dim(a))
produces {1, 4, 9, 16}. When the input is simply a numeric range, an input list is not needed; this produces the same result:
seq(x^2, x, 1, 4)