List comprehensions

[Albert Hofkamp]

On Wed, 22 Dec 1999, Alexander Williams <thantos at chancel.org> wrote:
>On 21 Dec 1999 17:21:27 GMT, Albert Hofkamp <hat at se-46.wpa.wtb.tue.nl>
>wrote:
>>Say for yourself:
>>
>> *[ x<0 -> x:=x+2 
>>  | x>0 -> x:=x-3
>>  ]
>>
>>is much nicer than
>>
>> while x<0 or x>0:
>>   if x<0:
>>     x:=x+2
>>   elif x>0:
>>     x:=x-3
>>
>><big smile>
>
>Hmmm, am I to assume that the *[] syntax causes it to return a curried
>function that takes a list of things as its argument and returns a
>list of things as its result?  If so, then your while example in
>Python there is a bit flawed ...

No it is not, chi is heavily based on CSP and guarded command language
(from Dijkstra). The [ .. ] is a case-like selection statement (except
with non-deterministic choice). '|' separates alternatives, the
expression before the '->' is the guard, and the statements behind it
are executed after the choice is made. The *-prefix means it is repetitive.

The Python translation is thus correct, except that the order of
evaluation of the guards may be the other way around.

( Unlike Python, chi is not a intuitive language at first sight. It
  takes some time to understand it, but it allows very compact notation of
  calculations with a lot of data. It is mainly being used to describe
  scheduling strategies used in manufacturing control systems of highly
  complex factories ).

Ok, enough off-topic for now. People who want to know more, plz email me.

>    >>> zip(xs, ys)
>
>... and get exactly the list you wanted; once you have zipped lists
>together, you can then feed them to a Comprehension.

This is even shorter than the map() call.
Sorry for asking, but is it safe to assume that

  for x,y in zip(xs,ys):
    print x,y

works as expected  (and in list comprehensions as well then) ?
(I am still a terribly newbie at Python.
 It is a fascinating language, you learn new constructs every day !!
)

>Works in Python, though (or it will, once we have Comprehensions in
>place ...

I did some thinking about fold(), and came to the conclusion that your
idea is correct. Fold should be left separate from map and filter.

My basic problem with fold was that is is too much hassle, but that is
not the fault of fold, but of our language, because it doesn't allow
writing expressions as a name-less function.

>wonder if I can push for infinite lists, too? ...)  :)

Sure, just implement lazy evaluation :-)

>>  [ x+3 | y <- ys, z <- zs, y>z, x <- xs, y+z<x ]
>>
>>and define separate functions for each level.
>>(anyone care to do this with map and filter ?)
>
>Let's see ...  Not really easily with map and filter, because quite
>honestly they're intended to be soley parallel iterators (fulfilling

Hmm, maybe this is the cause of the misunderstandings about these
parallel iterators.
Due to my lack of knowledge of Python, I assumed map() and filter() as
described in Bird & Wadler for functional programming.

Basic idea there is
map(f,xs): applies function f to each element of xs, and returns a list
	of results.
filter(f,xs): applies function f to each element of xs, and returns a
	list of elements for which f returns true.

Tricks like you explain with zip() are not part of their definition.
I have read the Python tutorial, and saw these two functions, and
assumed that I understood what they meant. Apparently, I missed an
extension (wrt Bird&Wadler) that allows zip()-like functionality.

I must have a closer look at these functions !!


>Interestingly, though, with a wee bit of juggling, its structure looks
>very similar, like so:
>
>    Haskell:
>    >>> retList = [x+3 | y <- ys, 
>    >>> 	         z <- zs, y>z, 
>    >>> 	         x <- xs, y+z<x]
>
>... mirrors the (slightly reorganized) ...
>
>    Python:
>    >>> for y in ys:
>    >>>     for z in zs:
>    >>>         if y>z:
>    >>>            for x in xs:
>    >>>                if (y+z)<x:
>    >>>                   retList.append(x+3)
>
>Interestingly, they have the same structure in both the list
>expansions and the tests.

I think that is what makes them so easy to read and understand.
Once you have this mapping in your mind, you can almost write it down
without thinking. When you then have to convert it to a language without
this constrcut, it turns out to be a nightmare in 'normal' coding :-)

>My own intuitive feeling is that a List Comprehension should return a
>/list/ (even if its an empty list or a singleton list), while if you
>want a single value to emerge, you need a function.  Now, this begs

I fully agree on that.
Basically, the [ and ] already make you believe the result is a list,
even if you don't fully understand the contents.

>the question of those times a list /is/ the value and when its a list
>of values ...

I probably don't fully understand the consequences, but I see no real
problem (but all languages I really know work with static typing).

With a list comprehension, you get as much levels of lists as you put
in, with a function, it is reduced with at least 1 level.

    xs = [ [], [], [] ]
    [ x | x <- xs, x!=[1] ] returns a list of lists (equal to xs in fact)
    fold() returns a list (at most, depending on what the folding function
    does).

(about the latter, assume eg that I write a fold which calculates the
 maximum length of the elements in xs. The input is a list of lists, and
 the output is a natural number)


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