Спискові вирази

Генераторні списки (англ. list comprehension) - синтаксична конструкція доступна в деяких мовах програмування, яка призначена для створення списків застосуванням операцій над існуючими списками. Вона відповідає математичній формі запису множин, і замінює використання функцій map та filter.

Опис

Розгляньмо наступний приклад запису множини:

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

Це можна прочитати як, "$S$ множина всіх чисел виду "2 на $x$", де $x$ - елемент з множини натуральних чисел ($\mathbb{N}$), такий що $x$ в квадраті більше ніж $3$."

В мові Haskell такий запис множини можна відтворити генераторним списком такого вигляду:

s = [ 2*x | x <- [1..], x^2 > 3 ]

Тут список [1..] представляє $\mathbb{N}$, x^2>3 представляє предикат, а 2*x - вихідний вираз.

Генераторні списки дають результати в означеному порядку (на відміну від членів множини); і генераторні списки можуть генерувати елементи за потребою, а не одразу ввесь список, дозволяючи таким чином, наприклад попереднє означення членів нескінченної множини.

Історія

Мова програмування SETL (кінець 1960-тих) мала інструкції конструюванння множин, і система комп'ютерної алгебри AXIOM (1973) мала подібні конструкції які обробляли потоки, але вперше термін "comprehension" для таких конструкцій був використаний Родом Бурсталом та Джоном Дарлінґтоном в описі мови програмування NPL (1977).

Smalltalk block context messages які являють собою генераторні списки були в цій мові щонайменше з часів Smalltalk-80.

Робота Бурстала та Дарглінґтона з NPL здійснила вплив на багато мов програмування протягом 1980-тих, але не всі з них включали генераторні списки. Виключенням була впливова лінива чисто функціональна мова програмування Miranda, яка була випущена в 1985-тому. Розроблена опісля, теж цілком функціональна мова з лінивими обчисленнями Haskell, ввібрала багато особливостей Міранди, включно з генераторними списками. Мова програмування Python теж піддалась сильному впливу лінивих функціональних мов, і ввела генераторні списки. Чисті функціональні мови залишаються нішевими, в той час як Python досяг ширшого прийняття і представив генераторні списки ширшій аудиторії.

Генераторні списки пропонувалиьс як нотація запитів до баз даних і були реалізовані в мові запитів Kleisli.

Приклади в різних мовах програмування

Далі йтимуть приклади синтаксису генераторних списків в різних мовах програмування:

Хоча в оригінальному прикладі використовується нескінченний список, виразити його можуть не всі мови, тому в деяких ми покажемо як використати підмножину $\{0, 1, ..., 100\}$ замість підмножини $\mathbb{N}$.

Clojure

Clojure генерує нескінченні ліниві послідовності (подібно до Хаскеля, чи генераторів Пайтона). Використовуйте take щоб отримати перші N результатів нескінченної послідовності.

(take 20 (for [x (iterate inc 0) :when (> (* x x) 3)] (* 2 x)))

Common Lisp

Генераторні списки можуть виражатись за допомогою ключового слова collect макроса loop. Умови виражаються за допомогою if, як показано нижче:

(loop for x from 0 to 100 if (> (* x x) 3) collect (* 2 x))

Нескінченна лінива послідовність може створюватись різними способами, наприкладч за допомогою об'єктів CLOS чи макросом yield.

Erlang

Подібний приклад на Erlang:

 S = [2*X || X <- lists:seq(0,100), X*X > 3].

F#

Генератори мають форму [for x in collection do ... yield expr] для списків та seq {for x in collection do ... yield expr} для послідовностей.

Наприклад:

> seq { for x in 0..100 do
          if x*x > 3 then yield 2*x } ;;
val it : seq<int> = seq [4; 6; 8; 10; ...]

Haskell

Приклад давався на початку статті:

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

Дивись також

• Оператор SELECT в SQL
• Монади
• Інші конструкції для обробки послідовностей:
  • Генератор (програмування)
  • Map (функція вищого порядку)
• Інші конструкції програмування, перенесені з математичних форм запису:
  • Варта
  • Зіставлення зі зразком
  • Оператор (програмування)

Посилання

• List Comprehension in The Free On-line Dictionary of Computing, Editor Denis Howe.
• Trinder, Phil(1992). "Comprehensions, a query notation for DBPLs". Proceedings of the third international workshop on Database programming languages: bulk types & persistent data, Nafplion, Greece, 55–68.
• Wadler, Philip(1990). "Comprehending Monads". Proceedings of the 1990 ACM Conference on LISP and Functional Programming, Nice.
• Wong, Limsoon(2000). "The Functional Guts of the Kleisli Query System". Proceedings of the fifth ACM SIGPLAN international conference on Functional programming, 1–10.

Haskell

• The Haskell 98 Report, chapter 3.11 List Comprehensions.
• The Glorious Glasgow Haskell Compilation System User's Guide, chapter 7.3.4 Parallel List Comprehensions.
• The Hugs 98 User's Guide, chapter 5.1.2 Parallel list comprehensions (a.k.a. zip-comprehensions).

OCaml

• OCaml Batteries Included
• Language extensions introduced in OCaml Batteries Included

Python

• Python Reference Manual, chapter 5.2.4 List displays.
• Python Enhancement Proposal PEP 202: List Comprehensions.
• Python Reference Manual, chapter 5.2.5 Generator expressions.
• Python Enhancement Proposal PEP 289: Generator Expressions.

Common Lisp

• Implementation of a Lisp comprehension macro by Guy Lapalme

Clojure

• Clojure API documentation - for macro

Axiom

• Axiom stream examples

Решта

• SQL-подібні оператори над множинами в Python Cookbook (англ.)
• Обговорення генераторних списків та пов'язаних конструкцій в Scheme (англ.)
• Генераторні списки в різних мовах програмування (англ.)