В функциональном программировании фильтр — это функция высшего порядка , которая обрабатывает структуру данных (обычно список ) в некотором порядке для создания новой структуры данных, содержащей именно те элементы исходной структуры данных, для которых заданный предикат возвращает логическое значение 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]в соответствии с функцией:
Эта функция выражает, что если четно, то возвращаемое значение равно , в противном случае — . Это предикат.
Фильтр — стандартная функция для многих языков программирования , например, Haskell, [1] OCaml , [2] Standard ML , [3]
или Erlang . [4] Common Lisp предоставляет функции remove-ifи remove-if-not. [5] Scheme Requests for Implementation (SRFI) 1 предоставляет реализацию фильтра для языка Scheme . [6] C++ предоставляет алгоритмы remove_if (мутирующий) и remove_copy_if(немутирующий); C++11 дополнительно предоставляет copy_if(немутирующий). [7] Smalltalk предоставляет select:метод для коллекций. Фильтр также может быть реализован с использованием списочных включений в языках, которые их поддерживают.
В Haskell filterэто можно реализовать так:
фильтр :: ( a -> Bool ) -> [ a ] -> [ a ] фильтр _ [] = [] фильтр p ( x : xs ) = [ x | p x ] ++ фильтр p xs Здесь []обозначает пустой список, ++операцию конкатенации списков, а [x | p x]обозначает список, условно содержащий значение, x, если условие p xвыполняется (оценивается как True).
Фильтр создает свой результат, не изменяя исходный список. Многие языки программирования также предоставляют варианты, которые деструктивно изменяют аргумент списка вместо этого для более высокой производительности. Другие варианты фильтра (например, Haskell dropWhile[14] и partition[15] ) также распространены. Распространенная оптимизация памяти для чисто функциональных языков программирования заключается в том, чтобы входной список и отфильтрованный результат имели самый длинный общий хвост ( tail-sharing ).
listlists