List comprehensions: Difference between revisions

From Rosetta Code
Content added Content deleted
(Added Wrapl code)
(Pari/GP)
Line 473: Line 473:
{Application.exit 0}
{Application.exit 0}
end</lang>
end</lang>

=={{header|PARI/GP}}==
<lang>vector(100,x,x^3+sin(x))</lang>


=={{header|Perl}}==
=={{header|Perl}}==

Revision as of 19:51, 31 October 2010

Task
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 algol68>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

AutoHotkey

Works with: AutoHotkey_L

List Comprehension is not built in. <lang AutoHotkey> comprehend("show", range(1, 20), "triples") return

comprehend(doToVariable, inSet, satisfying) {

 set := %satisfying%(inSet.begin, inSet.end)
 index := 1
 While % set[index, 1]
 {
   item := set[index, 1] . ", " . set[index, 2] . ", " . set[index, 3]
   %doToVariable%(item)
   index += 1
 }
 return

}


show(var) {

 msgbox % var

}

range(begin, end)

{
  set := object()
  set.begin := begin
  set.end := end
  return set
}

!r::reload !q::exitapp

triples(begin, end) {

 set := object()
 index := 1
 range := end - begin
 
 loop, % range
 {
   x := begin + A_Index 
   loop, % range
   {
     y := A_Index + x 
     if y > 20

break loop, % range {

 z := A_Index + y 
 if z > 20
   break
 isTriple := ((x ** 2 + y ** 2) == z ** 2)
 if isTriple
 {
   set[index, 1] := x 
   set[index, 2] := y
   set[index, 3] := z
   index += 1
 ; msgbox % "triple: "  x . y . z
 }
 

} } } return set } </lang>

C#

<lang csharp>using System.Linq;

static class Program {

 static void Main()
 {
   var ts =
     from a in Enumerable.Range(1, 20)
     from b in Enumerable.Range(a, 21 - a)
     from c in Enumerable.Range(b, 21 - b)
     where a * a + b * b == c * c
     select new { a, b, c };
     foreach (var t in ts)
       System.Console.WriteLine("{0}, {1}, {2}", t.a, t.b, t.c);
 }

} </lang>

C++

There is no equivalent construct in C++. The code below uses three nested loops and an if statement:

<lang cpp>#include <vector>

  1. include <cmath>
  2. include <iostream>
  3. include <algorithm>
  4. include <iterator>

void list_comprehension( std::vector<int> & , int ) ;

int main( ) {

  std::vector<int> triangles ;
  list_comprehension( triangles , 20 ) ;
  std::copy( triangles.begin( ) , triangles.end( ) ,

std::ostream_iterator<int>( std::cout , " " ) ) ;

  std::cout << std::endl ;
  return 0 ;

}

void list_comprehension( std::vector<int> & numbers , int upper_border ) {

  for ( int a = 1 ; a < upper_border ; a++ ) {
     for ( int b = a + 1 ; b < upper_border ; b++ ) {

double c = pow( a * a + b * b , 0.5 ) ; //remembering Mr. Pythagoras if ( ( c * c ) < pow( upper_border , 2 ) + 1 ) { if ( c == floor( c ) ) { numbers.push_back( a ) ; numbers.push_back( b ) ; numbers.push_back( static_cast<int>( c ) ) ; } }

     }
  }

} </lang>

This produces the following output: 3 4 5 5 12 13 6 8 10 8 15 17 9 12 15 12 16 20

Clojure

<lang lisp>(for [x (range 1 21) y (range x 21) z (range y 21) :when (= (+ (* x x) (* y y)) (* z z))] [x y z])</lang>

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>


D

D doesn't have list comprehensions. The following is mostly a toy.

<lang d>import std.string: writeln; import std.algorithm: iota; import std.array, std.typetuple;

TA[] select(TA, TI1, TC1, TI2, TC2, TI3, TC3, TP)

          (lazy TA mapper,
           ref TI1 iter1, TC1 items1,
           ref TI2 iter2, lazy TC2 items2,
           ref TI3 iter3, lazy TC3 items3,
           lazy TP where) {
   Appender!(TA[]) result;
   // save original iteration variables
   auto iters = TypeTuple!(iter1, iter2, iter3);
   foreach (el1; items1) {
       iter1 = el1;
       foreach (el2; items2) {
           iter2 = el2;
           foreach (el3; items3) {
               iter3 = el3;
               if (where())
                   result.put(mapper());
           }
       }
   }
   // restore original iteration variables
   TypeTuple!(iter1, iter2, iter3) = iters;
   return result.data;

}

void main() {

   enum int n = 21;
   int x, y, z;
   auto r = select((x,y,z), x, iota(1,n+1), y, iota(x,n+1), z, iota(y,n+1), x^^2 + y^^2 == z^^2);
   writeln(r);

}</lang>

It computes the result: 5 13 10 17 15 20

E

<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]) } } } }</lang>

Efene

<lang efene>pythag = fn (N) {

   [(A, B, C) for A in lists.seq(1, N) \
        for B in lists.seq(A, N) \
        for C in lists.seq(B, N) \
        if A + B + C <= N and A * A + B * B == C * C]

}

@public run = fn () {

   io.format("~p~n", [pythag(20)])

} </lang>

Erlang

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

F#

<lang fsharp>let pyth n = [ for a in [1..n] do

              for b in [a..n] do
              for c in [b..n] do
              if (a*a+b*b = c*c) then yield (a,b,c)]</lang>

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>

Ioke

<lang ioke>for(

 x <- 1..20, 
 y <- x..20, 
 z <- y..20,
 x * x + y * y == z * z,
 [x, y, z]

)</lang>

J

<lang J>require'stats' triples=: 1 + 3&comb isPyth=: 2&{"1 = 1&{"1 +&.:*: 0&{"1 pythTr=: (#~ isPyth)@triples</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.

In the above example, the word isPyth is our predicate (represented as B in the preceding paragraph). This corresponds to the constraint clause in set builder notation.

In the above example the word triples represents the universe of potential solutions (some of which will be valid, some not). This corresponds to the generator part of set builder notation.

The argument to isPyth will be the candidate solutions (the result of triples). The argument to triples will be the largest element desired in a triple.

Example use:

<lang J> pythTr 20

3  4  5
5 12 13
6  8 10
8 15 17
9 12 15

12 16 20</lang>

JavaScript

Translation of: Python
Works with: JavaScript version 1.7+ (Firefox 2+)
Works with: SpiderMonkey version 1.7

See here for more details

<lang javascript>function range(begin, end) {

   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);</lang>

outputs:

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

Lua

Lua doesn't have list comprehensions built in, but they can be constructed from chained coroutines:

<lang lua> LC={} LC.__index = LC

function LC:new(o)

 o = o or {}
 setmetatable(o, self)
 return o

end

function LC:add_iter(func)

 local prev_iter = self.iter
 self.iter = coroutine.wrap(
   (prev_iter == nil) and (function() func{} end)
   or (function() for arg in prev_iter do func(arg) end end))
 return self

end

function maybe_call(maybe_func, arg)

 if type(maybe_func) == "function" then return maybe_func(arg) end
 return maybe_func

end

function LC:range(key, first, last)

 return self:add_iter(function(arg)
   for value=maybe_call(first, arg), maybe_call(last, arg) do
     arg[key] = value
     coroutine.yield(arg)
   end
 end)

end

function LC:where(pred)

 return self:add_iter(function(arg) if pred(arg) then coroutine.yield(arg) end end)

end </lang>

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

<lang lua> function get(key)

 return (function(arg) return arg[key] end)

end

function is_pythagorean(arg)

 return (arg.x^2 + arg.y^2 == arg.z^2)

end

function list_pythagorean_triples(n)

 return LC:new():range("x",1,n):range("y",1,get("x")):range("z", get("y"), n):where(is_pythagorean).iter

end

for arg in list_pythagorean_triples(100) do

 print(arg.x, arg.y, arg.z)

end </lang>

Mathematica

<lang mathematica>Select[Tuples[Range[n], 3], #11^2 + #12^2 == #13^2 &]</lang>

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

Oz

Oz does not have list comprehension.

However, there is a list comprehension package available here. It uses the unofficial and deprecated macro system. Usage example:

<lang oz>functor import

  LazyList
  Application
  System

define

  fun {Pyth N}
     <<list [X Y Z] with

X <- {List.number 1 N 1} Y <- {List.number X N 1} Z <- {List.number Y N 1} where X*X + Y*Y == Z*Z

     >>
  end
  {ForAll {Pyth 20} System.show}
  {Application.exit 0}

end</lang>

PARI/GP

<lang>vector(100,x,x^3+sin(x))</lang>

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>

Perl 6

Perl 6 has single-dimensional list comprehensions that fall out naturally from nested modifiers; multidimensional comprehensions are also supported via the cross operator; however, Perl 6 does not (yet) support multi-dimensional list comprehensions with dependencies between the lists, so the most straightforward way is currently: <lang perl6>my $n = 20; gather for 1..$n -> $x {

        for $x..$n -> $y {
          for $y..$n -> $z {
            take $x,$y,$z if $x*$x + $y*$y == $z*$z;
          }
        }
      }</lang>

Note that gather/take is the primitive in Perl 6 corresponding to generators or coroutines in other languages. It is not, however, tied to function call syntax in Perl 6. We can get away with that because lists are lazy, and the demand for more of the list is implicit; it does not need to be driven by function calls.

PicoLisp

PicoLisp doesn't have list comprehensions. We might use a generator function, pipe or coroutine.

Using a generator function

<lang PicoLisp>(de pythag (N)

  (job '((X . 1) (Y . 1) (Z . 0))
     (loop
        (when (> (inc 'Z) N)
           (when (> (inc 'Y) N)
              (setq Y (inc 'X)) )
           (setq Z Y) )
        (T (> X N))
        (T (= (+ (* X X) (* Y Y)) (* Z Z))
           (list X Y Z) ) ) ) )

(while (pythag 20)

  (println @) )</lang>

Using a pipe

<lang PicoLisp>(pipe

  (for X 20
     (for Y (range X 20)
        (for Z (range Y 20)
           (when (= (+ (* X X) (* Y Y)) (* Z Z))
              (pr (list X Y Z)) ) ) ) )
  (while (rd)
     (println @) ) )</lang>

Using a coroutine

Coroutines are available only in the 64-bit version. <lang PicoLisp>(de pythag (N)

  (co 'pythag
     (for X N
        (for Y (range X N)
           (for Z (range Y N)
              (when (= (+ (* X X) (* Y Y)) (* Z Z))
                 (yield (list X Y Z)) ) ) ) ) ) )

(while (pythag 20)

  (println @) )</lang>

Output in all three cases:

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

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>

Scala

<lang scala>def pythagoranTriangles(n: Int) = for {

 x <- 1 to 21
 y <- x to 21
 z <- y to 21
 if x * x + y * y == z * z

} yield (x, y, z)</lang>

which is a syntactic sugar for:

<lang scala> def pythagoranTriangles(n: Int) = (1 to n) flatMap (x =>

 (x to n) flatMap (y => 
   (y to n) filter (z => x * x + y * y == z * z) map (z => 
     (x, y, z))))</lang>

Alas, the type of collection returned depends on the type of the collection being comprehended. In the example above, we are comprehending a Range. Since a Range of triangles doesn't make sense, it returns the closest (supertype) collection for which it does, an IndexedSeq.

To get a List out of it, just pass a List to it:

<lang scala>def pythagoranTriangles(n: Int) = for {

 x <- List.range(1, n + 1)
 y <- x to 21
 z <- y to 21
 if x * x + y * y == z * z

} yield (x, y, z)</lang>

Sample:

scala> pythagoranTriangles(21)
res36: List[(Int, Int, Int)] = List((3,4,5), (5,12,13), (6,8,10), (8,15,17), (9,12,15), (12,16,20))

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}

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.

<lang ti89b>{1, 2, 3, 4} → a seq(a[i]^2, i, 1, dim(a))</lang>

produces {1, 4, 9, 16}. When the input is simply a numeric range, an input list is not needed; this produces the same result:

<lang ti89b>seq(x^2, x, 1, 4)</lang>

Visual Basic .NET

This example is untested. Please check that it's correct, debug it as necessary, and remove this message.


Translation of: C#

<lang vbnet>Module ListComp

   Sub Main()
       Dim ts = From a In Enumerable.Range(1, 20) _
                From b In Enumerable.Range(a, 21 - a) _
                From c In Enumerable.Range(b, 21 - b) _
                Where a * a + b * b == c * c _
                Select New With { a, b, c }
       
       For Each t In ts
           System.Console.WriteLine("{0}, {1}, {2}", t.a, t.b, t.c)
       Next
   End Sub

End Module</lang>

Wrapl

<lang wrapl>ALL WITH x <- 1:to(n), y <- x:to(n), z <- y:to(n) DO (x^2 + y^2 = z^2) & [x, y, z];</lang>