Списковое включение

Поделись знанием:
(перенаправлено с «ZF-выражение»)
Перейти к: навигация, поиск

Абстракция списков или списковое включение (англ. list comprehension, нем. Erfassung der Liste[1]) в синтаксисе некоторых языков программирования — это способ компактного описания операций обработки списков[2].

Списковое включение позволяет вычислять и бесконечные списки (в языках, которые их поддерживают). Например, на языке Миранда бесконечный список чётных положительных чисел можно записать следующим образом[2]:

 [ n | n <- [1..]; n rem 2 = 0 ]

что читается так: «список всех n, таких что n входит в [1..] и остаток от деления n на 2 равен нулю».

По аналогии со списковыми включениями, в других языках программирования есть выражения битовых строк (Erlang), включения списков и словарей (Python в версии 3).





Терминология

В переводе книги Филда и Харрисона «Функциональное программирование»[2] вводится термин «абстракция списков» и «включение списков». Тем не менее, в литературе используются также «списковое выражение», «выделение списка»[3], «списочное встраивание»[4][5], «генератор списка» (возможно, не очень удачный перевод, так как в функциональном программировании есть отдельное понятие для генератора списка, англ. list generator[6])[7], «определитель списка»[8].

В аксиоматике теории множеств Цермело-Френкеля есть аксиома выделения, которая позволяет строить множество на основе имеющегося, путём выбора элементов, соответствующих некоторому предикату. Абстракция списков является аналогией выделения для списков[9] и иногда можно даже встретить термин ZF-выражение[10].

Примеры из различных языков программирования

Python

Чётные числа от 2 до 9998 включительно:

[n for n in range(1, 10000) if n % 2 == 0]

Списковые включения могут использовать вложенные итерации по переменным:

[(x, y) for x in range(1, 10) for y in range(1, 10) if x % y == 0]

В языке Python есть и выражения-генераторы, которые имеют схожий со списковыми включениями синтаксис, но возвращают итератор[11]. Сумма чётных чисел из предыдущего примера:

sum((n for n in range(1, 10000) if n % 2 == 0))

В данном случае дополнительные скобки не нужны, но в общем случае их отсутствие вызовет синтаксическую ошибку.

Как уже говорилось выше, Python предоставляет аналогичные возможности для создания множеств и словарей.

>>> {x for x in range(10)}
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
>>> {x:x**2 for x in range(10)}
{0: 0, 1: 1, 2: 4, 3: 9, 4: 16, 5: 25, 6: 36, 7: 49, 8: 64, 9: 81}

Erlang

В Erlang генератор списка будет выглядеть следующим образом:

[ N || N <- [1, 2, 3, 4, 5, 6], N rem 2 == 0 ].

Haskell

Пример с чётными числами на Haskell[9]:

[x | x <- [1..], x `mod` 2 == 0] -- бесконечный список: [2,4,6,8,10..]

В Haskell выражение вида x <- выр называется генератором. В одном выделении может быть несколько генераторов:

[(x, y) | x <- [1..4], y <- [1..4], x `mod` y == 0] -- 8 уникальных пар: [(1,1),(2,1),(2,2),(3,1),(3,3),(4,1),(4,2),(4,4)]

LINQ в C#

LINQ для C# 3.0 имеет несколько сходных со списковыми включениями синтаксических конструкций для запросных выражений[12]:

var s = Enumerable.Range(0, 100).Where(x => x*x > 3).Select(x => x*2);

Альтернативный синтаксис, напоминающий SQL:

var s = from x in Enumerable.Range(0, 100) where x*x > 3 select x*2;

Напишите отзыв о статье "Списковое включение"

Примечания

  1. Душкин, 2007, с. 594.
  2. 1 2 3 Филд, Харрисон, 1993, с. 93-94.
  3. [www.ibm.com/developerworks/ru/library/l-haskell3/ Алексей Бешенов. Функциональное программирование на Haskell : Часть 4. Свертки списков, IBM]
  4. [citforum.ru/programming/python/python9.shtml И опять о функциональном программировании на Python, перевод Intersoft Lab]
  5. [www.ibm.com/developerworks/ru/library/l-prog/ Дэвид Мертц, Очаровательный Python: Функциональное программирование на языке Python, Часть 1]
  6. Душкин, 2007, с. 110.
  7. Чезарини, Томпсон, 2012, с. 27.
  8. Душкин, 2007, с. 110-116.
  9. 1 2 [www.ibm.com/developerworks/ru/library/l-haskell3/ Алексей Бешенов. Функциональное программирование на Haskell: Часть 3. Определение функций, IBM]
  10. [www.softcraft.ru/paradigm/dp/dp05-08.shtml И. А. Дехтяренко, Декларативное программирование, 5.8. Синтаксический сахар: язык Erlang. 2003]
  11. Прохоренок, 2011, с. 124.
  12. Albahari, Albahari, 2012, p. 328-331.

