Фильтр (функция высшего порядка)

В функциональном программировании фильтр — это функция высшего порядка , которая обрабатывает структуру данных (обычно список ) в некотором порядке для создания новой структуры данных, содержащей именно те элементы исходной структуры данных, для которых данный предикат возвращает логическое значение. true.

Пример [ править ]

В Haskell пример кода

 фильтровать   даже   [  1  ..  10  ]

вычисляет список 2, 4,…, 10, применяя предикат evenк каждому элементу списка целых чисел 1, 2, …, 10 в этом порядке и создания нового списка тех элементов, для которых предикат возвращает логическое значение true, тем самым создавая список, содержащий только четные члены этого списка. И наоборот, пример кода

 фильтр   (  нет   .   даже  )   [  1  ..  10  ]

вычисляет список 1, 3, …, 9, собирая те элементы списка целых чисел 1, 2, …, 10, для которых предикат even возвращает логическое значение false (с . являющийся оператором композиции функций ).

Визуальный пример [ править ]

Ниже вы можете увидеть каждый шаг процесса фильтрации для списка целых чисел. X = [0, 5, 8, 3, 2, 1] по функции:

f(x)={\begin{cases}\mathrm {True} &{\text{ if }}x\equiv 0{\pmod {2}}\\\mathrm {False} &{\text{ if }}x\equiv 1{\pmod {2}}.\end{cases}}

Эта функция выражает, что если $x$ даже возвращаемое значение $\mathrm {True}$ , иначе это $\mathrm {False}$ . Это предикат.

применение этапов обработки функции фильтра — Просмотр этапов обработки при применении функции фильтра к списку

Сравнение языков [ править ]

Фильтр — стандартная функция для многих языков программирования , например, Хаскелл, ^[1] ОКамл , ^[2] Стандартный МЛ , ^[3] или Эрланг . ^[4] Common Lisp предоставляет функции remove-if и remove-if-not. ^[5] Запросы на реализацию схемы (SRFI) 1 обеспечивают реализацию фильтра для языка Scheme . ^[6] C++ предоставляет алгоритмы remove_if (мутирующие) и remove_copy_if(немутирующий); C++11 дополнительно предоставляет copy_if (немутирующий). ^[7] Smalltalk предоставляет select:метод для коллекций. Фильтр также можно реализовать с использованием списков на языках, которые их поддерживают.

В Хаскеле filter можно реализовать следующим образом:

 фильтр   ::   (  a   ->   Bool  )   ->   [  a  ]   ->   [  a  ] 
  фильтр   _   []       =   [] 
  фильтр   p   (  x  :  xs  )   =   [  x   |    p   x  ]   ++   фильтр   p   xs

Здесь, [] обозначает пустой список, ++ операцию объединения списков и [x | p x] обозначает список, условно содержащий значение, x, если условие p x держится (оценивается как True).

Фильтровать на разных языках
Язык	Фильтр	Примечания
АПЛ	`(pred array)/array` или `pred{⍵/⍨⍺⍺ ⍵}array`	Второй пример — доп APL .
С# 3.0	`ienum.Where(pred)` или The `where` пункт	Где находится метод расширения ienum — это IEnumerable Аналогично во всех языках .NET.
CFML	`obj.filter(func)`	Где `obj`представляет собой массив или структуру. `func` получает в качестве аргумента значение каждого элемента.
Кложур	`(filter predicate list)^[8]`	Или, через понимание списка : `(for [x list :when (pred x)] x)`
Общий Лисп	`(remove-if inverted-pred list) (remove-if (complement pred) list) (remove-if-not pred list)`	Функция `remove-if-not` устарел ^[5] в пользу эквивалента `remove-if` где предикат дополняется. ^[9] Таким образом, фильтр `(remove-if-not #'oddp '(0 1 2 3))` должно быть написано `(remove-if (complement #'oddp) '(0 1 2 3))` или проще: `(remove-if #'evenp '(0 1 2 3))` где `evenp` возвращает инвертированное значение `oddp`. ^[10]
С++	`std::remove_copy_if(begin, end, result, prednot) std::copy_if(begin, end, result, pred) (C++11)`	в заголовке <алгоритм> начало , конец , результат — итераторы предикат перевернут
Д	`std.algorithm.filter!(pred)(list)`
Эрланг	`lists:filter(Fun, List)`	Или, через понимание списка : `[ X \|\| X <- List, Fun(X) ]`
классный	`list.findAll(pred)`
Хаскелл	`filter pred list`	Или, через понимание списка : `[x \| x <- list, pred x]`
Смешанный	`list.filter(pred)` `Lambda.filter(list, pred)`	Или, через понимание списка : `[x \| x <- list, pred x]`
Дж	`(#~ pred) list`	Пример монадического крючка. # — это копирование, ~ меняет аргументы. `(f g) y = y f (g y)`
Юлия	`filter(pred, array)`	Функция фильтра также принимает `dict`тип данных. Или, через понимание списка : `[x for x in array if pred(x)]`
Ява 8+	`stream.filter(pred)`
JavaScript 1.6	`array.filter(pred)`
Котлин	`array.filter(pred)`
Математика	`Select[list, pred]`
Objective-C ( Какао в Mac OS X 10.4+)	`[array filteredArrayUsingPredicate:pred]`	`pred` является объектом NSPredicate , выразительность которого может быть ограничена.
F# , OCaml , стандартное машинное обучение	`List.filter pred list`
ПАРИ/ГП	`select(expr, list)`	В версии 2.4.2 порядок аргументов изменен на обратный.
Перл	`grep block list grep expr, list`
PHP	`array_filter(array, pred)`
Пролог	`filter(+Closure,+List,-List)`	Начиная с ISO/IEC 13211-1:1995/Cor.2:2012. ^[11] основной стандарт содержит приложение закрытия через `call/N`^[12]
Питон	`filter(func, list)`	Или, через понимание списка : `[x for x in list if pred(x)]`. В Python 3 `filter` был изменен, чтобы возвращать итератор , а не список. ^[13] Дополнительная функциональность, возвращающая итератор по элементам, для которых предикат имеет значение false, также доступна в стандартной библиотеке как `filterfalse` в `itertools` модуль.
Рубин	`enum.find_all {block} enum.select {block}`	`enum` это перечисление
Ржавчина	`iterator.filter(pred)`	`iterator` является `Iterator` и `filter` метод возвращает новый итератор; `pred` это функция (в частности `FnMut`), который получает элемент итератора и возвращает `bool`
С , Р	`Filter(pred,array) array[pred(array)]`	Во втором случае pred должна быть векторизованной функцией.
Скала	`list.filter(pred)`	Или, через понимание: `for(x <- list; if pred) yield x`
Схема Р ⁶РС	`(filter pred list)` `(remove inverted pred list)` `(partition pred list list)`
Болтовня	`aCollection select: aBlock`
Быстрый	`array.filter(pred) filter(sequence, pred)`
XPath , XQuery	`list[block]` `filter(list, func)`	В `block` элемент контекста `.` сохраняет текущее значение

