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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Генераторні списки (англ. 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 досяг ширшого прийняття і представив генераторні списки ширшій аудиторії.

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

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

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

Хоча в оригінальному прикладі використовується нескінченний список, виразити його можуть не всі мови, тому в деяких ми покажемо як використати підмножину \{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 ]



Дивись також[ред.ред. код]

Посилання[ред.ред. код]

Haskell[ред.ред. код]

OCaml[ред.ред. код]

Python[ред.ред. код]

Common Lisp[ред.ред. код]

Clojure[ред.ред. код]

Axiom[ред.ред. код]

Решта[ред.ред. код]