HelpSource/Guides/ListComprehensions.schelp

   1 title:: List Comprehensions
   2 categories:: Language, Collections
   3 summary:: list comprehensions and generator expressions
   4
   5 section:: Introduction
   6
   7 List comprehensions are a syntactic feature of functional programming languages like Miranda, Haskell, and Erlang which were later copied into Python.
   8 You can search the web for "list comprehensions" or "generator expressions" to learn more.
   9 Basically list comprehensions are for getting a series of solutions to a problem.
  10
  11 in SC these are just a syntax macro for a longer expression. read this as emphasis:: "all [x,y] for x in 1..5, y in 1..x, such that x+y is prime" :::
  12 code::
  13 all {:[x,y], x <- (1..5), y <- (1..x), (x+y).isPrime }
  14 ::
  15 returns:
  16 code::
  17 [ [ 1, 1 ], [ 2, 1 ], [ 3, 2 ], [ 4, 1 ], [ 4, 3 ], [ 5, 2 ] ]
  18 ::
  19
  20 the list comprehension above is equivalent to the following code:
  21 code::
  22 all(Routine.new({ (1..5).do {|x| (1..x).do {|y| if ((x+y).isPrime) {[x,y].yield} }}}));
  23 ::
  24 ..but much more concise and much easier to keep in your head than writing it out.
  25
  26 In the list comprehension compiler, simple series like code::(1..5):: and code::(1..x):: are treated as special cases and implemented as loops rather than making a collection.
  27
  28 A list comprehension in SC is really a link::Classes/Routine::. You can use the code::all:: message to collect all of the Routine's results into a list.
  29
  30 section:: A few examples
  31 code::
  32 all {: x/(x+1), x <- (1..5) }
  33
  34 [ 0.5, 0.66666666666667, 0.75, 0.8, 0.83333333333333 ]
  35 ::
  36 code::
  37 all {:[x,y], x <- (1..3), y <- [\a,\b,\c] }
  38
  39 [ [ 1, a ], [ 1, b ], [ 1, c ], [ 2, a ], [ 2, b ], [ 2, c ], [ 3, a ], [ 3, b ], [ 3, c ] ]
  40 ::
  41 code::
  42 all {:[x,y], x <- (0..3), y <- (x..0) }
  43
  44 [ [ 0, 0 ], [ 1, 1 ], [ 1, 0 ], [ 2, 2 ], [ 2, 1 ], [ 2, 0 ], [ 3, 3 ], [ 3, 2 ], [ 3, 1 ], [ 3, 0 ] ]
  45 ::
  46 code::
  47 all {:y, x <- (1..4), y <- (x..1) }
  48
  49 [ 1, 2, 1, 3, 2, 1, 4, 3, 2, 1 ]
  50 ::
  51
  52 code::
  53 (
  54 var intervals;
  55 // a function to generate intervals between all pairs of notes in a chord voicing
  56 intervals = {|chord|
  57         all {: chord[i+gap] - chord[i],
  58                 gap <- (1 .. chord.lastIndex),
  59                 i <- (0 .. chord.lastIndex - gap)
  60         }
  61 };
  62
  63 intervals.([0,4,7,10]).postln;
  64 intervals.([0,1,3,7]).postln;
  65 )
  66
  67 [ 4, 3, 3, 7, 6, 10 ]
  68 [ 1, 2, 4, 3, 6, 7 ]
  69 ::
  70
  71 code::
  72 all {:[y, z], x<-(0..30), var y = x.nthPrime, var z = 2 ** y - 1, z.asInteger.isPrime.not  }
  73 [ [ 11, 2047 ], [ 23, 8388607 ], [ 29, 536870911 ] ] // mersenne numbers which are no primes
  74 ::
  75
  76 section:: Qualifier Clauses
  77
  78 A list comprehension begins with code:: {: :: and contains a body followed by several qualifier clauses separated by commas.
  79 code::
  80 {: body , qualifiers }
  81 ::
  82 There are several types of qualifier clauses that can appear after the body.
  83
  84 subsection:: generator clause
  85
  86 The basic clause is the generator clause. Its syntax is
  87 code::
  88 name <- expr
  89 ::
  90 The expression should be something that can respond meaningfully to 'do' such as a collection or a stream.
  91 The name takes on each value of the expression.
  92 The name is a local variable whose scope extends to all clauses to the right. The name is also in scope in the body.
  93 code::
  94 all {: x, x <- (1..3) }
  95
  96 [ 1, 2, 3 ]
  97 ::
  98 code::
  99 all {: x, x <- [\a, \b, \c] }
 100
 101 [ a, b, c ]
 102 ::
 103 code::
 104 all {: x, x <- (1!3)++(2!2)++3 }
 105
 106 [ 1, 1, 1, 2, 2, 3 ]
 107 ::
 108 multiple generators act like nested loops.
 109 code::
 110 all {: [x,y], x <- (1..2), y <- (10,20..30) }
 111
 112 [ [ 1, 10 ], [ 1, 20 ], [ 1, 30 ], [ 2, 10 ], [ 2, 20 ], [ 2, 30 ] ]
 113 ::
 114 generators can depend on previous values.
 115 code::
 116 all {: x, x <- (1..3), y <- (1..x) }
 117
 118 [ 1, 2, 2, 3, 3, 3 ]
 119 ::
 120 code::
 121 all {: x, x <- (1..3), y <- (1..4-x) }
 122
 123 [ 1, 1, 1, 2, 2, 3 ]
 124 ::
 125
 126 subsection:: guard clause
 127
 128 A guard clause is simply an expression. It should return a boolean value.
 129 code::
 130 expr
 131 ::
 132 The guard acts as a filter on the results and constrains the search.
 133 code::
 134 all {: x, x <- (0..10), x.odd }
 135
 136 [ 1, 3, 5, 7, 9 ]
 137 ::
 138 code::x.odd:: is the guard and causes all even numbers to be skipped.
 139 code::
 140 all {: x, x <- (0..30), (x % 5 == 0) || x.isPowerOfTwo }
 141
 142 [ 0, 1, 2, 4, 5, 8, 10, 15, 16, 20, 25, 30 ]
 143 ::
 144 you can have multiple guards.
 145 code::
 146 all {: [x,y], x <- (0..10), (x % 5 == 0) || x.isPowerOfTwo, y <- (1..2), (x+y).even }
 147
 148 [ [ 0, 2 ], [ 1, 1 ], [ 2, 2 ], [ 4, 2 ], [ 5, 1 ], [ 8, 2 ], [ 10, 2 ] ]
 149 ::
 150
 151 subsection:: var clause
 152
 153 A var clause lets you create a new variable binding that you can use in your expressions.
 154 The scope of the name extends to all clauses to the right and in the body.
 155 code::
 156 var name = expr
 157 ::
 158 Unlike the generator clause, the name is bound to a single value, it doesn't iterate.
 159 code::
 160 all {: z, x <- (1..20), var z = (x*x-x) div: 2, z.odd }
 161
 162 [ 1, 3, 15, 21, 45, 55, 91, 105, 153, 171 ]
 163 ::
 164
 165 subsection:: side effect clause
 166
 167 This clause lets you insert code to do some side effect like printing.
 168 code::
 169 \:: expr
 170 ::
 171 code::
 172 all {: z, x <- (1..20), var z = (x*x-x) div: 2, :: [x,z].postln, z.even }
 173 ::
 174
 175 subsection:: termination clause
 176
 177 The termination clause is for stopping further searching for results. Once the expression becomes false,
 178 the routine halts.
 179 code::
 180 :while expr
 181 ::
 182
 183 using a guard
 184 code::
 185 all {: z, x <- (1..20), var z = (x*x-x) div: 2,  :: [x,z].postln, z < 50 }
 186 ::
 187
 188 using a termination clause. this one stops searching, so does less work than the above.
 189 code::
 190 all {: z, x <- (1..20), var z = (x*x-x) div: 2,  :: [x,z].postln, :while z < 50 }
 191 ::
 192
 193 section:: Constrained Search
 194
 195 list comprehensions can solve constrained combinatorial problems like this one:
 196
 197 Baker, Cooper, Fletcher, Miller, and Smith live on different floors of an apartment house that contains only five floors.
 198 Baker does not live on the top floor. Cooper does not live on the bottom floor.
 199 Fletcher does not live on either the top or the bottom floor. Miller lives on a higher floor than does Cooper.
 200 Smith does not live on a floor adjacent to Fletcher's. Fletcher does not live on a floor adjacent to Cooper's.
 201 Where does everyone live?
 202 code::
 203 (
 204 z = {: [baker, cooper, fletcher, miller, smith] ,
 205     var floors = (1..5),
 206     baker <- floors,  baker != 5,  // Baker does not live on the top floor.
 207     // remove baker's floor from the list.
 208     // var creates a new scope, so the 'floors' on the left is a new binding.
 209     var floors = floors.removing(baker),
 210     cooper <- floors, cooper != 1, // Cooper does not live on the bottom floor.
 211     var floors = floors.removing(cooper), // remove cooper's floor from the list.
 212     fletcher <- floors, (fletcher != 5) && (fletcher != 1) // Fletcher does not live on either top or bottom floor.
 213         && (absdif(fletcher, cooper) > 1), // Fletcher does not live on a floor adjacent to Cooper's.
 214     var floors = floors.removing(fletcher), // remove fletcher's floor
 215     miller <- floors, miller > cooper, // Miller lives on a higher floor than does Cooper.
 216     var floors = floors.removing(miller), // remove miller's floor
 217     smith <- floors, absdif(fletcher, smith) > 1  // Smith does not live on a floor adjacent to Fletcher's.
 218 };
 219 )
 220
 221 z.next; // [3, 2, 4, 5, 1 ]
 222 z.next; // nil.  only one solution
 223 ::
 224
 225 combinatorial problems can take a lot of time to run.
 226 you can reorder the above tests to make it run faster. generally you want to search the most constrained variables first.
 227 the most constrained person above is fletcher, so he should be searched first, then cooper, etc.
 228
 229
 230 section:: Grammar
 231
 232 Here is the BNF grammar for list comprehensions in SC.
 233 code::
 234 [ ] - optional
 235 { } - zero or more
 236
 237 <list_compre> ::= "{:" <body> ',' <qualifiers> "}"
 238
 239 <body> ::= <exprseq>
 240
 241 <exprseq> ::= <expr> { ";" <expr> }
 242
 243 <qualifiers> ::= <qualifier> { ',' <qualifiers> }
 244
 245 <qualifier> ::= <generator> | <guard> | <binding> | <side_effect> | <termination>
 246
 247 <generator> ::= <name> "<-" <exprseq>
 248
 249 <guard> ::= <exprseq>
 250
 251 <binding> ::= "var" <name> "=" <exprseq>
 252
 253 <side_effect> ::= "::" <exprseq>
 254
 255 <termination> ::= ":while" <exprseq>
 256 ::
 257
 258 section:: Code Generation
 259
 260 For each of the above clauses, here is how the code is generated. The body acts as the innermost qualifier.
 261 By understanding these translations, you can better understand how scoping and control flow work in list comprehensions.
 262
 263 definitionlist::
 264 ## generator || code::
 265 expr.do {|name| ..next qualifier.. }
 266 ::
 267
 268 ## guard || code::
 269 if (expr) { ..next qualifier.. }
 270 ::
 271
 272 ## binding || code::
 273 {|name| ..next qualifier.. }.value(expr)
 274 ::
 275
 276 ## side effect || code::
 277 expr ; ..next qualifier..
 278 ::
 279
 280 ## termination || code::
 281 if (expr) { ..next qualifier.. }{ nil.alwaysYield }
 282 ::
 283 ::
 284