Talk:List comprehension

	This article is within the scope of WikiProject Computing, a collaborative effort to improve the coverage of computers, computing, and information technology on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.ComputingWikipedia:WikiProject ComputingTemplate:WikiProject ComputingComputing
???	This article has not yet received a rating on Wikipedia's content assessment scale.
???	This article has not yet received a rating on the project's importance scale.

Call me a pedant, but..

"This is the near equivalent to the above expression", where the above had "n*n":

 S = [2*x for x in range(101) if x**2 > 3]

Not quite.. "x**2" is very different to "x*x" if x is an integer. I recently wrote a subnet calculator where multiplying by 2 should be the same as a left shift (endian-ness dependent). My subnet masks would have been subject to rounding errors!

Feel free to remove this comment once people have finished arguing whether my edit was necessary :-) —Preceding unsigned comment added by 86.154.39.223 (talk) 22:43, 9 November 2010 (UTC)[reply]

History

"The earliest reference to the list comprehension notation is in Rod Burstall and John Darlington's description of their programming language, NPL from 1977, but already SETL had a similar construct." -- I don't understand this phrase. If SETL already had such a construct, how can the NPL one be the first reference? Is it the first occurence of the term, or is the SETL construct actually different?

The FOLDOC reference has similar, unclear statements. It's sometimes difficult to know which constructs "are the same". I can tell that SETL has a similar construct called a "tuple former" (see eg http://www.settheory.com/Chapters/Chapter_3.html). But it also works for sets (a "set former") and can contain quantifications forall and exists. It might also be that there are no accepted "references" about SETL. --TuukkaH 09:57, 28 August 2006 (UTC)[reply]

It is indeed incomprehensible, because it badly misuses the words "reference" and "notation". I've attempted to improve it. -- 98.108.203.136 (talk) 03:05, 30 June 2008 (UTC)[reply]

Forms of List Comprehension

"Certain lists are too complex to express by other means." -- An example would be nice.

It could be easier to give for the previous formulation: "Thus the resulting operation can be complex to express in other means." One example of advanced list comprehension use I've seen is the Haskell solution and generalization here: http://www.frank-buss.de/challenge/index.html --TuukkaH 22:28, 31 August 2006 (UTC)[reply]

The claim is absurd. -- 98.108.203.136 (talk) 03:20, 30 June 2008 (UTC)[reply]

I just don't get it

This definition seems to only make sense if you already know what a list comprehension is! In which case -- why would you be looking up the definition?

Let me take it apart, to try and demontrate what I mean:

"In programming languages, list comprehension is a construct for list processing, analogous to the set-builder notation (set comprehension), that is, the mathematical notation such as the following:"

Okay -- so it's a 'construct for list processing' -- that seem to be categorising it, not explaining it.

And it's 'analogous to the set-builder notation (set comprehension)' -- so we've said that it's similar to set comprehension.

This seems to be uniquely devoid of any description... to summarise:

"List comprehensions are a construct for list processing, that is similar to set comprehensions"

Now getting back to the first few words: "In programming languages" -- this doesn't seem to be accurate. Are list comprehensions limited to functional languages (or perhaps limited to functional languages and the functional parts of mixed-impure functional languages) ?

This definition doesn't resolve some of my own naive questions about list comprehensions.

For example -- is a list comprehension a set of rules that can be used to show that a member doesn't belong to a list?

Or is it a piece of code that theoretically generates a list?

What sort of values is it limited to?

Can a list comprehension apply to something other than numbers? (I think there can... but i don't know)...

59.167.212.209 06:06, 26 March 2007 (UTC)LeonB[reply]

Thanks for your comments! A list comprehension denotes a list which is the result of the operations included in the comprehension on input lists. I would've expected the text to give the right idea, although it doesn't contain a definition. For exact definitions, you'll have to turn to the specification of each programming language. I tweaked the intro a bit, I hope it helps at least a little.

I would think we needn't explain that mathematical and programming language constructs can in general work on other types than numbers too, but perhaps someone can find a non-intrusive way to include this. Haskell and Python are the languages we know of, which already shows that list comprehensions are available for both functional and imperative languages like any other expression syntax. --TuukkaH 20:15, 26 March 2007 (UTC)[reply]

Thankyou TukkaH! This sentence here: "A list comprehension denotes a list which is the result of the operations included in the comprehension on input lists" Clears it up a bit for me. I quite like your edits! Thank you again! 203.52.70.253 03:32, 27 March 2007 (UTC)LeonB (different IP address today... but still me, i promise)[reply]

Although it is nice when a definition of a term does not repeat the term it is intended to define. Just a thought :) dr.ef.tymac 14:35, 27 March 2007 (UTC)[reply]

