Filter Function

The FilterFunction is one of the CommonHigherOrderFunctions. It takes a predicate function and a sequence, and returns a sequence consisting of all the members of the input sequence for which the predicate returns true.

This example implementation only works for sequences implemented as lists

 (defun filter (f list)
   (cond
    ((not list)                   ;; the list is empty
     nil)
    ((funcall f (first list))     ;; the first element satisfies the test
     (cons (first list) (filter f (rest list))))
    (t                            ;; otherwise ...
     (filter f (rest list)))))

(filter #'evenp '(1 2 3 4 5 8 2)) ;; EVENP returns T for even numbers => (2 4 8 2)

I can't find an encoding in my browser (Safari 1.0) to make the above lisp look like anything but gibberish. It looks fine in EditPage. Anyone else see anything similar? DavidVincent

HaskellLanguage comes with a filter function in Prelude:

  filter even numbers

OcamlLanguage comes with a filter function in the List module:

  List.filter (fun x -> x mod 2 = 0) numbers

SmlLanguage comes with a filter function in the List module:

  List.filter (fn x => x mod 2 = 0) numbers

CommonLisp has builtin filter functions called REMOVE-IF and REMOVE-IF-NOT (see chapter 17 of the CommonLispHyperSpec):

  (remove-if-not #'evenp '(1 2 3 4 5 8 2))
   => (2 4 8 2)

In SmalltalkLanguage: #select:

  #(1 2 3 4 5) select: [:each | each even]

PerlLanguage's grep isn't limited to regular expressions (it wouldn't be a HigherOrderFunction if it were. Oh yes it would; real perl (ir)regular expressions allow you to embed arbitrary perl code. I am not saying that this is a good thing).

  @evens = grep { $_ & 1 == 0 } (1,2,3,4,5,8,2);

PythonLanguage has a filter function. I guess using ListComprehension would be considered more pythonic.

  evens = filter(lambda x: x%2 == 0, [1,2,3,4,5,8,2])
  evens = [x for x in [1,2,3,4,5,8,2] if x%2 == 0]

RubyLanguage has Enumerable#find_all (and the synonym Enumerable#select):
  evens = [1,2,3,4,5,8,2].select { |i| i%2 == 0 }

CsharpLanguage arrays have a FindAll function.

  evens = Array.FindAll(new int[] {1,2,3,4,5,8,2}, delegate(int n) { return n%2 == 0; });

which can be trivially defined for arbitrary sequences:
  public static IEnumerable<T> FindAll(IEnumerable<T> input, Predicate<T> test) {
    foreach (T item in input) if test(item) yield return item;
  }

CsharpLanguage 3.0 adds three features that make this more direct:

(1) Compact lambda syntax simplifies the call to Array.FindAll:

  var numbers = new int[] {1,2,3,4,5,8,2};
  var evens = Array.FindAll(numbers, n => n % 2 == 0);

(2) The FindAll method above is built-in to the framework (and called Where):

  evens = numbers.Where(n => n % 2 == 0);

(3) The language now supports list comprehension syntax:

  evens = from n in numbers where n % 2 == 0 select n;

ErlangLanguage has HigherOrderFunctions, but you could use a ListComprehension for this:

  [X || X <- [1,2,3,4,5,8,2], (X rem 2) == 0].
    => [2,4,8,2]

In JavaScript 1.6, arrays have a method called "filter":

  var evens = numbers.filter(function(x){return x % 2 == 0;});

In the not-yet standardized R<sup>6</sup>RS Scheme, there is a function called filter:

  (filter (lambda (x) (= 0 (modulo x 2))) numbers)

In PhpLanguage:

  $evens = array_filter(array(1,2,3,4,5,8,2), create_function('$x', 'return $x % 2 == 0;'));


CeePlusPlus has "remove_if" and "remove_copy_if" in the header <algorithm>. They kind of implement Filter with the predicate reversed.

Remove_copy_if most closely approximates Filter. The format is: std::remove_copy_if(begin, end, result, predicate), where begin, end, and result are iterators. It copies the elements between begin and end that do NOT satisfy the predicate to the location starting at result. It does not mutate the original collection.

 bool is_odd(int x) { return x % 2 != 0; }

std::vector<int> nums; for (int i = 0; i < 10; i++) nums.push_back(i); std::vector<int> evens; std::remove_copy_if(nums.begin(), nums.end(), std::back_inserter(evens), is_odd);

Note: Contrary to popular belief, there is no "copy_if" function in the C++ standard. Use "remove_copy_if" with the reversed predicate.

Remove_if mutates the collection it's used on, but does not actually "remove" anything, because it cannot remove with an iterator alone. Instead, it simply moves the "unwanted" elements to the end of the collection. The format is: std::remove_copy_if(begin, end, predicate). It returns an iterator to the "new end" of the collection; that is, the items between the "new end" and end are the unwanted items.

 std::vector<int> nums;
 for (int i = 0; i < 10; i++)
   nums.push_back(i);
 std::vector<int>::iterator new_end =
   std::remove_if(nums.begin(), nums.end(), is_odd);
 nums.erase(new_end, nums.end()); // erase the odd elements from the collection


ObjectiveCee In MacOSX 10.4+ CocoaFramework provides an "NSPredicate" system for specifying queries about properties objects in a simple, user-friendly syntax. It was relatively limited, and was expanded in Mac OS X 10.5; however, it is not documented well. The following seems to work on Mac OS X 10.5 with an array of NSNumbers:

 NSPredicate *isEven = [NSPredicate predicateWithFormat:@"modulus:by:(SELF, 2) == 0"];
 NSArray *evens = [numbers filteredArrayUsingPredicate:isEven];


CategoryFunctionalProgramming CategoryInManyProgrammingLanguages

EditText of this page (last edited July 14, 2009) or FindPage with title or text search