Author: Brad

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.

One of the most frequently used operations in functional programming is the map operation. The map operation takes a collection of values, performs some transformation on each element, and creates a new collection containing those new elements. The elements in the new collection can be the same type as the elements in the original collection, or they may be of a different type. It just depends on the transformation.

Sequential Collections

Let’s look at a couple of examples. First, say that you have a list of integers, and you need the squares of those integers:

You can define the function f to calculate the square of a number. Then you can use the map function to apply f to each member in the input list and create a new list containing the squares of the items in the original list. In functional programming parlance, we say that you map f over the list to produce the new list. The code looks like this:

let f = fun n -> n * n
let squares = [2; 4; 6; 8] |> List.map f
// val squares : int list = [4; 16; 36; 64]

Of course, you can also define the mapping function inline:

let squares = [2; 4; 6; 8]
              |> List.map (fun n -> n * n)
// val squares : int list = [4; 16; 36; 64]

Second, suppose you need to compute the length of each string in a list:

Similar to the last example, just define a function to calculate the length of a string, and map it over the list of strings with the map function:

let f = fun (s : string) -> s.Length
let lengths = ["five"; "six"; "pick up"; "sticks"]
              |> List.map f
// val lengths : int list = [4; 3; 7; 6]

Notice two things:

1. In both examples, the output list maintains the order of the elements in the input list. This happens because a list is a sequential collection. The same is also true for an array and a sequence. In contrast, as we will see in a moment, order is not maintained when mapping over a non-sequential collection like a set.

2. Whereas the type of both the input list and the output list is the same in the first example—they both contain integers—in the second example, the type of the elements in the output list (integers) is different from the type of the elements of the input list (strings). This happens frequently in functional programming. It is not uncommon to move a collection of inputs through a series of transformations, changing the type with each transformation.

Sets

The Set module also defines a map function. It behaves essentially the same as the map functions for lists, arrays, or sequences, but there are some minor differences. Sets are not sequential collections, so the order of their elements is not guaranteed. In other words, if you iterate through the input set and get the elements out in a certain order, after you map over it to get the output set, iterating over the elements of the output set may not yield the same order as the counterpart elements in the input set. Furthermore, by definition, sets cannot contain duplicates. So then, what happens if you map a function over the input set that produces duplicate output values? Let’s see:

let lengths = set["four"; "five"; "six"; "seven"]
              |> Set.map (fun s -> s.Length)
// val lengths : Set<int> = set [3; 4; 5]

That makes sense. Duplicates are dropped. Well, now you know. And knowing is half the battle. (What’s the other half, though? They never did tell us that!)

Strings

Finally, you can map over strings as well. Mapping over strings operates on each character in the string:

let toUpper = fun c -> System.Char.ToUpper(c)
let allcaps = "sesquipedalian"
              |> String.map toUpper
// val allcaps : string = "SESQUIPEDALIAN"

Using String.map does have one constraint: You must use a mapping function with the signature char -> char. That is, it must take a char and return a char. If you need to transform the characters into values of another type, you can use Seq.map, which treats the string as a sequence of characters:

let ascii = "sesquipedalian"
            |> Seq.map (fun c -> int c)
// val ascii : seq<int> =
//   seq [115; 101; 115; 113; ...]

Collections

F#’s sequential collections all define the concat function: Array.concat, List.concat, and Seq.concat. The concat function takes a sequence of arrays, lists, or sequences and flattens them. (In fact, some languages call this operation “flatten.”) That is, it takes the elements of the nested collections, pulls them out, and puts them all together in order in a new sequential collection, according to the type of the nested collection.

To illustrate, let’s say that the (now defunct) Java Posse podcast members and the .NET Rocks podcast members want to get together (as they did once before) to do a combined podcast—a panel, if you will, or an omni-podcast:

let javaPosse = ["Dick"; "Tor"; "Carl"; "Chet"]
let dotNetRocks = ["Carl"; "Richard"]
let podcasts = seq [javaPosse; dotNetRocks]
// val podcasts : seq<string list> =
//   [
//     ["Dick"; "Tor"; "Carl"; "Chet"];
//     ["Carl"; "Richard"]
//   ]

So now you have a list of lists. To get your omni-podcast panel, you call List.concat on podcasts:

