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

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

Пример

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

 filter even [1..10]

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

 filter (not . even) [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}$. Это предикат.

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

Сравнение языков

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

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

 filter :: (a -> Bool) -> [a] -> [a]
 filter _ []     = []
 filter p (x:xs) = [x | p x] ++ filter 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)	Или, через понимание списка : (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 устарел в пользу эквивалента remove-if где предикат дополняется. Таким образом, фильтр (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.
С++	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. основной стандарт содержит приложение закрытия через call/N
Питон	filter(func, list)	Или, через понимание списка : [x for x in list if pred(x)]. В Python 3 filter был изменен, чтобы возвращать итератор, а не список. Дополнительная функциональность, возвращающая итератор по элементам, для которых предикат имеет значение 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
Схема Р 6 РС	(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 и partition) также распространены. Общая оптимизация памяти для чисто функциональных языков программирования заключается в том, чтобы входной список и отфильтрованный результат имели самый длинный общий хвост ( tail-sharing ).

См. также

• Карта (функция высшего порядка)
• Понимание списка
• Охранник (вычисление)