Варианты [ править ]

Фильтр создает результат без изменения исходного списка. Многие языки программирования также предоставляют варианты, которые вместо этого деструктивно изменяют аргумент списка для повышения производительности. Другие варианты фильтра (например, Haskell dropWhile^[14] и partition^[15]) также распространены. Общая оптимизация памяти для чисто функциональных языков программирования заключается в том, чтобы входной список и отфильтрованный результат имели общий самый длинный хвост ( tail-sharing ).

См. также [ править ]

Ссылки [ править ]

^ filter в стандартной прелюдии Haskell
^ filter в OCaml модуле стандартной библиотеки list
^ «Структура списка» . Стандартная базовая библиотека машинного обучения . Проверено 25 сентября 2007 г.
^ filter/2 в документации модуля Erlang STDLIB Reference Guide. lists
^ Перейти обратно: ^а ^б Функция REMOVE, REMOVE-IF, REMOVE-IF-NOT, DELETE, DELETE-IF, DELETE-IF-NOT в HyperSpec Common Lisp
^ filter в СРФИ 1
^ remove_if и remove_copy_if SGI в спецификации стандартной библиотеки шаблонов (STL)
^ clojure.core/filter на ClojureDocs
^ Функция COMPLEMENT в Common Lisp HyperSpec.
^ Функция EVENP, ODDP в Common Lisp HyperSpec.
^ ИСО/МЭК 13211-1:1995/Кор 2:2012.
^ «Проект технического исправления 2» .
^ «Встроенные функции — документация Python 3.9.0» . docs.python.org . Проверено 28 октября 2020 г.
^ Удаление фильтра Haskell Пока
^ фильтра Haskell Раздел

[HaskellStandard-1] filter в стандартной прелюдии Haskell

[OcamlManual-2] filter в OCaml модуле стандартной библиотеки list

[3] «Структура списка» . Стандартная базовая библиотека машинного обучения . Проверено 25 сентября 2007 г.

[4] filter/2 в документации модуля Erlang STDLIB Reference Guide. lists

[remove-if-5] Перейти обратно: ^а ^б Функция REMOVE, REMOVE-IF, REMOVE-IF-NOT, DELETE, DELETE-IF, DELETE-IF-NOT в HyperSpec Common Lisp

[SRFI1-6] filter в СРФИ 1

[SGISTLSpec-7] remove_if и remove_copy_if SGI в спецификации стандартной библиотеки шаблонов (STL)

[8] ure.core/filter на ClojureDocs

[9] Функция COMPLEMENT в Common Lisp HyperSpec.

[10] Функция EVENP, ODDP в Common Lisp HyperSpec.

[Cor.2-11] ИСО/МЭК 13211-1:1995/Кор 2:2012.

[12] «Проект технического исправления 2» .

[13] «Встроенные функции — документация Python 3.9.0» . docs.python.org . Проверено 28 октября 2020 г.

[14] Удаление фильтра Haskell Пока

[15] фильтра Haskell Раздел

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]