let panel = List.concat podcasts
// val panel : string list =
//   ["Dick"; "Tor"; "Carl"; "Chet"; "Carl"; "Richard"]

As you can see, concat flattens the nested lists into one long list and preserves the order of the elements as they were in the original nested lists.

Another illustration: File.ReadAllLines reads all the lines of a file into an array. If you should need an omnibus array of all of the lines in a collection of files, you could do this:

let files = [| "file1.txt", "file2.txt" |]
let allLines =
  files
  |> Array.map File.ReadAllLines  // nested arrays of lines
  |> Array.concat  // flattens nested arrays into one array
// val lines : string [] =
//   [|
//     "file1 line1"; "file1 line2";
//     "file2 line1"; "file2 line2"; "file2 line3";
//      ...
//   |]

Strings

The String module also defines a concat function. It takes a sequence of strings and joins them all together into one string. String.concat is a little different from the collection versions of the concat function in that it takes two parameters: the string sequence is the second parameter, but the first is a separator or delimiter string. (Some languages call this operation “join.”)

For example, if you have a list of names that you want to concatenate together, but separate with a comma and a space, this gets you where you want to go:

let beatles =
  ["John"; "Paul"; "George"; "Ringo"]
  |> String.concat ", "
// val beatles : string = "John, Paul, George, Ringo"

But if you want to make String.concat act just like the collection versions of concat, that is, just to jam the strings together with no delimiter, just use en empty string as your delimiter:

let atrocious =
  [
    "super"; "cali"; "fragi"; "listic";
    "expi"; "ali"; "docious"
  ]
  |> String.concat ""
// val atrocious : string =
//   "supercalifragilisticexpialidocious"

I’ve already used the pipeline operator ( |> ) in previous F# Friday posts, but it occurred to me that it and its comrades are worth a discussion of their own.

F#’s convention in collection modules is to make the collection the last argument to any function.

let hs = List.filter 
           (fun (s:string) -> s.StartsWith("h"))
           ["hi"; "di"; "ho"]
// val hs : string list = ["hi"; "ho"]

Simple enough, but it gets a little hairy when you want to chain operations together. Let’s say that you want to (1) perform a map operation on all the elements in a list, (2) filter out some elements, (3) take the first three elements, and then finally (4) multiply them all together. You can pack it all into one expression, but it’s not pretty:

let p = Seq.reduce (*)
         (Seq.truncate 3
           (List.filter (fun n -> n % 2 = 1)
             (List.map (fun n -> (3 * n)) [1..10])))
// val p : int = 405

The parentheses start to stack up, and to follow what’s going on, you’re forced to do the opposite of what comes naturally: You have to start with the end of the expression and work your way backward to the beginning.

What is this, Clojure? (Wink, wink, nudge, nudge, say no more.)

You can improve upon the above by assigning the result of each step to a temporary variable:

let mapped = List.map (fun n -> (3 * n)) [1..10]
let filtered = List.filter (fun n -> n % 2 = 1) mapped
let truncated = Seq.truncate 3 filtered
let reduced = Seq.reduce (*) truncated
// val reduced : int = 405

That’s … better, but it could be better still. What pattern do we notice about each step? The result of each step becomes the last input of the next step. What if there were a way to forward the result of each step to the last input of the step that follows it? That way we could read each step of the process, top-to-bottom and left-to-right, in the order that it occurs.

Enter the Pipeline Operator

Specifically the forward pipeline operator:

let p = List.map (fun n -> (3 * n)) [1..10]
        |> List.filter (fun n -> n % 2 = 1)
        |> Seq.truncate 3
        |> Seq.reduce (*)
// val p : int = 405

Ah, that’s much better. The result of the expression on each line feeds directly into the next line, becoming its final input. We can actually make one more little tweak:

let p = [1..10]
        |> List.map (fun n -> (3 * n))
        |> List.filter (fun n -> n % 2 = 1)
        |> Seq.truncate 3
        |> Seq.reduce (*)
// val p : int = 405

That puts the input on its own line, so that it’s clear what the starting state is, and then there’s nothing on each line that follows but the operation to be performed on the input at that stage of the process.

Two Are Better than One

There is also a two-element version of the pipeline operator. If you want to use it to pass two values to a two-input function, just wrap those inputs in a two-element tuple (also known as a pair or a couple):

