В функциональном программировании, фильтр - это функция высшего порядка, которая обрабатывает структуру данных (обычно list ) в некотором порядке для создания новой структуры данных, содержащей именно те элементы исходной структуры данных, для которых данный предикат возвращает логическое значение 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 ]
в соответствии с функцией:
Эта функция выражает, что если даже, возвращаемое значение равно , иначе это . Это предикат.
Просмотр этапов обработки при применении функции фильтрации к спискуФильтр - стандартная функция для многих языков программирования, например, Haskell, OCaml, Standard ML или Erlang. Common Lisp предоставляет функции remove-if
и remove-if-not
. Запросы схемы для реализации (SRFI) 1 предоставляют реализацию фильтра для языка Схема. C ++ предоставляет алгоритмы remove_if
(изменяющийся) и remove_copy_if
(неизменяемый); C ++ 11 дополнительно предоставляет copy_if
(без мутации). Smalltalk предоставляет метод select:
для коллекций. Фильтр также можно реализовать с помощью составных частей списка на языках, которые их поддерживают.
В Haskell фильтр
может быть реализован следующим образом:
filter :: (a ->Bool) ->[a] ->[a] filter _ = filter p ( x: xs) = [x | p x] ++ filter p xs
Здесь обозначает пустой список,
++
операцию конкатенации списков и [x | p x]
обозначает список, который условно содержит значение x
, если выполняется условие p x
(оценивается как True
).
Язык | Фильтр | Примечания | |
---|---|---|---|
APL | (массив предикатов) / массив | ||
C# 3.0 | ienum.Where (пред) . or. where предложение | Где - метод расширения. ienum - это IEnumerable. Аналогично во всех языках.NET | |
CFML | obj.filter (func) | Где obj - массив или структура. func получает в качестве аргумента значение каждого элемента. | |
Clojure | (список предикатов фильтра) | Или через понимание списка : (для [x list: when (pred x)] x) | |
Common Lisp | (удалить-если-инвертированный-список-пред). (удалить-если (дополнить-пред) список). (удалить-если-не-список-пред) | Функция удалить-если-не устарел в пользу эквивалентного 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 . | |
C ++ | std :: remove_copy_if (begin, end, result, prednot). std :: copy_if (begin, end, result, pred) (C ++ 11) | в заголовке | |
D | std.algorithm.filter! (pred) (list) | ||
Erlang | lists: filter (Fun, List) | Или, через понимание списка : [X || X <- List, Fun(X) ] | |
Groovy | list.findAll (pred) | ||
Haskell | отфильтровать список предварительных запросов | Или, через понимание списка : [x | x <- list, pred x] | |
Haxe | list.filter (pred) . Lambda.filter (list, pred). | Или, через понимание списка : [x | x <- list, pred x] | |
J | (# ~ pred) list | Пример монадической ловушки. # копирует, ~ меняет аргументы. (f g) y = y f (g y) | |
Julia | filter (pred, array) | Функция фильтра также принимает тип данных dict . Или через понимание списка : [x для x в массиве, если pred (x)] | |
Java 8+ | stream.filter (pred) | ||
JavaScript 1,6 | array.filter (pred) | ||
Kotlin | array.filter (pred) | ||
Mathematica | Select [list, pred] | ||
Objective-C (Какао в Mac OS X 10.4+) | [array filterArrayUsingPredicate: pred] | pred - это объект NSPredicate, который может быть ограничен в выразительность | |
F#, OCaml, Standard ML | List.filter pred list | ||
PARI / GP | select (expr, list) | Порядок аргументов в версии 2.4 обратный.2. | |
Perl | список блоков grep. grep expr, list | ||
PHP | array_filter (array, pred) | ||
Prolog | filter (+ Closure, + List, -List) | Начиная с ISO / IEC 13211-1: 1995 / Cor.2: 2012, основной стандарт содержит приложение закрытия через call / N | |
Python | filter (func, list) | Или через понимание списка : [x вместо x в списке if pred (x)] . В Python 3.x фильтр filter был изменен, чтобы возвращать итератор, а не список. Дополнительные функции, возвращающие итератор по элементам, для которых предикат ложен, также доступны в стандартной библиотеке как filterfalse в модуле itertools . | |
Ruby | enum.find_all {block}. enum.select {block} | enum - это перечисление | |
Rust | iterator.filter (pred) | iterator - это Iterator , а метод filter возвращает новый итератор; pred - это функция (в частности, FnMut ), которая получает элемент итератора и возвращает bool | |
S, R | Filter (pred, array). array [pred (array)] | Во втором случае pred должен быть векторизованной функцией | |
Scala | list.filter (pred) | Или, через for-computing: for (x <- list; if pred) yield x | |
Схема RRS | (список фильтров с предварительным просмотром) . (удалить список с обратным просмотром) . (список списка с предварительным разделением) | ||
Smalltalk | Выбор коллекции: aBlock | ||
Swift | array.filter (pred). filter (sequence, pred) | ||
XPath, XQuery | list [block] . filter (list, func) | В блоке контекстный элемент . содержит текущее значение |
Фильтр создает свой результат без изменения исходного списка. Многие языки программирования также предоставляют варианты, которые вместо этого деструктивно измените аргумент списка для повышения производительности. Также распространены другие варианты фильтра (например, Haskell dropWhile
и partition
). Обычная оптимизация памяти для чисто функциональных языков программирования означает, что входной список и отфильтрованный результат должны иметь самый длинный общий хвост (совместное использование хвоста ).