F# Friday – The filter Function

Another frequently used operation in functional programming is filter. The filter function allows you to pare down a collection by specifying a criterion. Any element in the collection that does not meet that criterion is dropped, and you get a new collection consisting only of the elements that meet the criterion.

Sequential Collections

Suppose you have a list of numbers, and you want to filter out the odd numbers, leaving only the evens. Define a predicate—a function that takes an input and returns true or false—that determines whether an integer is even, returning true for even numbers and false for odd. Pass that predicate and your list to List.filter, and List.filter returns a new list containing only the even numbers:

Here is the code:

let f = fun n -> n % 2 = 0
let evens = [4; 5; 6; 7] |> List.filter f
// val evens : int list = [4; 6]

Notice that filter preserves the order of the original collection because a list is a sequential collection. The same goes for arrays and sequences.

Sets

While filter works essentially the same for sets as it does for the sequential collections, it does not guarantee to preserve the order. Such is the nature of sets: they are not sequential collections.

If you have a set of words, and you want to retain only the words that start with “d,” you take the same approach as with a list. Define a predicate that determines whether a string starts with "d". Then pass your predicate and your set to Set.filter:

The code ought to look pretty familiar:

let f = fun (s : string) -> s.StartsWith("d")
let dWords =
  set ["witch"; "call"; "depths"; "disgrace"]
  |> Set.filter f
// val dWords : Set<string> =
//   set ["depths"; "disgrace"]

Again, while the order of the elements happens to have been preserved in this simple example with a small set, Set.filter is not required to do so.

Maps

There is also Map.filter. Instead of taking a single-input predicate, Map.filter takes a two-input predicate: the first input is the map’s key type, and the second is the value type. That means you can filter a map on the key, the value, or both.

Maybe you have a map of Dream Theater albums to the members of the band who played on that album. (Dream Theater has undergone a lineup change or two.) You want to know on which albums Kevin Moore was on keyboards:

let albums =
  [
    "When Dream and Day Unite", set ["Dominici";"Petrucci";"Moore";"Myung";"Portnoy"];
    "Images and Words", set ["LaBrie";"Petrucci";"Moore";"Myung";"Portnoy"];
    "Awake", set ["LaBrie";"Petrucci";"Moore";"Myung";"Portnoy"];
    "Falling into Infinity", set ["LaBrie";"Petrucci";"Sherinian";"Myung";"Portnoy"];
    "Metropolis Pt. 2", set ["LaBrie";"Petrucci";"Rudess";"Myung";"Portnoy"];
    "Six Degrees of Inner Turbulence", set ["LaBrie";"Petrucci";"Rudess";"Myung";"Portnoy"];
    "Train of Thought", set ["LaBrie";"Petrucci";"Rudess";"Myung";"Portnoy"];
    "Octavarium", set ["LaBrie";"Petrucci";"Rudess";"Myung";"Portnoy"];
    "Systematic Chaos", set ["LaBrie";"Petrucci";"Rudess";"Myung";"Portnoy"];
    "Black Clouds and Silver Linings", set ["LaBrie";"Petrucci";"Rudess";"Myung";"Portnoy"];
    "A Dramatic Turn of Events", set ["LaBrie";"Petrucci";"Rudess";"Myung";"Mangini"];
    "Dream Theater", set ["LaBrie";"Petrucci";"Rudess";"Myung";"Mangini"] ]
  |> Map.ofList
let withMoore =
  albums
  |> Map.filter (fun _ v -> Set.contains "Moore" v)
// val withMoore : Map<string,string list> =
//   map
//     [("Awake",
//       set ["LaBrie"; "Petrucci"; "Moore"; "Myung"; "Portnoy"]);
//      ("Images and Words",
//       set ["LaBrie"; "Petrucci"; "Moore"; "Myung"; "Portnoy"]);
//      ("When Dream and Day Unite",
//       set ["Dominici"; "Petrucci"; "Moore"; "Myung"; "Portnoy"])]

That’s a big chunk there, but the long and the short is that our filter function is ignoring the key (hence the underscore) and examining only the value, searching the set in each entry for Moore’s name.