Lijstcomprehensie

In programmeertalen is sequentie-besef of lijstcomprehensie een syntactische constructie om een lijst te noteren. Het is gebaseerd op wiskundige notatie voor verzamelingen. Een lijstcomprehensie is syntactische suiker aangezien hetzelfde ook bereikt kan worden met andere taalconstructies, zoals de hogere-ordefuncties map en filter. Enkele programmeertalen waarin men sequentie-besef kan gebruiken zijn Python en Haskell.

Overzicht

In de wiskunde is het mogelijk een verzameling als volgt te noteren:

$S=\{\,2\cdot x\mid x\in \mathbb {N} ,\ x^{2}>10\,\}$

Dit kan worden gelezen als: "S is de verzameling van alle '2 maal x', waarvoor geldt dat x een element is van de verzameling natuurlijke getallen en dat x in het kwadraat groter is dan 10".

Deze notatie bevat de volgende onderdelen:

• $2\cdot x$: een functie die toegepast wordt op elk van de elementen.
• $x$: een variabele die gebruikt wordt om de elementen van de verzameling $\mathbb {N}$ te benoemen.
• $\mathbb {N}$: een verzameling die dient als invoer; hieruit worden de elementen gehaald die in de genoteerde verzameling terecht kunnen komen (mits het predicaat waar is).
• $x^{2}>10$: een predicaat dat moet gelden voor de elementen die in de verzameling komen (hiermee worden elementen uit de invoerverzameling gefilterd).

Voorbeeld

In de functionele programmeertaal Haskell kan het bovenstaande geschreven worden als:

[ 2 * x | x <- [0..], x * x > 10 ]

Hierin staat [0..] voor de lijst natuurlijke getallen. Het gedeelte x <- [0..] wordt een generator genoemd.

De bovenstaande lijstcomprehensie kan ook als volgt genoteerd worden:

map (\x -> 2 * x) (filter (\x -> x * x > 10) [0..])

Het is ook mogelijk meerdere generatoren en meerdere predicaten te gebruiken, zoals:

[ (x, y) | x <- [1..10], x `rem` 3 == 0, y <- [1..10], x + y == 7 ]

Syntactische suiker

Lijstcomprehensie is een vorm van syntactische suiker aangezien dit concept ook uitgedrukt kan worden in bestaande taalconstructies. Voor de programmeertaal Haskell beschrijft het Haskell 98 Report een systematische manier om lijstcomprehensies om te schrijven naar bestaande taalconstructies, zoals let ... in ... en if ... then ... else ....

Zo wordt [ x | x <- [0..], x `rem` 2 == 0 ] bijvoorbeeld omgeschreven naar:

let ok x = if x `rem` 2 == 0 then [x] else []
    ok _ = []
in concatMap ok [0..]

Hierin is rem een functie die de rest (Engels: remainder) van een deling oplevert. De functie concatMap ok [0..] is hetzelfde als concat (map ok [0..]), waarbij map de functie map is en concat is concatenatie van een lijst.

Bronnen, noten en/of referenties