102 views

Skip to first unread message

Jun 14, 2003, 1:52:17 PM6/14/03

to

Why are list comprehensions called what they are? I find the name very

confusing. Is this some standard computer science term? Is it stolen

from some other language?

confusing. Is this some standard computer science term? Is it stolen

from some other language?

Jun 14, 2003, 2:41:20 PM6/14/03

to

On Sat, 14 Jun 2003 13:52:17 -0400, Roy Smith <r...@panix.com>

wrote:

> Why are list comprehensions called what they are? I find the name very

> confusing. Is this some standard computer science term? Is it stolen

> from some other language?

wrote:

> Why are list comprehensions called what they are? I find the name very

> confusing. Is this some standard computer science term? Is it stolen

> from some other language?

I know it from the functional programming language Haskell

And I believe it's a math term for collecting things together.

Comprehension as in comprehensive not as in comrehending

(understanding). But I could be wrong on that...

Alan g.

Jun 14, 2003, 2:21:45 PM6/14/03

to

it came from the functional programing world via ML (or was it Haskell).

That's what they called it.

looking up comprehension in a dictionary (.com) I find :

3. Logic. The sum of meanings and corresponding implications inherent in a

term.

which I suspect is the meaning used here.

Jun 14, 2003, 2:48:25 PM6/14/03

to

http://wombat.doc.ic.ac.uk/foldoc/foldoc.cgi?list+comprehension

"Roy Smith" <r...@panix.com> wrote in message

news:roy-9EE81E.1...@reader1.panix.com...

Jun 14, 2003, 4:54:36 PM6/14/03

to

|Roy Smith wrote:

|> Why are list comprehensions called what they are?

|> Why are list comprehensions called what they are?

Sean 'Shaleh' Perry <shale...@attbi.com> wrote

|it came from the functional programing world via ML (or was it Haskell).

Perry's answer is correct, as far as it goes. But the Haskell/ML usage

itself derives from Zermelo-Frankel axiomatic set theory. In

particular, the Axiom of Comprehension states: given a set A and a

predicate P, there uniquely exists a set B that contains only elements

of A that fulfill P.

Now backtracking a little, why such an odd axiom? This is because of

Russell's paradox. Back in the old days, mathematicians thought that

sets were simply the extensionality of intention predicates. In other

words, given any predicate, sui generis, there is a set of things

fulfilling the predicate.

Russell asked, What about the set of all things that are not members of

themselves? (It is a member of itself if-and-only-if it is not a

member of itself). Russell had this awkward solution involving type

hierarchies that is best forgotten. The more elegant solution is ZFC

axiomatization. In particular, you avoid the paradox if you need to

start with a prior set A, and only check the predicate against its

members.

So what does this have to do with list comprehensions. Well, recall how

you would write the set B in math notation. Subject to the limits of my

keyboard, something like:

B = {x | x <- A s.t. P(x)}

I try to draw the "member of" symbol as "<-" in ASCII.

Now suppose we turn the usual squiggly set brackets into angle brackets,

and replace "s.t." (such that) with a simple comma:

[x | x <- A, P(x)]

Viola... Haskell. Now suppose we use the word "in" instead of the

ASCII attempt at the member symbol. And we use the word "if" instead of

"s.t.". And also, the conditionality mark "|" is expanded to the word

"for":

[x for x in A if P(x)]

And that's Python.

Yours, Lulu...

--

---[ to our friends at TLAs (spread the word) ]--------------------------

Echelon North Korea Nazi cracking spy smuggle Columbia fissionable Stego

White Water strategic Clinton Delta Force militia TEMPEST Libya Mossad

---[ Postmodern Enterprises <me...@gnosis.cx> ]--------------------------

Jun 14, 2003, 5:11:16 PM6/14/03

to

Lulu of the Lotus-Eaters wrote:

> So what does this have to do with list comprehensions. Well, recall

> how

> you would write the set B in math notation. Subject to the limits of

> my

> keyboard, something like:

>

> B = {x | x <- A s.t. P(x)}

>

> I try to draw the "member of" symbol as "<-" in ASCII.

In this set notation, it's | (sometimes written as a colon) that means

"such that." Where you wrote "s.t.," you really meant logical and:

B = {x | x in A and P(x)}

