In computer science, the syntax of a programming language is the set of rules that define the combinations of symbols that are considered to be syntactically correct computer programs in that language.... construct available in some programming language
Programming language
A programming language is a machine-readable artificial language designed to express computations that can be performed by a machine, particularly a computer.... s for creating a list based on existing lists. It follows the form of the mathematical set-builder notation
Set-builder notation
In set theory and its applications to logic, mathematics, and computer science, set-builder notation is a mathematical notation for describing a Set by stating the properties that its members must satisfy.... (set comprehension.) as distinct from the use of map
Map (higher-order function)
In many programming languages, map is the name of a higher-order function that applies a Procedural parameter to a sequence of elements and returns a sequence of results.... and filter
Filter (higher-order function)
In functional programming, filter is a higher-order function that processes a data structure in some order to produce a new data structure containing exactly those elements of the original data structure for which a given predicate returns the boolean value true.... functions.
can be read, "S is the set of all 2 times x where x is an item in the set of natural numbers, for which x squared is greater than 3."
In this annotated version of the example:
A list comprehension has the same syntactic components to represent generation of a list in order from an input list
List (computing)
In computer science, a list is an ordered Multiset of entity/items.In the context of object-oriented programming languages, a list is defined as an instance of an abstract data type , formalizing the concept of an order theoryed Collection class of entity.... or iterator
Iterator
In computer science, an iterator is an object that allows a programmer to traverse through all the elements of a Collection , regardless of its specific implementation.... :
The order of generation of members of the output list is based on the order of items in the input.
Haskell is a standardized, purely functional programming language with non-strict programming language, named after logician Haskell Curry. The goals of the language are described as:... 's list comprehension syntax, this set-builder construct would be written similarly, as:
s = [ 2*x | x <- [0..], x^2 > 3 ]
Here, the list [0..] represents , x^2>3 represents the predicate, and 2*x represents the output expression.
List comprehensions give results in a defined order, (unlike the members of sets); and list comprehensions may generate
Generator (computer science)
In computer science, a generator is a special subroutine that can be used to control the iteration behaviour of a control flow#Loops. A generator is very similar to a function that returns an array, in that a generator has parameters, can be called, and generates a sequence of values.... the members of a list in order, rather than produce the entirety of the list thus allowing, for example, the previous Haskell definition of the members of an infinite list.
the first use of the term "comprehension" for such constructs was in Rod Burstall and John Darlington's description of their programming language NPL
NPL programming language
NPL was a functional language with pattern matching designed by Rod Burstall and John Darlington in 1977. The language allowed certain sets and logic constructs to appear on the right hand side of definitions, E.g.... from 1977.
Comprehensions were proposed as a query notation for databases and were implemented in the Kleisli database query language.
following provides a few examples of specific syntax used in programming languages.
In computer science, the syntax of a programming language is the set of rules that define the combinations of symbols that are considered to be syntactically correct computer programs in that language.... construct available in some programming language
Programming language
A programming language is a machine-readable artificial language designed to express computations that can be performed by a machine, particularly a computer.... s for creating a list based on existing lists. It follows the form of the mathematical set-builder notation
Set-builder notation
In set theory and its applications to logic, mathematics, and computer science, set-builder notation is a mathematical notation for describing a Set by stating the properties that its members must satisfy.... (set comprehension.) as distinct from the use of map
Map (higher-order function)
In many programming languages, map is the name of a higher-order function that applies a Procedural parameter to a sequence of elements and returns a sequence of results.... and filter
Filter (higher-order function)
In functional programming, filter is a higher-order function that processes a data structure in some order to produce a new data structure containing exactly those elements of the original data structure for which a given predicate returns the boolean value true.... functions.
Overview
Consider the following example in set builder notation.
This can be read, "S is the set of all 2 times x where x is an item in the set of natural numbers, for which x squared is greater than 3."
In this annotated version of the example:
is the variable representing members of an input set.
represents the input set, which in this example is the set of natural numbers
Sometimes it is inconvenient or impossible to describe a set by listing all of its elements. Another useful way to define a set is by specifying a property that the elements of the set have in common.... function acting as a filter on members of the input set.
is an output function producing members of the new set from members of the input set that satisfy the predicate function.
brackets contain the expression
the vertical bar and the comma are separators.
A list comprehension has the same syntactic components to represent generation of a list in order from an input list
List (computing)
In computer science, a list is an ordered Multiset of entity/items.In the context of object-oriented programming languages, a list is defined as an instance of an abstract data type , formalizing the concept of an order theoryed Collection class of entity.... or iterator
Iterator
In computer science, an iterator is an object that allows a programmer to traverse through all the elements of a Collection , regardless of its specific implementation.... :
A variable representing members of an input list.
An input list (or iterator).
An optional predicate expression.
And an output expression producing members of the output list from members of the input iterable that satisfy the predicate.
The order of generation of members of the output list is based on the order of items in the input.
Haskell is a standardized, purely functional programming language with non-strict programming language, named after logician Haskell Curry. The goals of the language are described as:... 's list comprehension syntax, this set-builder construct would be written similarly, as:
s = [ 2*x | x <- [0..], x^2 > 3 ]
Here, the list [0..] represents , x^2>3 represents the predicate, and 2*x represents the output expression.
List comprehensions give results in a defined order, (unlike the members of sets); and list comprehensions may generate
Generator (computer science)
In computer science, a generator is a special subroutine that can be used to control the iteration behaviour of a control flow#Loops. A generator is very similar to a function that returns an array, in that a generator has parameters, can be called, and generates a sequence of values.... the members of a list in order, rather than produce the entirety of the list thus allowing, for example, the previous Haskell definition of the members of an infinite list.
History
The SETL programming language (later 1960's) had a set formation construct, and the computer algebra system
Computer algebra system
A computer algebra system is a Application software that facilitates symbolic mathematics. The core functionality of a CAS is manipulation of mathematical expressions in symbolic form.... AXIOM
Axiom
In traditional logic, an axiom or postulate is a proposition that is not proved or demonstrated but considered to be either self-evidence, or subject to necessary decision.... (1973) has a similar construct that processes streams,
but the first use of the term "comprehension" for such constructs was in Rod Burstall and John Darlington's description of their programming language NPL
NPL programming language
NPL was a functional language with pattern matching designed by Rod Burstall and John Darlington in 1977. The language allowed certain sets and logic constructs to appear on the right hand side of definitions, E.g.... from 1977.
Comprehensions were proposed as a query notation for databases and were implemented in the Kleisli database query language.
Examples in different programming languages
The following provides a few examples of specific syntax used in programming languages. For a more comprehensive comparison, please see the main article in the Programming language comparison
Comparison of programming languages (enumeration)
List Comprehensions List comprehension is a Syntax of programming languages construct available in some programming languages for creating a list based on existing lists.... series.
Although the original example denotes an infinite list, few languages can express that, so in some of those cases we show how to take a subset of rather than a subset of .
A list comprehension is a Syntax of programming languages construct available in some programming languages for creating a list based on existing lists.... ).
Erlang
The same example in Erlang:
S = [2*X || X <- lists:seq(0,100), X*X > 3].
Python is a general-purpose high-level programming language. Its design philosophy emphasizes code readability. Python's core syntax and semantics are Minimalism , while the standard library is large and comprehensive.... has a corresponding syntax for expressing list comprehensions.
The near-equivalent in Python to the example above is as follows:
S = [2*x for x in range(101) if x**2 > 3]
A generator expression may be used in Python 2.4 to achieve functional equivalence with S using a generator
Generator (computer science)
In computer science, a generator is a special subroutine that can be used to control the iteration behaviour of a control flow#Loops. A generator is very similar to a function that returns an array, in that a generator has parameters, can be called, and generates a sequence of values.... to iterate an infinite list:
from itertools import count
S = (2*x for x in count if x**2 > 3)
Scala
Using the for-comprehension:
val s = for (x <- Stream.from(0); if x*x > 3) yield 2*x
F#
The F# generator comprehension has the list comprehension syntax elements.
Generator comprehensions can be used to generate Lists, Sequences (like lists but evaluated on-demand) and Arrays (not discussed here).
Generators are of the form [for x in collection do ... yield expr] for lists and seq for sequences.
For example:
(* Int32.MaxValue used to indicate "infinite" *)
> seq ;;
val it : seq = seq [4; 6; 8; 10; ...]
OCaml
OCaml Batteries Included has uniform comprehension syntax for lists, arrays, enumerations (like streams), lazy lists (like lists but evaluated on-demand), sets, hashtables, etc.
Comprehension are of the form
[? expression | x <- enumeration ; condition; condition ; ...]
For instance,
[? 2 * x | x <- 0 -- max_int ; x * x > 3];;
- : int Enum.t =
or, to compute a list,
[? List: 2 * x | x <- 0 -- 100 ; x * x > 3];;
- : int list = [2; 4; 6; 8; 10]
or, to compute a set,
[? PSet: 2 * x | x <- 0 -- 100 ; x * x > 3];;
- : int PSet.t =
etc.
XQuery and XPath
Like the original NPL use, these are fundamentally database access languages.
This makes the comprehension concept more important, because it is computationally infeasible to retrieve the entire list and operate on it (the initial 'entire list' may be an entire XML database).
is conceptually evaluated as a series of "steps" where each step produces a list and the next step applies a filter function to each element in the previous step's output. See: http://www.w3.org/TR/xpath#section-Location-Steps.
In XQuery, full XPath is available, but FLWOR statements are also used, which is a more powerful comprehension construct. See http://www.w3schools.com/XQuery/xquery_flwor.asp.
for $b in //book
where $b[@pages < 400]
order by $b//title
return
Here the XPath //book is evaluated to create a sequence (aka list); the where clause is a functional "filter", the order by sorts the result, and the ... XML snippet is actually an anonymous function that builds/transforms XML for each element in the sequence using the 'map' approach found in other functional languages.
So, in another functional language the above FLWOR statement may be implemented like this:
The infinite set of natural numbers can be made available as a static property with a getter:
public static IEnumerable Naturals
Then the set can be defined by a comprehension:
var s = from x in Naturals where x*x > 3 select x*2;
Latest .NET 3.5 Framework has Enumerable.Range method which allows to write like this:
var s = from x in Enumerable.Range(0, int.MaxValue) where x*x > 3 select x*2;
or equivalent code through chain methods:
var s = Enumerable.Range(0, int.MaxValue).Where(x => x*x > 3).Select(x => x*2);
In functional programming, a monad is a kind of abstract data type used to represent computations . Programs written in functional style can make use of monads to structure procedures that include sequenced operations, or to define arbitrary control flows .... is a generalization of the list comprehension to other monads in functional programming
Monads in functional programming
In functional programming, a monad is a kind of abstract data type used to represent computations . Programs written in functional style can make use of monads to structure procedures that include sequenced operations, or to define arbitrary control flows .... .
Set comprehension
Version 3 of the Python language introduces syntax for set comprehensions. Similar in form to list comprehensions, set comprehensions generate Python sets instead of lists.
>>> s =
>>> print(s)
>>> type(s)
>>>
Dict comprehension
Version 3 of the Python language introduces syntax for dictionary comprehensions. Similar in form to list comprehensions, dictionary comprehensions generate Python dictionaries instead of lists.
>>> d =
>>> print(d)
>>> type(d)
>>>
The Glorious Glasgow Haskell Compilation System, more commonly known as the Glasgow Haskell Compiler or GHC, is an open source Machine language compiler for the functional programming Computer programming Programming language Haskell .... has an extension called parallel list comprehension (also known as zip-comprehension) that permits multiple independent branches of qualifiers within the list comprehension syntax.
Whereas qualifiers separated by commas are dependent, qualifier branches separated by pipes are evaluated in parallel.
See also
Cf. the SELECT statement together with its FROM and WHERE clauses in SQL
SQL
SQL is a database computer language designed for the retrieval and management of data in relational database management systems , database schema creation and modification, and database object access control management.... .
A programming language is a machine-readable artificial language designed to express computations that can be performed by a machine, particularly a computer....
A mathematical notation is a system of symbolic representations of mathematical objects and ideas. Mathematical notations are used in mathematics and the physical sciences, engineering and economics....
In functional programming, a monad is a kind of abstract data type used to represent computations . Programs written in functional style can make use of monads to structure procedures that include sequenced operations, or to define arbitrary control flows .... for monads and monadic notation in general
For other programming language constructs used to process sequences:
In computer science, a generator is a special subroutine that can be used to control the iteration behaviour of a control flow#Loops. A generator is very similar to a function that returns an array, in that a generator has parameters, can be called, and generates a sequence of values....
In many programming languages, map is the name of a higher-order function that applies a Procedural parameter to a sequence of elements and returns a sequence of results....
For other programming language constructs copied from the mathematical notation:
In computer programming, a guard is a Boolean datatype expression that must evaluate to true if the program execution is to continue in the branch in question....
In computer science, pattern matching is the act of checking for the presence of the constituents of a given pattern. In contrast to pattern recognition, the pattern is rigidly specified....
Programming languages generally support a set of operators that are similar to operator. A language may contain a fixed number of built-in operators or it may allow the creation of programmer-defined operators ....
External links
SQL-like set operations with list comprehension one-liners in the