Литература

  • Филд А., Харрисон П. Функциональное программирование = Functional Programming. — М.: Мир, 1993. — 637 с. — ISBN 5-03-001870-0.
  • Прохоренок Н. А. Python. Самое необходимое.. — БХВ-Петербург, 2011. — 416 с. — ISBN 978-5-9775-0614-4.
  • Душкин Р. Функциональное программирование на языке Haskell.. — ДМК-Пресс, 2007. — 608 с. — ISBN 5-94074-335-8.
  • Albahari, J. and Albahari, B. C# 5.0 in a Nutshell: The Definitive Reference. — O'Reilly Media, Incorporated, 2012. — 1042 p. — ISBN 9781449320102.

Отрывок, характеризующий Списковое включение

На третий день своего приезда в Москву он узнал от Друбецких, что княжна Марья в Москве. Смерть, страдания, последние дни князя Андрея часто занимали Пьера и теперь с новой живостью пришли ему в голову. Узнав за обедом, что княжна Марья в Москве и живет в своем не сгоревшем доме на Вздвиженке, он в тот же вечер поехал к ней.
Дорогой к княжне Марье Пьер не переставая думал о князе Андрее, о своей дружбе с ним, о различных с ним встречах и в особенности о последней в Бородине.
«Неужели он умер в том злобном настроении, в котором он был тогда? Неужели не открылось ему перед смертью объяснение жизни?» – думал Пьер. Он вспомнил о Каратаеве, о его смерти и невольно стал сравнивать этих двух людей, столь различных и вместе с тем столь похожих по любви, которую он имел к обоим, и потому, что оба жили и оба умерли.
В самом серьезном расположении духа Пьер подъехал к дому старого князя. Дом этот уцелел. В нем видны были следы разрушения, но характер дома был тот же. Встретивший Пьера старый официант с строгим лицом, как будто желая дать почувствовать гостю, что отсутствие князя не нарушает порядка дома, сказал, что княжна изволили пройти в свои комнаты и принимают по воскресеньям.
– Доложи; может быть, примут, – сказал Пьер.
– Слушаю с, – отвечал официант, – пожалуйте в портретную.
Через несколько минут к Пьеру вышли официант и Десаль. Десаль от имени княжны передал Пьеру, что она очень рада видеть его и просит, если он извинит ее за бесцеремонность, войти наверх, в ее комнаты.
В невысокой комнатке, освещенной одной свечой, сидела княжна и еще кто то с нею, в черном платье. Пьер помнил, что при княжне всегда были компаньонки. Кто такие и какие они, эти компаньонки, Пьер не знал и не помнил. «Это одна из компаньонок», – подумал он, взглянув на даму в черном платье.
Княжна быстро встала ему навстречу и протянула руку.
– Да, – сказала она, всматриваясь в его изменившееся лицо, после того как он поцеловал ее руку, – вот как мы с вами встречаемся. Он и последнее время часто говорил про вас, – сказала она, переводя свои глаза с Пьера на компаньонку с застенчивостью, которая на мгновение поразила Пьера.
– Я так была рада, узнав о вашем спасенье. Это было единственное радостное известие, которое мы получили с давнего времени. – Опять еще беспокойнее княжна оглянулась на компаньонку и хотела что то сказать; но Пьер перебил ее.
– Вы можете себе представить, что я ничего не знал про него, – сказал он. – Я считал его убитым. Все, что я узнал, я узнал от других, через третьи руки. Я знаю только, что он попал к Ростовым… Какая судьба!
Пьер говорил быстро, оживленно. Он взглянул раз на лицо компаньонки, увидал внимательно ласково любопытный взгляд, устремленный на него, и, как это часто бывает во время разговора, он почему то почувствовал, что эта компаньонка в черном платье – милое, доброе, славное существо, которое не помешает его задушевному разговору с княжной Марьей.
Но когда он сказал последние слова о Ростовых, замешательство в лице княжны Марьи выразилось еще сильнее. Она опять перебежала глазами с лица Пьера на лицо дамы в черном платье и сказала:
– Вы не узнаете разве?
Пьер взглянул еще раз на бледное, тонкое, с черными глазами и странным ртом, лицо компаньонки. Что то родное, давно забытое и больше чем милое смотрело на него из этих внимательных глаз.
«Но нет, это не может быть, – подумал он. – Это строгое, худое и бледное, постаревшее лицо? Это не может быть она. Это только воспоминание того». Но в это время княжна Марья сказала: «Наташа». И лицо, с внимательными глазами, с трудом, с усилием, как отворяется заржавелая дверь, – улыбнулось, и из этой растворенной двери вдруг пахнуло и обдало Пьера тем давно забытым счастием, о котором, в особенности теперь, он не думал. Пахнуло, охватило и поглотило его всего. Когда она улыбнулась, уже не могло быть сомнений: это была Наташа, и он любил ее.
В первую же минуту Пьер невольно и ей, и княжне Марье, и, главное, самому себе сказал неизвестную ему самому тайну. Он покраснел радостно и страдальчески болезненно. Он хотел скрыть свое волнение. Но чем больше он хотел скрыть его, тем яснее – яснее, чем самыми определенными словами, – он себе, и ей, и княжне Марье говорил, что он любит ее.
«Нет, это так, от неожиданности», – подумал Пьер. Но только что он хотел продолжать начатый разговор с княжной Марьей, он опять взглянул на Наташу, и еще сильнейшая краска покрыла его лицо, и еще сильнейшее волнение радости и страха охватило его душу. Он запутался в словах и остановился на середине речи.