List comprehensions

[Albert Hofkamp]

On 20 Dec 1999 15:28:28 +0100, Magnus L. Hetland <mlh at vier.idi.ntnu.no> wrote:
>Greg Ewing <greg.ewing at compaq.com> writes:
>
>> skaller wrote:
>> > 
>> > What is the proposed syntax for list comprehensions?
>> 
>> The one my patch currently implements is:
>> 
>>    list_comprehension :== '[' expr iterator... ']'
>>    iterator :== 'for' target 'in' expr | 'if' expr

While on this subject, we introduced these things in our specification
language a few years back, and it was a huge success. We even decided to
drop support for the `normal' map & filter functions.

It might be nice to show our approach here.


We use

 [ res-expr | iter-list ]

 with iter-list :== iter-expr | iter-list , iter-expr
      iter-expr :== bool-expr | var <- expr

where res-expr is some expression (and the resulting type of the entire
               comprehension is a list of the type of that expression),
      bool-expr is a boolean expression,
      var <- expr is a mathematical-like notation for the 'for' construct

Semantics are defined (I can send you a definition if you like). In tis
forum, they are best explained with an example:


      xs := [ 1,2,3,4,5 ]
      print [ (x,y) | x <- xs, x>3, y <- xs, y>x ]

means

      result = []
      for x in xs:
         if x>3:
	    for y in xs:
	       if y>x:
	          result=result+[ (x,y) ]
      print result

in other words, iter-expressions are nested in each other.
Our experience is that it is quite easy to explain what it means, and it
gets used quite a lot (unlike those map() and filter() functions, which
most of our users did not understand).

For sets, we have a similar notation (the surrounding [ and ] become {
and }, and all lists (eg xs and ys) must be sets).
The latter restriction is mainly to force users to think about the
structure of their data rather than just construct something without
thinking.

>Have you looked into adding separators (like "and") between the
>iterators yet? (You *did* see that as a possibility, didn't you?)

We considered that as well, but we decided against it. Reason is mainly
how the line looked in ASCII. The word 'and' was considered too
distracting.

>After all, that is what is done in math, more or less... (Either using
>a logical and or a comma.)
>
>  (Quasi-LaTeX)
>  P = {(x,y) | x \in X \and y \in Y}

The element-sign was also considered against '<-'. The reason for not
choosing the first was that you may want to test the existence of an
element in a set as a boolean expression, like in

  [ x | x <- xs, x in yr ]

(for all x from xs, test whether the element is in yr (yr is a set), and
put those elements in the resulting list)
If you would use 'in' for both, then there is no way to differentiate
between both uses. Also, the '<-' more or less looks like pulling data
from the thing at the right, so it has a nice intuitive meaning.
(but our language is much more oriented towards mathematical notation
than Python).

[ As a side-note, if you use 'and' as seperator, then you run into
  similar trouble, although much more subtle.
  Is 'x>5 and y<4' one expression, or 2 seperated by 'and' ?
  Here, you won't get bitten, because the meaning of and corresponds with
  the meaning of the seperator.
]

>Hm... Do the iterators work in parallel? Or would I end up with a

I'd like to have that, except that I don't know how to write that
down. On the other hand, in our field, it is probably not needed much.

Also, I'd like to get rid of fold().
For example, how would you write an expression which calculates the sum
of all elements (or the sum of all elements which hold for some special
condition ?)
The same problem exists with finding the maximum element in a list.

>could the version with "and" mean, then? Since it is a bit more

I'd rather write that in a single for loop, like

   for (x,y) in (X,Y):

(but this means something completely different :-) )

>(Or am I just confused here?)

Not imho.



Albert
---
Look ma, windows without Windows !!