let subtract a b = a - b
let diff = subtract 17 11
let diff2 = (17, 11) ||> subtract
// val diff : int = 6
// val diff2 : int = 6

The use case for ( ||> ) is when you need to chain calls together that take two arguments and return a couple. It’s a contrived example, but you could calculate Fibonacci numbers this way:

let fib m n = n, m + n
let f = (1, 1)
        ||> fib
        ||> fib
        ||> fib
        ||> fib
// val f : int * int = (5, 8)

A Threefold Cord

There is even a three-element version: ( |||> ). You could take a three-element position tuple (or a triple) containing a north-south element, an east-west element, and an up-down element and move it around with functions that take three arguments and return a triple:

let north ns ew ud = (ns + 1, ew,     ud)
let south ns ew ud = (ns - 1, ew,     ud)
let east  ns ew ud = (ns,     ew + 1, ud)
let west  ns ew ud = (ns,     ew - 1, ud)
let up    ns ew ud = (ns,     ew,     ud + 1)
let down  ns ew ud = (ns,     ew,     ud - 1)
let p3 = (0,0,0)
         |||> north |||> north |||> north
         |||> west
         |||> down |||> down
// val p3 : int * int * int = (3, -1, -2)

Do I Hear Four?

Alas, if you need to pass a four-element tuple (a quad) to a four-input function, there is no pre-defined pipeline operator that meets your needs. And probably for good reason, frankly. But we throw caution to the wind around here: Let’s just define our own!

let (||||>) (a, b, c, d) f = f a b c d

Now you can extend that position triple with a fourth element that accumulates the distance covered with each move:

let (||||>) (a, b, c, d) f = f a b c d
let north4 ns ew ud Δ = (ns + 1, ew,     ud,     Δ + 1)
let south4 ns ew ud Δ = (ns - 1, ew,     ud,     Δ + 1)
let east4  ns ew ud Δ = (ns,     ew + 1, ud,     Δ + 1)
let west4  ns ew ud Δ = (ns,     ew - 1, ud,     Δ + 1)
let up4    ns ew ud Δ = (ns,     ew,     ud + 1, Δ + 1)
let down4  ns ew ud Δ = (ns,     ew,     ud - 1, Δ + 1)
let p4 = (0,0,0,0)
         ||||> north4 ||||> north4 ||||> north4
         ||||> west4
         ||||> down4 ||||> down4
// val p4 : int * int * int * int = (3, -1, -2, 6)

… We Came In

Finally, there are also one-, two-, and three-element versions of the backward pipeline operator. A backward pipeline operator sends the result of its right-hand expression to the function on the left-hand side as its final input value:

let weapon = Some 6
printfn "%s" <| match weapon with
                | Some d -> 
                  sprintf "Your weapon does %d points of damage" d
                | None -> "Better run for the hills"
// Your weapon does 6 points of damage

The backward pipeline operators see less use than the forward operators, and you can probably see why. What’s the point? The reason for the forward pipeline is to transplant the result of an expression from the left-hand side of the function call to the right. Well, if you’re already on the right-hand side of the function call, why would you need another operator? Dave Fancher in The Book of F# puts it this way:

Because it changes precedence within an expression, the backward pipelining operator is sometimes used as a replacement for parentheses.

As you can see in the example above, you are able to put a complex expression on the right-hand side of the backward pipeline operator. The whole match expression is evaluated first and then passed to printfn as its final argument.

This Is Where …

Even though the backward pipeline operator can eliminate some parentheses, sometimes you still need some parentheses to force the right precedence. For instance, this doesn’t work:

let s = String.concat " " <| Seq.append ["DO"] <| ["MI";"SOL"]
--------^^^^^^^^^^^^^^^^^
// error FS0001: Type mismatch. Expecting a
//     'a -> 'b -> 'c    
// but given a
//     'a -> string    
// The type ''a -> 'b' does not match the type 'string'

This happens because, while backward pipelining allows you to evaluate the right-hand expression first, the compiler still evaluates chains of backward pipelines from left to right. In other words, the compiler sees the above expression as this:

let s = (String.concat " " <| Seq.append ["DO"]) <| ["MI";"SOL"]

Bend the compiler to your will with this:

let s = String.concat " " <| (Seq.append ["DO"] <| ["MI";"SOL"])
// val s : string = "DO MI SOL"