X squared

Some of the examples use x squared. Others use x*x. On a language-to-language comparison, this appears to give some languages a syntactic shortness advantage (see ERLANG versus C#). Should we unify the syntax in all languages to use one or the other?

Rbirkby 09:26, 5 June 2007 (UTC)[reply]

In an encyclopaedia, shouldn't clarity count? --Paddy (talk) 06:21, 12 July 2008 (UTC)[reply]

Is this really list comprehension?

Most of the examples seem to be showing list processing, not list comprehension like in Haskell... You could write a bunch of AppleSoft Basic to build a list, but that doesn't mean that AppleSoft has list comprehension as a language feature. Perhaps someone a bit more savvy in the feature could way in, but it seems to me that most of the examples in different languages should be deleted. Donald Hosek 20:32, 15 June 2007 (UTC)[reply]

Your basic point is a good one, but the problem is the applied terminology is sufficiently imprecise to warrant the current approach, which seems to be people adding in what they consider to be their programming language's "closest equivalent" ... this approach definitely has some warts, no doubt about it, but the warts are probably better treated by pointing them out in the article, rather than getting rid of the whole thing. It's actually useful to compare a basic operation in different languages that do not have the same evaluation strategy and semantics as Haskell.

Rather than taking out the examples, it seems the following is called for:

a clarifying footnote indicating the very point you make about Haskell vs other implementations;
a review of the examples to make sure they at least produce the result they claim to produce;
a few words at the top of the section "Forms of list comprehension" indicating that not all of these meet the "baseline definition" (assuming that such definition is derived from Haskell usage). dr.ef.tymac 14:06, 16 June 2007 (UTC)[reply]

I would agree, except the term "list comprehension" isn't imprecise. List comprehensions are syntactic sugar for building lists, using special, set-builder-like syntax. I've never heard the term used any other way. Query comprehensions and monad comprehensions aren't really list comprehensions, although they're worth mentioning. "Map" and "filter" don't qualify at all. Many of the examples are simply incorrect. I'm deleting the worst offenders. --Jorend 22:36, 30 November 2007 (UTC)[reply]

Less, in this case, is more. I agree with the edits Jorend :-) --Paddy 06:48, 1 December 2007 (UTC)[reply]

Bounded/unbounded

By "Forms of list comprehension", I wonder if Dreftymac was referring to the fact that The mathematical notation at the head of the article, and the Haskell example both show no upper bound, (except finite resources in Haskells case of course). In the examples shown only Haskell and Python give an unbounded version, (I cannot determine if the Visual Prolog example has a fixed upper bound). --Paddy 05:34, 2 September 2007 (UTC)[reply]

The term "list comprehension" refers to the set builder syntax; bounded/unbounded is an orthogonal concept. You don't need Haskell's lazy evaluation to have list comprehensions. -- 98.108.203.136 (talk) 03:27, 30 June 2008 (UTC)[reply]

(Don't) Need Perl6 Example

Perl 6 has more advanced capabilities, and is in fact very similar to Haskel in some respects. Someone who is current with it should add an example and discussion of lazy vs. finite list.

If Perl6 is not yet released , should an example be given? --Paddy 22:26, 18 July 2007 (UTC)[reply]

I will be deleting the Perl 6 example as Perl 6 is still in active development and an example here is premature/original research --Paddy 06:15, 8 November 2007 (UTC)[reply]

"S = [ 2*x | x<-[0..], x^2>3 ]" employs a needless exponent.

The current list example seems inelegant:

S = [ 2*x | x<-[0..], x^2>3 ]

If I understand correctly, it'd be this list of numbers:

{ 2,4,6,...}

The even numbers. It's puzzling why the list notation uses x^2>3 instead of x>1. Exponents aren't needed to describe even numbers. --AC 04:53, 7 September 2007 (UTC)[reply]

A mathematical definition of a set was given. Just because there's some other mathematical definition that yields the same set is irrelevant. -- 98.108.203.136 (talk) 03:33, 30 June 2008 (UTC)[reply]

x^2>3 is not really a good example of a filter since it only filters out x = 1, and inelegantly too. Why not use something like x congruent to y mod z? 83.248.95.93 (talk) 08:32, 7 September 2009 (UTC)[reply]

More people know he notation for square and greater than. It is a major section of the syntax, but the filter expression itself should be chosen to be easily understood and could be something else, but I don't think there is sufficient reason to change, as yet. --Paddy (talk) 17:46, 7 September 2009 (UTC)[reply]

concatMap

The languages which don't have list comprehensions should really be discussing their equivalents of concatMap and filter, rather than map and filter, because in the general case, these are the two things which list comprehensions desugar to. —Preceding unsigned comment added by 74.124.127.135 (talk) 21:53, 10 October 2007 (UTC)[reply]

Languages which don't have list comprehension and want to discuss their equivalents of map and filter can do so on the relevant pages Masklinn (talk) 13:42, 18 August 2010 (UTC)[reply]

Translation into list functions<- What is this about?

I an not a Haskel programmer, but have read several programming languages. I cannot see what this section in the article is about? I think it should be made more general or deleted if all it is is BNF for Haskels list comprehension syntax. --Paddy (talk) 12:22, 23 June 2008 (UTC)[reply]

I agree. This is an article about list comprehensions, not Haskell, and this esoteric section hurts rather than aids understanding, so I've removed it. If someone thinks it belongs in WP, add it to the Haskell page. -- 98.108.203.136 (talk) 03:41, 30 June 2008 (UTC)[reply]

Infinite lists and the introduction

Haskell seems to not create a list, but to just create something that will iterate over the members of what would be the list, thus allowing the use of unbounded ranges. The introduction seems to say that a list is produced which is not the same thing. Python uses two separate terms here, list comprehensions that create lists and so must be bounded in size, and generator comprehensions which yield successive members of what would be the list when iterated over. I can't think of a rewording of the opening paragraph at the moment, but intermediate lists are not necessarily generated.

If Haskell has no meaningful distinction between a list and the generator that creates list members then that could explain the opening paragraph, but I'm used to lists being of finite size --Paddy (talk) 12:22, 23 June 2008 (UTC)[reply]

That makes sense, you might want to check on the WP reference desks to see if there is a Haskell person who knows the specific distinction in terminology that they use. Generally, however, since the article should be accessible to a general audience, and this is not exclusively about Haskell, there's no reason why you shouldn't be able to use the intuitive distinction between lists and generators -- a distinction made in many languages, not just Python. dr.ef.tymac (talk) 16:04, 23 June 2008 (UTC)[reply]

From this Haskell reference it seems that infinite lists are described as just lists were you specify a pattern to generate successive members. The documentation still calls them lists. Other languages choose to use another name for this such as generator. --Paddy (talk) 16:50, 23 June 2008 (UTC)[reply]

This is about the difference between imperative and declarative programming. The sort of lazy evaluation found in Haskell allows one to blur the distinction, so that we can work with mathematical descriptions, which do not have the sorts of finite limits of the von Neumann model. -- 98.108.203.136 (talk) 03:50, 30 June 2008 (UTC)[reply]

Its a finite generator, of a sequence of members of an infinite list, which can be used where only a computable subset of the members of the list are needed. Haskell and other languages have this ability. --Paddy (talk) 18:34, 30 June 2008 (UTC)[reply]

Because list comprehensions are about syntax and similarities to set builder notation, i have changed the intro to better describe this syntax. --Paddy (talk) 18:34, 30 June 2008 (UTC)[reply]

Removal of non-LC examples

Unless someone can say why not, I am thinking of doing the following edits to remove non LC type syntax in the examples, including all the map+filter based examples as the page is about doing the task using LC's rather than equivalent code for doing the task:

Remove section "Translation into list functions"
Haskell: remove all but multiple generator LC example
Perl: remove map example
In the section "Parallel list comprehension", leeave only the first paragraph up to, but not including the first example.

--Paddy (talk) 15:13, 24 June 2008 (UTC)[reply]

More importantly, I think we need a better LC explanation here. It seems that the difference between LC and map+filter is not that obvious. Instead of removing examples (that technically might not be LC, but have pretty similar syntax), I suggest moving them to a new 'equivalent syntax in other languages' section (or something like that) and explaining why the alternative syntax is not LC. Ghettoblaster (talk) 16:56, 24 June 2008 (UTC)[reply]

Hi Ghettoblaster, I think the distinction between LC and map+filter has now been made, and highlighting the true LC examples should also make it clear. I am against leaving a section for map+filter examples as those should be on a different page. I am however thinking of expanding on LC syntax. --Paddy (talk) 09:52, 30 June 2008 (UTC)[reply]

FYI, before reading this, I removed that horrible Haskell-specific and esoteric "Translation into list functions" section. I also fixed the two bugs in the perl example, FWIW. -- 98.108.203.136 (talk) 03:56, 30 June 2008 (UTC)[reply]

Main Example is in Overview

Could the Erlang example be changed to follow the Haskel example in the overview section, then all language examples will do similar things. and be related to the set builder notation expression. --Paddy (talk) 16:23, 22 August 2008 (UTC)[reply]

I will be chopping the examples in different programming languages so that only versions of the example set builder notation analogue in haskel are shown. Please stick to versions of this for clarity. --Paddy (talk) 05:20, 26 November 2008 (UTC)[reply]

PostScript Reference

Why is PostScript referenced in the references section? I don't see it mentioned in the text. Does PostScript have some feature relevant to list comprehensions? —Preceding unsigned comment added by Ezrakilty (talk • contribs) 12:52, 9 February 2009 (UTC)[reply]

Linq example needed

If Linq does follow set builder syntax, then it would be good if their were Linq examples added to the C# section that implemented the standard examples; then the current Linq info could be removed from the 'Similar constructs' section. --Paddy (talk) 09:46, 26 September 2009 (UTC)[reply]

SQL, SPARQL,...?

The first thing that comes to my mind when thinking of th este notation in mathematics is SQL and even more so SPARQL. Am I missing something subtle but deciding or should these both prominently mentioned here? Hixxxxx (talk) 11:10, 16 March 2011 (UTC)[reply]

SQL statements are indeed examples of list comprehensions. I see that SQL is mentioned briefly. I think it would be reasonable to give a longer example as is done with the fuller programming languages. I can't speak to SPARQL but perhaps it falls in that category too. — Preceding unsigned comment added by Ezrakilty (talk • contribs) 13:19, 16 March 2011 (UTC)[reply]

Smalltalk and programming bias

I am waiting for someone to say that Smalltalk-80 select: is a filter and that the collect: message is not an LC. What else could explain this very biased "history" of LC in programming languages? Is this about a name for a formal function/mapping/transform or a practice as implemented in the programming languages of an applied science? If you have doubts, see the minimalist changes to Smalltalk in Seaside that take blocks to continuations and then quote "Smalltalk does not have continuations." But in practice Smalltalk is a programming environment, not a language definition. For a useful comparison, look at the impact of genome studies on the previous hierarchies in botany where one standpoint if forced to give way to another (and, yes, I recognize the irony.)

I soon expect to seen an article in which Traits are "shown" in the History section to have come from Scala. G. Robert Shiplett 17:23, 8 June 2011 (UTC) — Preceding unsigned comment added by Grshiplett (talk • contribs)

Too complicated

I consider myself a pretty seasoned programmer in various programming languages and environments, but I had no idea what a "List comprehension" is, and after reading this article, I have no idea anymore what ANYTHING is.

Could at least the introductory section explain this with real-world examples in a SLIGHTLY simpler manner? — Preceding unsigned comment added by 82.139.196.68 (talk) 21:37, 25 December 2011 (UTC)[reply]

So if the following were taken word-by-word, could you explain where the problem lies:

A list comprehension is a syntactic construct available in some programming languages for creating a list based on existing lists. It follows the form of the mathematical set-builder notation (set comprehension) as distinct from the use of map and filter functions.

--Paddy (talk) 10:25, 30 December 2011 (UTC)[reply]

Is the Mathematica version correct?

Correct me if I'm wrong, I don't have Mathematica and knows very little about the language, but from cursory examination of the code, the Mathematica version seems to be doing something different than the rest of the examples. The examples are supposed to produce the equivalent of s = [ 2*x | x <- [0..100], x^2 > 3 ] but it seems the Mathematica version are doing something like s = [ x | x <- [0..100], x^2 > 3 ]. In other words, I don't see the multiplication by 2 anywhere in the Mathematica version. — Preceding unsigned comment added by 110.175.240.90 (talk) 15:04, 30 January 2012 (UTC)[reply]

Also, per the thread Removal of non-LC examples, map+filter is a distinct concept from LC, and as far as I can tell, Mathematica's Select is a filter. If Mathematica doesn't have a true LC, then it should fall under the criteria for removal.