[where `in' is set membership and `and' is logical conjunction].

--

Erik Max Francis && m...@alcyone.com && http://www.alcyone.com/max/

__ San Jose, CA, USA && 37 20 N 121 53 W && &tSftDotIotE

/ \ To perceive is to suffer.

\__/ Aristotle

Jun 14, 2003, 6:46:55 PM6/14/03

to

Hi, as you are speaking of comprehensions, functional languages

and Haskell; i want to propose a game to the group:

Let's make some examples to see how long is python compared

with Haskell.

I've make my try, writing the famous example of qsort in Haskell

in a "functional" python:

and Haskell; i want to propose a game to the group:

Let's make some examples to see how long is python compared

with Haskell.

I've make my try, writing the famous example of qsort in Haskell

in a "functional" python:

Haskell:

qsort [] = []

qsort (x:xs) = qsort elts_lt_x ++ [x] ++ qsort elts_greq_x

where

elts_lt_x = [y | y <- xs, y < x]

elts_greq_x = [y | y <- xs, y >= x]

Python:

def qsort(list) :

if len(list)<=1 : return list

x,xs=list[0],list[1:]

elts_lt_x=[y for y in xs if y < x]

elts_greq_x=[y for y in xs if y >= x]

return qsort(elts_lt_x)+[x]+qsort(elts_greq_x)

6 lines vs 5 lines, not bad!

Someting can do it better??

I have a question too, there something in haskell that is

difficult to "copy" with python?

I like haskell for his math-style but have really something more?

Jun 14, 2003, 8:49:39 PM6/14/03

to

On Sat, 14 Jun 2003 22:46:55 GMT, Maurix <maurix78_r...@wanadoo.es> wrote:

>Hi, as you are speaking of comprehensions, functional languages

>and Haskell; i want to propose a game to the group:

>Let's make some examples to see how long is python compared

>with Haskell.

>I've make my try, writing the famous example of qsort in Haskell

>in a "functional" python:

>

>Haskell:

>

>qsort [] = []

>qsort (x:xs) = qsort elts_lt_x ++ [x] ++ qsort elts_greq_x

> where

> elts_lt_x = [y | y <- xs, y < x]

> elts_greq_x = [y | y <- xs, y >= x]

>

>

>Python:

>

>def qsort(list) :

> if len(list)<=1 : return list

> x,xs=list[0],list[1:]

> elts_lt_x=[y for y in xs if y < x]

> elts_greq_x=[y for y in xs if y >= x]

> return qsort(elts_lt_x)+[x]+qsort(elts_greq_x)

>

>6 lines vs 5 lines, not bad!

>Someting can do it better??

You can take a line out by taking advantage of short circuit logic and

the fact that list.append returns None:

(it breaks the lookalike pattern though ;-)

def qsort(seq) : # practically untested

if len(seq)<=1 : return seq

x,xs,elts_greq_x = seq[0],seq[1:],[]

elts_lt_x=[y for y in xs if y < x or elts_greq_x.append(y)] #(append => None)

return qsort(elts_lt_x)+[x]+qsort(elts_greq_x)

BTW, 'list' is a builtin, so it's not a good choice for a parameter name.

>

>I have a question too, there something in haskell that is

>difficult to "copy" with python?

>

>I like haskell for his math-style but have really something more?

Haskell and ML (OCAML?) are both round tuits as yet for me.

Which is tastiest?

Regards,

Bengt Richter

Jun 14, 2003, 9:33:02 PM6/14/03

to

maurix> def qsort(list) :

maurix> if len(list)<=1 : return list

maurix> x,xs=list[0],list[1:]

maurix> elts_lt_x=[y for y in xs if y < x]

maurix> elts_greq_x=[y for y in xs if y >= x]

maurix> return qsort(elts_lt_x)+[x]+qsort(elts_greq_x)

maurix> 6 lines vs 5 lines, not bad!

maurix> Someting can do it better??

The temporary list comprehensions aren't really needed:

def qsort(lst):

if len(lst) <= 1: return lst

x, xs = lst[0], lst[1:]

return (qsort([i for i in xs if i<x]) + [x] +

qsort([i for i in xs if i>=x])

and if you're willing to forego a little bit of white space:

def qs(lst):

if len(lst) <= 1: return lst

x, y = lst[0], lst[1:]

return qs([i for i in y if i<x])+[x]+qs([i for i in y if i>=x])

Eliminating x and y then crushing a bit more white space:

def qs(l):

if len(l) <= 1: return l

return qs([i for i in l[1:]if i<l[0]])+l[:1]+qs([i for i in l[1:]if i>=l[0]])

Finally, the ultimate abuse:

def qs(l):

return len(l) > 1 and (qs([i for i in l[1:]if i<l[0]])+l[:1]+qs([i for i in l[1:]if i>=l[0]])) or l

Of course, these are all just variations on the theme you posted.

>>> def qs(l):

... return len(l) > 1 and (qs([i for i in l[1:]if i<l[0]])+l[:1]+qs([i for i in l[1:]if i>=l[0]])) or l

...

>>> import random

>>> import string

>>> l = list(string.letters)

>>> random.shuffle(l)

>>> "".join(l)

'CIaSFXhqQYuvDPsxVNUbepnjHmOiMdBkoRWtZwcKGzAgErfJLylT'

>>> "".join(qs(l))

'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz'

Skip

Jun 15, 2003, 6:42:34 AM6/15/03

to

Thanks for the ideas,

But, what about the order? If we want to be "fuctional" the order is not

to be important:

But, what about the order? If we want to be "fuctional" the order is not

to be important:

qsort=lambda l : len(l) > 1 and (...)

(...) qsort(elts_lt_x(l))+[l[0]]+qsort(elts_greq_x(l)) or l

elts_lt_x=lambda l : [y for y in l[1:] if y<l[0]]

elts_greq_x=lambda l : [y for y in l[1:] if y>=l[0]]

My aim is not to put all in a line, (if you want you can put the qsort

in c in the same line!!) but use a similar sintaxis of a pure functional

language.

I think "structurally" because i'm a c programmer but learning Python

i'm apreciating his functional style. Python permit it but, we think

functionally when we make algorithms?

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu