comprehending comprehensions
Roy Smith
confusing. Is this some standard computer science term? Is it stolen
from some other language?
Alan Gauld
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.
Sean 'Shaleh' Perry
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.
Sean Ross
"Roy Smith" <r...@panix.com> wrote in message
news:roy-9EE81E.1...@reader1.panix.com...
Lulu of the Lotus-Eaters
|> 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> ]--------------------------
Erik Max Francis
> 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
Maurix
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?
Bengt Richter
>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
Skip Montanaro
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
Maurix
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?