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

редактировать

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

Содержание
  • 1 Пример
    • 1.1 Визуальный пример
  • 2 Сравнение языков
  • 3 Варианта
  • 4 См. Также
  • 5 Ссылки
Пример

В 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) = {T rue if x ≡ 0 (mod 2) F alse if x ≡ 1 (mod 2). {\ displaystyle f (x) = {\ begin {cases} True {\ text {if}} x \ Equiv 0 {\ pmod {2}} \\ False {\ text {if}} x \ Equiv 1 {\ pmod {2}}. \ End {cases}}}{\ displaystyle f (x) = {\ begin {case} True {\ text {if}} x \ Equiv 0 {\ pmod {2}} \\ False {\ text {if}} x \ Equiv 1 {\ pmod {2}}. \ end {case}}}

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

применение шагов обработки функции фильтра Просмотр этапов обработки при применении функции фильтрации к списку
Сравнение языков

Фильтр - стандартная функция для многих языков программирования, например, 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.0ienum.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)в заголовке . begin, конец, результат - итераторы. изменен предикат
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,6array.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). Обычная оптимизация памяти для чисто функциональных языков программирования означает, что входной список и отфильтрованный результат должны иметь самый длинный общий хвост (совместное использование хвоста ).

См. Также
Ссылки
Последняя правка сделана 2021-05-20 04:01:53
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте