F# Friday – The map Function

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:

Illustrates mapping a squaring function over a list of integers (2, 4, 6, 8) to produce a new list of integers (4, 16, 36, 64)
Mapping a Squaring Function over a List of 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:

Illustrates mapping a function to calculate string length over a list of strings ("five", "six", "pick up", "sticks") to produce a list of integers (4, 3, 7, 6)
Mapping a Length Function over a List of Strings

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; ...]

F# Friday – The concat Function

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"

F# Friday – Pipeline Operators

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"

F# Friday – The (Elusive) contains Function

Let’s say you have a set containing the nicknames of the guys in the band Rush, and you want to see whether a certain person is in the band. No problem:

let rush = set ["Dirk"; "Lerxst"; "Pratt"]

let gotAlex = rush |> Set.contains "Lerxst"
// val gotAlex : bool = true
let gotAngus = rush |> Set.contains "Angus"
// val gotAngus : bool = false

If, on the other hand, you have the same values in a list, things don’t go so well:

let rush = ["Dirk"; "Lerxst"; "Pratt"]

let gotAlex = rush |> List.contains "Lerxst"
//   rush |> List.contains "Lerxst"
//   -------------^^^^^^^^
//
// error FS0039: The value, constructor,
// namespace or type 'contains' is not defined

Huh? No contains function in the List module? OK, what if you try it with an array?

let rush = [|"Dirk"; "Lerxst"; "Pratt"|]

let gotAlex = rush |> Array.contains "Lerxst"
//   rush |> Array.contains "Lerxst"
//   --------------^^^^^^^^
//
// error FS0039: The value, constructor,
// namespace or type 'contains' is not defined

Still AOL! Don’t look for it in the Seq module either; it’s not there.

Lists, Arrays, and Sequences (Oh My!)

Well, there are two ways around these limitations. First, contains is just a special case of exists, which is defined in all the collections modules. As F#’s modules are open, it’s easy enough to add contains to your projects:

module List =
    let contains x = List.exists ((=) x)

module Array =
    let contains x = Array.exists ((=) x)

module Seq =
    let contains x = Seq.exists ((=) x)

And voila, all of the following now work fine:

let rushL = ["Dirk"; "Lerxst"; "Pratt"]
let rushA = [|"Dirk"; "Lerxst"; "Pratt"|]
let rushSeq = seq ["Dirk"; "Lerxst"; "Pratt"]

let gotAlex = rushL |> List.contains "Lerxst"
// val gotAlex : bool = true
let gotNeil = rushA |> Array.contains "Pratt"
// val gotNeil : bool = true
let gotGene = rushSeq |> Seq.contains "Gene"
//val gotGene : bool = false

// Lists and arrays are sequences!
let gotGeddy = rushL |> Seq.contains "Dirk"
// val gotGeddy : bool = true
let gotPeter = rushA |> Seq.contains "Peter"
// val gotPeter : bool = false

The other approach you could take is to use LINQ. Opening the System.Linq namespace grants you access to all of the Enumerable extension methods. That means that all of the following work:

open System.Linq

let rushL = ["Dirk"; "Lerxst"; "Pratt"]
let rushA = [|"Dirk"; "Lerxst"; "Pratt"|]
let rushSet = set ["Dirk"; "Lerxst"; "Pratt"]
let rushSeq = seq ["Dirk"; "Lerxst"; "Pratt"]

let gotAlex = rushL.Contains "Lerxst"
// val gotAlex : bool = true
let gotNeil = rushA.Contains "Pratt"
// val gotNeil : bool = true
let gotGeddy = rushSet.Contains "Dirk"
// val gotGeddy : bool = true
let gotGene = rushSeq.Contains "Gene"
//val gotGene : bool = false

If you prefer your F# to be a little more idiomatic, you can define new module functions that delegate to LINQ rather than using exists:

open System.Linq

module List =
    let contains x (l: 'T list) = l.Contains x

module Array =
    let contains x (a : 'T array) = a.Contains x

module Seq =
    let contains x (s : 'T seq) = s.Contains x

Strings

Similarly, the String module does not contain a contains function either. You can take the same tack as you did with the other collections and define contains in terms of exists:

module String =
    let contains x = String.exists ((=) x)

let gotX = "Lerxst" |> String.contains 'x'
// val gotX : bool = true
let gotA = "Lerxst" |> Seq.contains 'A'
// val gotA : bool = false

Or you likewise have the option of using LINQ:

open System.Linq

module String
    // String.Contains can take a char or a string,
    // so you have to specify which
    let contains (c : char) (s : string) = s.Contains c

let gotX = "Lerxst" |> String.contains 'x'
// val gotX : bool = true
let gotA = "Lerxst" |> Seq.contains 'A'
// val gotA : bool = false

Of course, because String.Contains is overloaded to take either a string or a char, you have a little more flexibility if you call it as a method on the string rather than an F# function:

"Pratt".Contains("tt")
// val it : bool = true
"Pratt".Contains('p')
// val it : bool = false

Maps

Finally, the Map module does have a containsKey function …

let rushM = ["Dirk", "bass"; "Lerxst", "guitar"; "Pratt", "drums"]
            |> Map.ofList
let gotGed = rushM |> Map.containsKey "Dirk"
// val gotGed : bool = true

… but no containsValue or contains functions:

rushM |> Map.contains "Dirk"
//   rushM |> Map.contains "Dirk"
//   -------------^^^^^^^^
//
// stdin(5,14): error FS0039: The value, constructor,
// namespace or type 'contains' is not defined

rushM |> Map.contains ("Dirk", "bass")

//   rushM |> Map.contains ("Dirk", "bass")
//   -------------^^^^^^^^
// 
// stdin(7,14): error FS0039: The value, constructor,
// namespace or type 'contains' is not defined

rushM |> Map.containsValue "bass"
//   rushM |> Map.containsValue "bass"
//   -------------^^^^^^^^^^^^^
// 
// stdin(9,14): error FS0039: The value, constructor,
// namespace or type 'containsValue' is not defined

As with the other collections, we can define contains and containsValue in terms of exists:

module Map =
    let contains (k,v) = Map.exists (fun x y -> (x,y) = (k,v))
    let containsValue v = Map.exists (fun _ x -> x = v)

let gotDirkOnBass = rushM |> Map.contains ("Dirk", "bass")
// val gotDirkOnBass : bool = true
let gotBassPlayer = rushM |> Map.containsValue "bass"
// val gotBassPlayer : bool = true

You could alternatively define contains in terms of LINQ, but it is more verbose and provides no advantage over Map.exists. Because neither LINQ nor the IDictionary interface provide a ContainsValue method, defining Map.containsValue is certainly more verbose and a little more involved than simply using Map.exists.

NOTE: As of this writing, F# 3.1 is the latest version. According to UserVoice, F# 4.0 adds the missing contains function to the List, Array, and Seq modules, along with a few other useful functions.

F# Friday — The exists Function

The collections modules in F# all define an exists function that takes a predicate and an instance of the collection. If any item in the collection meets the predicate, exists returns true. Otherwise, it returns false.

[1..12] |> List.exists (fun n -> n = 11)
// val it : bool = true

[|1..12|] |> Array.exists (fun n -> n < 1)
// val it : bool = false

set [1..12] |> Set.exists (fun n -> n % 2 = 0)
// val it : bool = true

seq [1..12] |> Seq.exists (fun n -> n > 20)
// val it : bool = false

Of course, as lists, arrays, and sets are all sequences, we can use Seq.exists for all of them:

[1..12] |> Seq.exists (fun n -> n = 11)
// val it : bool = true

[|1..12|] |> Seq.exists (fun n -> n < 1)
// val it : bool = false

set [1..12] |> Seq.exists (fun n -> n % 2 = 0)
// val it : bool = true

Strings are collections/sequences of characters, so both of the following are valid:

"asdf" |> String.exists (fun c -> c = 's')
// val it : bool = true

"asdf" |> Seq.exists (fun c -> c = 'b')
// val it : bool = false

The Map module also defines an exists function, but the predicate takes two inputs: one for the key and one for the value.

[("A", 1); ("B", 2); ("C", 4); ("D", 8)]
|> Map.ofList
|> Map.exists (fun k v -> (k,v) = ("C",4))
// val it : bool = true

And of course, if you want to test only the key or only the value, name the input of no interest with an underscore in the lambda.

[("A", 1); ("B", 2); ("C", 4); ("D", 8)]
|> Map.ofList
|> Map.exists (fun k _ -> k = "Z")
// val it : bool = false

[("A", 1); ("B", 2); ("C", 4); ("D", 8)]
|> Map.ofList
|> Map.exists (fun _ v -> v = 2)
// val it : bool = true

The Option module also defines an exists function. If the option is Some, then exists applies the predicate to the value in the Some instance and returns the result. If the option is None, then exists always returns false.

Some "X" |> Option.exists (fun s -> s = "X")
// val it : bool = true

Some "X" |> Option.exists (fun s -> s = "Y")
// val it : bool = false

None |> Option.exists (fun s -> s = "X")
// val it : bool = false