Talk:List comprehension

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)

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? — Preceding unsigned comment added by Bogdanb (talk • contribs) 00:25, 2006 August 28 (UTC)

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)

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)

---

I have not been able to find any mention of "list comprehensions" or "set comprehensions" by Darlington in relation to either SETL or NPL. However, in his retrospective "Some History of Functional ProgrammingLanguages", David Turner (designer of SASL, KRC, and Miranda) claims that

NPL was implemented in POP2 by Burstall and used for Darlington’s work on program transformation (Burstall & Darlington 1977). The language was first order, strongly (but not polymorphically) typed, purely functional, call-by-value. It also had “set expressions” e.g.

setofeven (X)  <=  <:x : x in X & even(x):>}}

In a footnote attached to the term "list comprehension" he also notes

I initially called these ZF expressions, a reference to Zermelo-Frankel set theory — it was Phil Wadler who coined the better term list comprehension."

I have been able to find use of the term 'set expressions' by Darlington in contexts that might be relevant, e.g. his 1972 thesis.

Unless someone can turn up better references that prove otherwise, I would like to update the history section to incorporate Turner's account (and actually include citations as evidence). I think including reference to the term "ZF expressions" is valuable in its own right, as this term seems to show up a lot in the literature in the 80s, and it's a valuable historical note connecting list comprehensions to set-builder notation.

I'll give it some time before I try to make the change, so please speak up if you have any reservations or think I am in error! Synechist (talk) 00:23, 27 December 2019 (UTC)

Forms of List Comprehension

"Certain lists are too complex to express by other means." -- An example would be nice. — Preceding unsigned comment added by 38.119.128.203 (talk) 21:30, 2006 August 31 (UTC)

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)

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

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

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)

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)

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)

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)

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

More jargon for interview time ?

I am equally lost in trying to understand the difference between "List Comprehension" and a function (or lambda function). It seems to me that almost every example language (almost only because a few look so alien that I can't comment) does not show *native* support for list comprehension. Rather, the examples show how to perform "List Comprehension" with the language's existing (non-native comprehension) syntax. A particularly good example of this is the C# example. That's just a query against a set with some operation on the elements which satisfy the query.

If I create a function which generates a randomly dimensioned matrix of unordered numbers which *do not* obey a predicate, can I call that a "syntactic construct" and give it a weird name like "Matrix Evolution" and base my PhD thesis upon it ? — Preceding unsigned comment added by SmigersSmigers (talk • contribs) 08:59, 2015 August 28 (UTC)

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)

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)

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)

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

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)

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)

(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. — Preceding unsigned comment added by D ugosz (talk • contribs) 18:41, 2007 July 17 (UTC)

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

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)

"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)

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)

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)

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)

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)

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)

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)

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)

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)

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)

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)

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)

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)

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)

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:

1. Remove section "Translation into list functions"
2. Haskell: remove all but multiple generator LC example
3. Perl: remove map example
4. 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)

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)

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)

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)

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)

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)

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)

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)

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)

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)

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)

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)

I'll bite: The first sentence, as pointed out by a previous commenter, categorises the concept rather than describing it - in plain English, it says little more than "it's a way of getting a list from another list". The second sentence doesn't really describe it either, instead giving an analogy to an even more abstract concept (set-builder notation) and a contrast to a couple of different ways of getting a list from another list (map and filter - those articles, incidentally, have very clear leading sentences, IMHO).

What it doesn't explain is: How does a list comprehension generate a new list? What are its fundamental properties? How does it differ from map() and filter(), other than in syntax?

I can sort of see what the "overview" is trying to get at, but it feels more like "background theory" - sure, in pure maths you don't generate a set you just describe it, but how does that apply to programming with lists? When you get to the list of fundamental components, it seems like it's just a special (and rather ugly) way of writing map(output_expression, filter(predicate, input_list)), but I'm sure that's missing the point in some way.

What the article needs is some description of why, given a functional programming language, you would ever want this peculiar notation.

A better definition up front might also go hand in hand with a clearer decision on which languages can actually be said to support it. At the moment, there are lots of examples "emulating" it with map() and filter() implementations, which seems to completely contradict the "in contrast to" in that second sentence. - IMSoP (talk) 22:38, 21 January 2014 (UTC)

If anyone happens to see this, I'd like to note that none of the edits in the nearly 5 years since my last comment has improved the introduction. This article still doesn't explain what the point of this syntax is, other than to make pure mathematicians happy. - IMSoP (talk) 15:20, 29 October 2018 (UTC)

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)

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. — Preceding unsigned comment added by 110.175.240.90 (talk) 15:12, 30 January 2012 (UTC)

+1. Removed. _R_ (talk) 16:23, 29 March 2012 (UTC)

Remove "Parallel list comprehension" as it is a property of zip?

I am thinking of removing the section on "Parallel list comprehension" tomorrow as this is a property of zip() pairing the items in two lists more than adding much to list comprehensions. --Paddy (talk) 05:53, 16 June 2012 (UTC)

Example of how it must be syntactical / language construct

If I understand correctly, it must be some feature built into the language itself, with it's own syntactical form, and not just a function doing the same, even if that function is very compact and elegant. Fx Python list comprehension and the Python map function. If think there should be a small subsection describing how the definition (normally? / always?) only applies to language constructs, not to a function, and then two examples of achieving the same (fx Python list comprehension and map-function), stating that the former is indeed list comprehension, while the latter by definition is not. MadsSkjern (talk) 07:07, 24 May 2015 (UTC)

External links modified

Hello fellow Wikipedians,

I have just modified 3 external links on List comprehension. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

• Added archive https://web.archive.org/web/20111008001258/http://w3schools.com/xquery/xquery_flwor.asp to http://www.w3schools.com/XQuery/xquery_flwor.asp
• Added archive https://web.archive.org/web/20051129140339/http://www.haskell.org/ghc/docs/latest/html/users_guide/syntax-extns.html to http://www.haskell.org/ghc/docs/latest/html/users_guide/syntax-extns.html
• Added archive https://web.archive.org/web/20051018040438/http://page.axiom-developer.org/zope/mathaction/Streams to http://page.axiom-developer.org/zope/mathaction/Streams

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 18 January 2022).

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 04:20, 24 December 2017 (UTC)

Let's remove the C++ quasi implementation?

Nearly half of the current article is devoted to tangential notes on how you can get something kind of like list comprehensions in C++. I don't see the relevance for the core concept. It seems clear to me that this material instead belongs on Comparison_of_programming_languages_(list_comprehension). Does anyone object to me making that change? -- Synechist (talk) 16:15, 27 February 2022 (UTC)