F# Friday – The Seq.takeWhile Function

When you want a set number of items from the beginning of a sequence, you use Seq.take or Seq.truncate. When you don’t care so much about the number, but rather the nature of the items, use Seq.takeWhile.

Seq.takeWhile starts at the beginning of the sequence and applies a predicate to each item, one by one. It returns each item in a new sequence until it reaches an item that does not meet the predicate:

Seq.takeWhile takes items from the beginning of a sequence until it reaches an item that does not meet the given predicate.
Taking Items from a Sequence While a Predicate Holds

Note that Seq.takeWhile does not return the item that fails to meet the predicate. It stops with the last item that meets the predicate.

Perhaps you have a sensor feeding you temperature readings once per minute:

type Reading = {
    Temperature : float
    Timestamp : DateTime

let readings = 
    seq [
        { Temperature = 89.5
          Timestamp = DateTime(2015, 07, 19, 10, 0, 0) }
        { Temperature = 90.1
          Timestamp = DateTime(2015, 07, 19, 10, 1, 0) }
        { Temperature = 89.9
          Timestamp = DateTime(2015, 07, 19, 10, 2, 0) }
        { Temperature = 90.0
          Timestamp = DateTime(2015, 07, 19, 10, 3, 0) }
        { Temperature = 90.1
          Timestamp = DateTime(2015, 07, 19, 10, 4, 0) }
        { Temperature = -1000.0
          Timestamp = DateTime(2015, 07, 19, 10, 5, 0) }
        { Temperature = -1000.0
          Timestamp = DateTime(2015, 07, 19, 10, 6, 0) }
        { Temperature = 90.2
          Timestamp = DateTime(2015, 07, 19, 10, 7, 0) }

Now to get all readings up until the thermometer returns the data-not-valid indicator, employ Seq.takeWhile:

let valid = 
    |> Seq.takeWhile (fun r -> r.Temperature <> -1000.0)

// val valid: seq<Reading> =
//   [{Temperature = 89.5;
//     Timestamp = 7/19/2015 10:00:00 AM};
//    {Temperature = 90.1;
//     Timestamp = 7/19/2015 10:01:00 AM};
//    {Temperature = 89.9;
//     Timestamp = 7/19/2015 10:02:00 AM};
//    {Temperature = 90.0;
//     Timestamp = 7/19/2015 10:03:00 AM};
//    {Temperature = 90.1;
//     Timestamp = 7/19/2015 10:04:00 AM}]

Finally, even though Seq.take throws an exception if you ask it for more elements than it can provide, Seq.takeWhile does not balk if it never reaches an element that fails to meet the predicate:

let all = seq [1;3;4;7]
          |> Seq.takeWhile (fun n -> n < 10)
// val all : seq<int> [1; 3; 4; 7]

As of F# 4.0, there are versions of takeWhile in the Array and List modules, but as of this writing, the documentation on MSDN does not yet include them.


F# Friday – The Seq.take and Seq.truncate Functions

Sometimes you have a collection of items, and you only want the first so many items. You may not know or even care what the first n items are, you just know that you want the first n items. Seq.take can do that for you.

To Infinity … and Beyond!

OK, it’s unusual that you just don’t care what items you get from a sequence, but there are occasions: for instance, random numbers. You really don’t care what the number is. You just don’t want it to be the same number every time, and perhaps you want it to fall within a certain range. Other than that, you don’t care: you just want a number!

let seed = System.DateTime.UtcNow.GetHashCode()
let rand = System.Random(seed)
let someNum = rand.Next()
// val someNum : int = 689587617  (well, this time anyway)

Now, assume that you have an application that needs a steady stream of random numbers. (Maybe even the number of random numbers you want is itself random!) Wouldn’t it be great to turn your random number into a sequence?

F# sequences are lazy data structures. That means that as you iterate over the sequence, it produces the next item on demand. It may not even have calculated what the next item is until you ask for it. In fact, sequences can be infinite! How do you have an infinite sequence? Well, back to the random number generator.

You can call rand.Next() until the cows come home and just keep getting values. Well, the Seq module gives us a way to turn rand (or any function that calculates a value from an input) into an infinite sequence—Seq.initInfinite:

let rands = Seq.initInfinite (fun _ -> rand.Next())

Seq.initInfinite takes a function that takes an integer and returns a value of the type you are interested in—an integer in this case. Now you can call Seq.take on rands, and get as many or as few values as you may want:

let taken = rands |> Seq.take 5
// val taken : 
//   seq [
//     974631199
//     1778702212
//     1311642930
//     1549454908
//     1138487539
//   ]

Additionally, F#’s sequence expressions allow you to create the infinite sequence of random numbers in what may be a slightly more readable fashion:

let rands = seq { while true do yield rand.Next() }
let taken = rands |> Seq.take 5
// val taken : 
//   seq [
//     1882861480
//     469452280
//     466017706
//     417690089
//     166247112
//   ]

Use whichever approach you find the more natural.

Going for the Gold

There are, of course, times when your data set is not infinite. You happen not to need all of them, but only the first few. I mentioned early on how that you may not know or care what the items are. A better way of saying it is that you (or someone) have likely already done the work to prepare the data set—processed it, sorted it, whatever. Now that you have done all that preprocessing, you want the first few items.

Perhaps you are writing software to determine the gold, silver, and bronze medal winners in the Olympic Games. You have a type representing each competitor:

type Competitor = {
    Name : string
    Score : float

You have the list of competitors for the 2012 men’s 110-meter hurdles, and they are already sorted according to ranking:

let competitors = 
    seq [
        { Name = "Aries MERRITT"; Score = 12.92 }
        { Name = "Jason RICHARDSON"; Score = 13.04 }
        { Name = "Hansle PARCHMENT"; Score = 13.12 }
        { Name = "Lawrence CLARKE"; Score = 13.39 }
        { Name = "Ryan BRATHWAITE"; Score = 13.40 }
        { Name = "Orlando ORTEGA"; Score = 13.43 }
        { Name = "Lehann FOURIE"; Score = 13.53 }

Now to get the medalists, take the first three records:

let medalists = competitors |> Seq.take 3
// val medalists: seq<Competitor> =
//   [
//     {Name = "Aries MERRITT"; Score = 12.92;}
//     {Name = "Jason RICHARDSON"; Score = 13.04;}
//     {Name = "Hansle PARCHMENT"; Score = 13.12;}
//   ]

Take It to the Limit

What happens, though, when you have a sequence with fewer items than you attempt to take?

let numbersOfTheCounting = seq [1;2;3] |> Seq.take 5
numbersOfTheCounting |> Seq.iter (printfn "%A")
// 1
// 2
// 3
// System.InvalidOperationException: 
//   The input sequence has an insufficient 
//   number of elements.

Oops! That’s not good! If you ask for more items than the sequence contains, you get an exception. I have to admit that I find this annoying. To me, Seq.take ought to return as many items as it can. If it should happen to contain fewer than you’ve asked for, oh well, no big deal; here are the ones it’s got. As a point of comparison, the take functions in Scala, Clojure, and Haskell all behave that way.

The good news is that there is an F# function that does behave that way: Seq.truncate. So if you want to use a function that’s a little more forgiving, just use Seq.truncate:

let numbersOfTheCounting = seq [1;2;3] |> Seq.truncate 5
numbersOfTheCounting |> Seq.iter (printfn "%A")
// 1
// 2
// 3

As of F# 4.0, there are versions of take and truncate in the Array and List modules, but as of this writing, the documentation on MSDN does not yet include them.


F# Friday – The List.append Function

Occasionally, you need to combine two lists (or arrays or sequences) into one. List.append to the rescue! (Along with Array.append and Seq.append.)

A widow Carol has three daughters: Marcia, Jan, and Cindy.

let ladies = ["Carol"; "Marcia"; "Jan"; "Cindy"]

A widower Mike has three sons: Greg, Peter, and Bobby.

let fellas = ["Mike"; "Greg"; "Peter"; "Bobby"]

That lovely lady meets that fellow, and they know it is much more than a hunch. They marry and form a family:

let bunch = List.append ladies fellas
// val bunch : string list =
//   ["Carol"; "Marcia"; "Jan"; "Cindy";
//    "Mike"; "Greg"; "Peter"; "Bobby"]

Of course, as you probably have guessed, order matters. Let’s reverse the arguments:

let bunch2 = List.append fellas ladies
// val bunch2 : string list =
//   ["Mike"; "Greg"; "Peter"; "Bobby";
//    "Carol"; "Marcia"; "Jan"; "Cindy"]

A note of caution: Idiomatic F# takes heavy advantage of the forward pipeline operator (|>). It may be tempting to do this, but watch out:

let yikes = [1; 2]
            |> List.append [3; 4]
// val yikes : int list = [3; 4; 1; 2]

Probably not what you wanted. This is one of those situations when the backward pipeline operator (<|) can step in to help you preserve readability:

let inOrder = [1; 2]
              |> List.append <| [3; 4]
// val inOrder : int list = [1; 2; 3; 4]

And you can even continue fluidly applying additional operations:

let inOrderAndTrebled = [1; 2]
                        |> List.append <| [3; 4]
                        |> ((*) 3)
// val inOrderAndTrebled : int list = [3; 6; 9; 12]

Update: Thanks to Isaac Abraham for reminding me that there is a list concatenation operator (@), so this works and is nicely readable, too:

let concatenated = [1; 2] @ [3; 4]
// val concatenated : int list = [1; 2; 3; 4]

Note that @ works for lists only, not sequences or arrays.


F# Friday – Pattern Matching, Part 4: Active Patterns

Active patterns and partial active patterns round out the F# developer’s toolbox for pattern matching.

These Patterns Are Highly Active

An active pattern allows you to define a set of named cases that you can use in your pattern matching expressions. The active recognizer, the type of function that defines active patterns, encapsulates pattern matching logic and associates it with the case name(s). The advantage is that you can give a readable name to a case that effectively communicates the nature of the match, but hide some of the clutter that can threaten the readability of your code.

A classic example is determining whether an integer is even or odd. Now you could do that this way:

match n % 2 with
| 0 -> n, "even"
| _ -> n, "odd"

Now n % 2 is a simple expression, and its use common enough in computer science that most of us recognize right away, whenever we see it, “Oh, right, even or odd.” But there is just the slightest context switch between thinking mathematically and thinking conceptually, i.e., determining intent. And that context switch slows us down. A more complex expression can slow us down even more.

Compare the above (admittedly simple) match expression to what you can do with an active pattern. First, define the active pattern this way:

let (|Even|Odd|) n =
    match n % 2 with
    | 0 -> Even
    | _ -> Odd

Where you usually give a name to the function, you now have a set of pipe-delimited names between what are known as banana clips (| |). Those names are case names that you will be able to use in match expressions. Finally, in the body of the active recognizer, you define a return path for each case name.

Now after defining the active pattern, you can use it in a match expression like this:

let oddOrEven n =
    match n with
    | Even -> n, "even"
    | Odd -> n, "odd"

seq { 1..10 }
|> oddOrEven
|> Seq.iter (printfn "%O")
// (1, odd)
// (2, even)
// (3, odd)
// (4, even)
// (5, odd)
// (6, even)
// (7, odd)
// (8, even)
// (9, odd)
// (10, even)

Look at the difference in readability. There is no context switch. It reads much smoother than the original match expression. You can see that oddOrEven takes a value, n, and returns a result based on whether n is even or odd. You don’t have to leave the realm of the conceptual to think mathematically and then turn right back around to think conceptually again.

A point of emphasis: When defining an active pattern, you need to cover all the bases and define a return condition for every case. (In that regard, an active pattern is something like an algebraic data type.) That is easy for the even/odd test: There are only two cases.

But what if there are several cases? Take the wavelengths of colors in the spectrum of visible light. Each color corresponds to a range of wavelengths:

Color Wavelength Ranges
Color Wavelength
Red 620–750 nm
Orange 590–620 nm
Yellow 570–590 nm
Green 495–570 nm
Blue 450–495 nm
Violet 380–450 nm

No problem, right? Just define a quick little active pattern:

let (|Red|Orange|Yellow|Green|Blue|Violet|) λ =
    match λ with
    | x when 620 <= x && x < 750 -> Red
    | x when 590 <= x && x < 620 -> Orange
    | x when 570 <= x && x < 590 -> Yellow
    | x when 495 <= x && x < 570 -> Green
    | x when 450 <= x && x < 495 -> Blue
    | x when 380 <= x && x < 450 -> Violet

But wait! The compiler tells you, “Incomplete pattern matches on this expression.” That is because there is radiation outside the visible spectrum; λ could be greater than 750 nm or less than 380 nm. You therefore need a catch-all case to cover the values that are outside the explicit cases:

let (|Red|Orange|Yellow|Green|Blue|Violet|Invisible|) λ =
    match λ with
    | x when 620 <= x && x < 750 -> Red
    | x when 590 <= x && x < 620 -> Orange
    | x when 570 <= x && x < 590 -> Yellow
    | x when 495 <= x && x < 570 -> Green
    | x when 450 <= x && x < 495 -> Blue
    | x when 380 <= x && x < 450 -> Violet
    | _ -> Invisible

Now you can use the active pattern like this:

let colorOfLight λ =
    match λ with
    | Red -> (sprintf "%d nm" λ), "red"
    | Orange -> (sprintf "%d nm" λ), "orange"
    | Yellow -> (sprintf "%d nm" λ), "yellow"
    | Green -> (sprintf "%d nm" λ), "green"
    | Blue -> (sprintf "%d nm" λ), "blue"
    | Violet -> (sprintf "%d nm" λ), "violet"
    | Invisible -> (sprintf "%d nm" λ), "invisible"

seq [800; 700; 600; 580; 500; 475; 400; 350]
|> colorOfLight
|> Seq.iter (printfn "%O")
// (800 nm, invisible)
// (700 nm, red)
// (600 nm, orange)
// (580 nm, yellow)
// (500 nm, green)
// (475 nm, blue)
// (400 nm, violet)
// (350 nm, invisible)

One final word before moving on: There is a limit to the number of cases in an active pattern. It can contain no more than seven cases. Your spectrum-of-light active pattern just so happens to go right up to that limit. If, for instance, you had needed to account for an indigo band of wavelengths between blue and violet, you would have had to take a different approach.

Active In Part

A partial active pattern is similar to an active pattern, but it does not cover the entire input domain. If the input meets the criteria sought, you return the case name in a Some. If not, you return a None.

Perhaps you are a clerk in a department store. You recommend that customers who are at least 6′ (72 inches) tall and have at least a 40-inch waist go to the Big & Tall section. Others you greet according to their proportions.

First, define a Measurements type:

type Measurements = {
    Height : int
    Waist : int

Then define partial active patterns: one to detect whether a customer meets the “big” criterion and another to detect whether he meets the “tall” criterion.

let (|Big|_|) (m : Measurements) =
    if m.Waist >= 40 then Some Big else None
let (|Tall|_|) (m : Measurements) =
    if m.Height >= 72 then Some Tall else None

Now that you have the patterns defined, you can use them in a match expression:

let sizeUp m =
    match m with
    | Big & Tall -> 
        "Let me show you to the big & tall section"
    | Big -> 
        "Big fella, ain'tcha?"
    | Tall -> 
        "How's the weather up there?"
    | _ -> 
        "May I help you, sir?"

Notice how you can use partial active patterns together and by themselves. Now you run some customers through the sizeUp function:

let me = { Height = 76; Waist = 36 }
let shrimp = { Height = 58; Waist = 28 }
let hoss = { Height = 80; Waist = 46 }
let tubby = { Height = 63; Waist = 42 }

seq [me; shrimp; hoss; tubby]
|> sizeUp
|> Seq.iter (printfn "%s")
// How's the weather up there?
// May I help you, sir?
// Let me show you to the big & tall section
// Big fella, ain'tcha?

Parameterizing on the Fly

Finally, active patterns may accept more than just the one parameter they test against. They can accept additional parameters in order to configure or modify their behavior.

You have a list of test scores, and you want to convert each to a letter grade. You can start by defining the partial active pattern AtLeast that takes a number, n, and returns a match only if evaluated against a score that is greater than or equal to n:

let (|AtLeast|_|) n score =
    if score >= n then Some AtLeast else None

Now build a grade function using AtLeast:

let grade =
    | AtLeast 90 -> "A"
    | AtLeast 80 -> "B"
    | AtLeast 70 -> "C"
    | AtLeast 60 -> "D"
    | _ -> "F"

Just a reminder that order matters in match expressions. If you had put the AtLeast 60 match case before the AtLeast 90 match case, then AtLeast 90 would never match. AtLeast 60 would always match first.

Evaluating a list of scores is now straightforward:

seq [95; 31; 72; 67; 89]
|> (fun n -> n, grade n)
|> Seq.iter (printfn "%O")
// (95, A)
// (31, F)
// (72, C)
// (67, D)
// (89, B)

F# Friday – Pattern Matching, Part 3: Discriminated Unions

Another tool in the pattern matching utility belt is discriminated unions. A discriminated union is a type that contains a small number of union cases. Each union case is treated as the same type as the discriminated union, but each case may comprise a different set of properties.

Discriminating Tastes

You could use a discriminated union to represent the different cast type options when opening a socket to send UDP packets: broadcast, unicast, and multicast. If you are opening a socket to broadcast, you only need a port number. If you are opening a socket to unicast, you also need the IP address of the machine you are unicasting to. Finally, if you are opening a socket to multicast, you need an IP address (the multicast group), a port number, and optionally the ID of a network interface card if you want to target a specific network interface.

type SocketMeta =
| Broadcast of Port : int
| Unicast of Addr : IPAddress * Port : int
| Multicast of Addr : IPAddress * Port : int * 
               NicId : string option

Each case can have any number of properties. If there is more than one property, chain them together with tuple syntax using the asterisk (*).

Now it’s easy to write a function to build a socket based on the meta information:

let buildSocket meta =
    match meta with
    | Broadcast port ->
        // configure for broadcast
    | Unicast(ip, port) ->
        // configure for unicast
    | Multicast(ip, port, nic) ->
        // configure for multicast

let addr = IPAddress.Parse("")
let s = buildSocket (Unicast (addr, 5150))

Discriminated unions are good for times when the number of cases is small, and the number of properties in each case is small. For instance, you have likely worked with a particular discriminated union type many times. Option is essentially this:

type Option<'T> =
| None
| Some of 'T

Option is either some value or nothing at all; that’s it. There is no third alternative. It is very easy to cover all the bases in a fairly short block of code.

Option also illustrates a couple of additional things about discriminated unions. First, union cases need not have any properties at all. None stands alone; it requires no properties. Second, naming the properties is optional. Some is so semantically clear, there is no need to give its single property a name. A type (which happens to be generic in the case of Option) is always required, but not a name.

Typing Lesson

It turns out that discriminated unions are a specific example of a more general kind of type: an algebraic data type. An algebraic data type is a composite type; that is, it is a combination of other types. An algebraic data type may comprise an infinite set of types or a finite set.

SocketMeta and Option both clearly consist of a finite number of types—a small finite number at that. As mentioned already, that’s what makes them so well suited to match expressions.


F# Friday – Pattern Matching, Part 2: Record Types

In addition to classes, F# also provides record types. They offer a few benefits that standard classes do not.

Getting Personal

Defining a record type is straightforward:

type Person = { First : string; Last : string }

Person has two fields, First and Last, both of type string. Defining a Person variable is easy:

let me = { First = "Brad"; Last = "Collins" }

Pattern matching on record objects is pretty straightforward, too:

let greet = 
    | { First = "Brad"; Last = "Collins" } ->
        "It's me!"
    | { First = "Brad" } -> "Nice name"
    | { Last = "Collins" } -> "Greetings, kinfolk"
    | _ -> "Hello, stranger"

let me = { First = "Brad"; Last = "Collins" }
let kin = { First = "Shad"; Last = "Collins" }
let namesake = { First = "Brad"; Last = "Rollins" }
let stranger = { First = "Ezra"; Last = "Shemiah" }

let meGreeting = greet me
// val meGreeting : string = "It's me!"

let kinGreeting = greet kin
// val kinGreeting : string = "Greetings, kinfolk"

let namesakeGreeting = greet namesake
// val namesakeGreeting : string = "Nice name"

let strangerGreeting = greet stranger
// val strangerGreeting : string = "Hello, stranger"

First, notice that you do not have to tell greet what kind of record type you want to match on. F# infers it.

Next, to match on a Person record with specific First and Last fields, specify both of them, as in the first match case above. To match on just one field, either First or Last, specify the field to match, and use the wildcard pattern, the underscore (_), for the field you don’t care about, as in the second and third match cases above. If Person had more than two fields, you could match any subset of them by specifying the field values you need to be exact and using the wildcard pattern for the fields you don’t.

One other thing to note here: Order matters. What if you had defined greet this way?

let greet = 
    | { First = "Brad" } -> "Nice name"
    | { Last = "Collins" } -> "Greetings, kinfolk"
    | { First = "Brad"; Last = "Collins" } ->
        "It's me!" // OOPS!
    | _ -> "Hello, stranger"

The third case (lines 5 and 6 above) would never match because { First = "Brad"; Last = "Collins" } would always match the first case. So, pay attention out there.

Personal Improvement

As with classes, we can extend record types with member functions and properties:

type Person = { 
    First : string
    Last : string
    static member Anonymous = { First = ""; Last = "" }
    static member Create first last = 
        { First = first
          Last = last }
    member x.Swap () = Person.Create x.Last x.First

let me = Person.Create "Brad" "Collins"
// val me : Person = {First = "Brad";
//                    Last = "Collins";}

let swapped = me.Swap()
// val swapped: Person = {First = "Collins";
//                        Last = "Brad";}

This example also demonstrates one of the extras you get with record types: A ToString() implementation. With a regular class, if you want ToString() to show you something more descriptive than a type name, you have to overload System.Object.ToString() yourself.

Record types also throw in implementations of Equals(o) and GetHashCode() for no charge:

let me = Person.Create "Brad" "Collins"
let swapped = me.Swap()
let myself = Person.Create "Brad" "Collins"

let iAm = me = myself
// val iAm : bool = true

let iAint = me = swapped
// val iAint : bool = false

let meHash = me.GetHashCode()
// val meHash : int = 1825427853

let myselfHash = myself.GetHashCode()
// val myselfHash : int = 1825427853

let swappedHash = swapped.GetHashCode()
// val swappedHash : int = 39593589

Notice how me and myself are equal though they are different object instances, and they also have the same hash code.

Finally, if you have a record instance and need a new instance with, say, only one or two field values that are different, F# provides a way to do that using the with keyword so that you don’t have to set every field value explicitly:

let me = Person.Create "Brad" "Collins"
let kin = { me with First = "Shad" }
// val kin : Person = {First = "Shad";
//                     Last = "Collins";}

let namesake = { me with Last = "Rollins" }
// val namesake : Person = {First = "Brad";
//                          Last = "Rollins";}

Identity Crisis

But what happens when you have two record types that coincidentally have the same members? Maybe you have a type representing polar coordinates type and a type representing an arc. Both of them contain a radius member, R, and an angle member, Θ:

type Polar = { R : float; Ï´ : float }
type Arc = { R : float; Ï´ : float }

What happens when you want to calculate the length of an arc, and you want to constrain arcs to “valid” angles, that is, between zero and a whole circle, nothing more than a circle or negative?

let π = System.Math.PI

let length arc =
    match arc with
    | { ϴ = a } when a < 0.0 || (2.0 * π) < a ->
        raise <| System.ArgumentException "Ï´ is out of range"
    | { R = radius; Ï´ = angle } -> radius * angle

F# yields a warning:

The field labels and expected type of this record expression or pattern do not uniquely determine a corresponding record

In other words, F# doesn’t know whether you want to match on a Polar object or an Arc object. You can fix this a couple of ways. One way is to specify the type of the arc parameter:

let π = System.Math.PI

let length (arc : Arc) =
    match arc with
    | { ϴ = a } when a < 0.0 || (2.0 * π) < a ->
        raise <| System.ArgumentException "Ï´ is out of range"
    | { R = radius; Ï´ = angle } -> radius * angle

let quarter = { R = 2.5; Ï´ = (Ï€ / 2.0) }
let len = length quarter
// val len : float = 3.926990817

Another option is to prepend the Θ field in the match expression with the Arc type:

let π = System.Math.PI

let length arc =
    match arc with
    | { Arc.ϴ = a } when a < 0.0 || (2.0 * π) < a ->
        raise <| System.ArgumentException "Ï´ is out of range"
    | { R = radius; Ï´ = angle } -> radius * angle

let quarter = { R = 2.5; Ï´ = (Ï€ / 2.0) }
let len = length quarter
// val len : float = 3.926990817

Similarly, to remove any ambiguity when creating a record instance, prepend the type name to the beginning of one of the field names:

let π = System.Math.PI

let arc = { Arc.R = 2.5; Ï´ = (Ï€ / 2.0) }
let polar = { Polar.R = 1.75; ϴ = (1.25 * π) }

F# Friday – Pattern Matching, Part 1

A terribly useful technique in functional programming is pattern matching. Pattern matching is simply a form of conditional logic, like an if-else expression or (in other languages) a switch statement, but quite a bit more powerful and flexible. With pattern matching, you can perform matches and take action based on simple values, such as integers, but also on complex types and the values of their members. Here are some examples using the simpler types, and a future post(s) will illustrate how to match on more complex types.

On the Whole (Numbers)

Pattern matching on integers is very straightforward. Just use literals:

let getResponse talents =
    match talents with
    | 5 -> "Here are your five talents plus five more"
    | 2 -> "Here are your two talents plus two more"
    | 1 -> "Here is your one talent, which I hid"
    | _ -> "Uh, wrong story"

let response = getResponse 5
// val response : string = 
//   "Here are your five talents plus five more"

let apocryphal = getResponse 42
// val apocryphal : string = "Uh, wrong story"

Of course, the set of all possible integers is very large. Our example here only covers three specific values: 1, 2, and 5. To cover every other case that you don’t specify explicitly, use the wildcard pattern _, the underscore. That’s how we could handle 42. Or 103. Or −7. Or any other integer.

Getting to the (Floating) Point

Floating point numbers are difficult to pin down because of the margin of error, so you don’t typically match on a specific number. Usually you match on ranges. Pattern matching allows for that, too:

let getState temp =
    match temp with
    | x when x <= 32.0 -> "solid"
    | x when x >= 212.0 -> "gas"
    | _ -> "liquid"

let atRoomTemp = getState 70.0
// val atRoomTemp : string = "liquid"

let atSouthPole = getState -70.6
// val atSouthPole : string = "solid"

Putting a condition on a match with the when keyword like that is called a guard. Guards are simply Boolean expressions. You could alternatively write the “liquid” step in getState with a compound Boolean expression:

let getState2 temp =
    match temp with
    | x when 32.0 > x && x < 212.0 -> "liquid"
    | x when x >= 212.0 -> "gas"
    | _ -> "solid"
let onHotSummerDay = getState2 98.5
// val onHotSummerDay : string = "liquid"

In one more rewrite of getState, note that it is possible to use variables, not just literals, in guards:

let getState3 temp =
    let freezingPoint = 32.0
    let boilingPoint = 212.0
    match temp with
    | x when x <= freezingPoint -> "solid"
    | x when x >= boilingPoint -> "gas"
    | _ -> "liquid"
let inDeathValley = getState3 134.0
// val inDeathValley : string = "liquid"

Stringly Typed Interfaces

Perhaps your application executes commands, and those commands are specified by names, that is, strings. (Some folks jokingly call them “stringly typed interfaces.”) Pattern matching is perfect for this task:

let execute command id value =
    let v = defaultArg value ""
    match command with
    | "add" -> sprintf "Added %d: %s" id v
    | "remove" -> sprintf "Removed %d" id
    | "update" -> sprintf "Updated %d: %s" id v
    | _ -> sprintf "Illegal command: %s" command

let added = execute "add" 42 (Some "foo")
// val added : string = "Added 42: foo"

let removed = execute "remove" 42 None
// val removed : string = "Removed 42"

let updated = execute "update" 42 (Some "bar")
// val updated : string = "Updated 42: bar"

let wowbanged = execute "wowbang" 73 None
// val wowbanged : string = "Illegal command: wowbang"

Perhaps you want to allow some flexibility in your command names. For example, another name for “add” could be “create.” Pattern matching expressions allow you to stack multiple conditions for which you want to take the same action:

let execute2 command id value =
    let v = defaultArg value ""
    match command with
    | "create"
    | "add" -> sprintf "Added %d: %s" id v
    | "delete"
    | "remove" -> sprintf "Added %d" id
    | "change"
    | "update" -> sprintf "Added %d: %s" id v
    | _ -> sprintf "Illegal command: %s" command
let created = execute2 "create" 84 (Some "baz")
// val created : string = "Added 84: baz"

Here Are Your Options

Perhaps you have a user variable that is a string option. If the user is logged in, user is a Some; otherwise the user is an unauthenticated guest. You’d like to generate a greeting based on whether the user is logged in or not:

let greet user =
    match user with
    | Some name -> sprintf "Welcome back, %s!" name
    | None -> "Hello, dear guest! Please sign in!"

let personal = greet (Some "bcollins")
// val personal : string = "Welcome back, bcollins!"

let generic = greet None
// val generic : string = 
//   "Hello, dear guest! Please sign in!"

Notice how the match expression can, in the case of the Some, unpack the value for you and assign it to a variable, name in this case. You don’t have to do it yourself.

Now given that Option is a binary choice, you may be tempted to think that an if-else block is probably a better, um, option. In some simple cases it may be, but in this case, you want to generate a message that differs by more than just the username. Look at what it takes to get the same results with an if-else block as the match expression above:

let greet2 user =
    if Option.isSome user then
        let name = Option.get user
        sprintf "Welcome back, %s!" name
        "Hello, dear guest! Please sign in!"

Now that’s not too bad, but compare that to the original version that uses the match expression. The match expression is just cleaner: It is very easy to see what the conditions are, and you don’t have to clutter the code by unpacking the Some value yourself.

Bearing with the Tuples of the Week

Pattern matching expressions can unpack tuples so that you can match on all values or individual values:

let getProducer chars =
    match chars with
    | ("Tom", "Jerry") -> "Hanna-Barbera"
    | ("Bugs", "Daffy") -> "Warner Brothers"
    | ("Mickey", _) -> "Disney"
    | (x, "Buzz") -> sprintf "Pixar with %s and Buzz" x
    | _ -> "other"

let prod = getProducer ("Tom", "Jerry")
// val prod : string = "Hanna-Barbera"

let prod2 = getProducer ("Mickey", "Minnie")
// val prod2 : string = "Disney"

let prod3 = getProducer ("Mickey", "Donald")
// val prod3 : string = "Disney"

let prod4 = getProducer ("Woody", "Buzz")
// val prod4 : string = "Pixar with Woody and Buzz"

let prod5 = getProducer ("Andy", "Buzz")
// val prod5 : string = "Pixar with Andy and Buzz"

let prod6 = getProducer ("Ren", "Stimpy")
// val prod6 : string = "other"

As you can see in the “Disney” line, you don’t care what the second element of the tuple is, so you throw it away with the wildcard pattern. On the other hand, on the “Pixar …” line, you want to capture the first element in the matched tuple and use it in the result. So you just give it a variable name, and the compiler assigns the value to the variable for you, just like with Some name above.

What’s Your Type?

Finally, pattern matching expressions can match even on different types and take action based on the type of the input:

let report (guests : obj) =
    match guests with
    | :? string as guest -> 
        sprintf "Our guest: %s" guest
    | :? (string array) as all -> 
        (all |> String.concat ", ")
        |> sprintf "Our guests: %s"
    | :? int as count -> 
        sprintf "We have %d guests" count
    | _ -> "Huh?"

let one = report "Brad"
// val one : string = "Our guest: Brad"

let many = report [|"Me"; "Myself"; "I"|]
// val many : string = "Our guests: Me, Myself, I"

let count = report 13
// val count : string = "We have 13 guests"

let stumped = report 3.14
// val stumped : string = "Huh?"

As you can see, you can choose from any number of types to match on and take action accordingly. Note that if the input argument does not contain a type annotation, such as (guests : obj) above, the compiler refuses to compile.


F# Friday – The Set.difference Function

Sometimes you have two sets of information, and you want to know what is in one set that the other set lacks. You want to perform a set difference operation.

What’s the Difference?

Given two sets, A and B, the difference between A and B—the items in A that are not in B—is written as follows:

A \ B

Likewise, the difference in B and A—the items in B that are not in A—is written vice versa:

B \ A

Set operations are frequently easiest to convey with a diagram:

An illustration of two sets, A and B, represented as two filled circles that are slightly overlapping. The difference (A \ B) is the part of set A not overlapping set B. The difference (B \ A) is the part of set B not overlapping set A.
The Difference in Two Sets A and B

It’s worth noting that a set difference operation is like arithmetic subtraction in that it matters which operand comes first. That is …

A \ B ≠ B \ A

White & nerdy mathematicians say that the set difference operation does not commute.

Always Never the Same

Continuing with my penchant for using band lineups as examples, put the original lineup of the band Kansas in one set and the current lineup in another:

let original =
    set ["Walsh"; "Livgren"; "Williams";
         "Steinhardt"; "Hope"; "Ehart"]
let current = 
    set ["Platt"; "Manion"; "Williams";
         "Ragsdale"; "Greer"; "Ehart"]

To get the original members no longer with the band, use the Set.difference function to take the difference in the original lineup and the current:

let departed = Set.difference original current
// val departed : Set<string> =
//   set ["Hope"; "Livgren"; "Steinhardt"; "Walsh"]

To get the current members who were not in the original lineup, do the opposite—take the difference in the current lineup and the original:

let noobs = Set.difference current original
// val noobs : Set<string> = 
//   set ["Greer"; "Manion"; "Platt"; "Ragsdale"]

How ’bout that! Simple enough, I suppose, but seeing as set difference is a whole lot like arithmetic subtraction, wouldn’t it be really nice if we could express our set difference operations just like we do arithmetic subtraction?

A − B

Good news: You can! F# defines a minus operator so that we can do exactly that:

let departed = original - current
let noobs = current - original
// val departed : Set<string> = 
//   set ["Hope"; "Livgren"; "Steinhardt"; "Walsh"]
// val noobs : Set<string> = 
//   set ["Greer"; "Manion"; "Platt"; "Ragsdale"]

F# Friday – The Option Type, Part 3

One more word on the Option type. While Option allows you a more type-safe alternative to nulls, it does not itself handle nulls. In other words, this …

let s = Some null

… gets you a Some containing a null. That doesn’t help so much if our aim is to get away from null, not kick it down the road.

The Java Way

In version 8, Java introduced its own Optional type, no doubt inspired by the Option and Maybe types available in the functional languages. It does handle nulls. Take the following classes as examples:

public class User {
  private String username;
  private String name;
  public User(String username) { this(username, null); }
  public User(String username, String name) {
    this.username = username; = name;
  public String getUsername() { return username; }
  public String getName() { return name; }

public class Session {
  private User user;
  public Session() { this(null); }
  public Session(User u) { this.user = u; }
  public User getUser() { return user; }

public class Application {
  private Session session;

  public Application() { this(null); }
  public Application(Session s) { this.session = s; }
  public Session getSession() { return session; }

Because Optional handles null in its map operation, this works:

Application app = new Application(new Session());
String name = Optional.of(app)
// name = "n/a"

In our example, the Session has a null User property. But that’s OK, because the map operation on line 4 (highlighted above) takes that null and converts it to a None, or more accurately, an Empty per Java parlance.

Back in .NET Land

We cannot do quite the same thing in F#. Now we, as enlightened F# developers, would never code up something that uses nulls all over the place like the Java classes above. But the C# world is more comfortable with nulls, so let’s say that you are working with a C# library that contains the analogs to the Java classes above:

public class User
    public string Username { get; private set; }
    public string Name { get; private set; }

    public User(string username, string name = null)
        Username = username;
        Name = name;

public class Session
    public User User { get; private set; }

    public Session(User u = null) { User = u; }

public class Application
    public Session Session { get; private set; }

    public Application(Session s = null) { Session = s; }

You pull that library into your F# project and write something like this:

let app = Application(Session())
let name =
    Some app
    |> (fun a -> a.Session)
    |> (fun s -> s.User)
    |> (fun u -> u.Name)
    |> defaultArg <| "n/a"
// NullReferenceException!!!

But that breaks down pretty quickly. Line 5 (highlighted above) yields an exception because s.User is null. in F# does not convert a null to a None. So then, what do we do?

Well, if you’re using F# 4.0, there is something new to the Option module: Option.ofObj. It is essentially a named constructor for Option. It takes an object reference and returns a None if it is a null, or a Some if it is not. Also, remember that Option.bind takes an operation that returns an Option and flattens it so that it does not return a nested Option, but just an Option. Therefore, you can change your code to this:

let app = Application(Session())
let name = 
    Some app
    |> Option.bind (fun a -> Option.ofObj a.Session)
    |> Option.bind (fun s -> Option.ofObj s.User)
    |> Option.bind (fun u -> Option.ofObj u.Name)
    |> defaultArg <| "n/a"
// name : string = "n/a"

It’s a bit more headache than you’d like, but that’s what you get for using flaky C# code, right?

If you’re not using F# 4.0 yet, then you can write a little utility function to do the same job:

let nullToOption = function 
                   | null -> None
                   | x -> Some x

let app = Application(Session())
let name = 
    Some app
    |> Option.bind (fun a -> nullToOption a.Session)
    |> Option.bind (fun s -> nullToOption s.User)
    |> Option.bind (fun u -> nullToOption u.Name)
    |> defaultArg <| "n/a"
// name : string = "n/a"

F# Friday – The Option Type, Part 2

Last week we introduced the Option type as a way of representing when a function may or may not return a value.

A Collection of One

Another way to think about an Option is as a collection that contains no more than one element. Consequently, the Option module provides some collection-like semantics, e.g., fold, map, exists, and even filter in F# 4.0. This allows us to chain operations together without having to check at each step whether the value is Some or None. We can put that off until the end of the sequence of operations and only do the check once. That way, the algorithm is more readable; it’s not cluttered with a bunch of if-else noise.

Say that you have a User type:

type User(id : string, name : string) =
    member x.Id = id
    member x.Name = name

Let’s say that your system is a website. In the top, right corner of the site, you want to display the name of the user who is currently logged in. You need a function that returns the user currently signed in:

let authenticatedUser : unit -> User option = // ...

Now why would this function return an Option? Well, the user browsing your site may not have logged in at this point. If that’s the case, then the current user is None. So then, the code to get the name of the current user is this:

let nameOpt = authenticatedUser()
              |> (fun u -> u.Name)
// val nameOpt : string option

Notice how the type of nameOpt is string option. In other words, assuming that authenticatedUser() returns a Some<User>, F# knows that the User.Name property is a string. Nevertheless it propagates the uncertainty, if you will, along through the map operation. Any operations you do on an Option only happen if the Option is a Some. Otherwise, F# happily ignores the operation and continues to propagate the None.

OK, so now that we have a final result Option, what do we do with it? That’s where defaultArg comes in:

let name = defaultArg nameOpt "Guest"
// val name : string

If nameOpt is a Some, name is the value in the Some. If nameOpt is a None, then name is "Guest". You can test both cases in the F# REPL. To see it work in the case of a Some:

let authenticatedUser : unit -> User option =
    fun () -> Some(User("bcollins", "Brad Collins"))
let nameOpt = authenticatedUser()
              |> (fun u -> u.Name)
// val nameOpt : string option = Some "Brad Collins"
let name = defaultArg nameOpt "Guest"
// val name : string = "Brad Collins"

And then to see it with a None:

let authenticatedUser : unit -> User option =
    fun () -> None
let nameOpt = authenticatedUser()
              |> (fun u -> u.Name)
// val nameOpt : string option = None
let name = defaultArg nameOpt "Guest"
// val name : string = "Guest"

Unraveling the Options

Remember how the collections modules define the collect function? For instance, this is the List.collect() function:

List.collect : ('T -> 'U list) -> 'T list -> 'U list

It’s like map, but collect takes a transformation function that takes an element and returns a list of values rather than just a single value. Then instead of returning a list of lists, collect flattens them into a single list.

Option has a similar function: bind. The bind operation takes a function that returns an Option and, instead of returning a nested Option (i.e., an Option<Option<'U>>, it just returns an Option<'U>:

Option.bind : ('T -> 'U option) -> 'T option -> 'U option

Maybe instead of having an authenticatedUser() function, your app just has a Session property. To get the name of the current user, you have to walk the property tree from the application to the session to the user and then finally the name. App.Session is an Option to indicate that there may be no valid session. Session.User is an Option to indicate that there may be no user signed in. Finally, maybe we don’t even force a user to have a name, just a user ID:

type User(id : string, name : string option) =
    new(id : string) = User(id, None)
    member x.Id = id
    member x.Name = name
type Session(user : User option) = 
    new() = Session(None)
    member x.User = user
type App(session : Session option) =
    new() = App(None)
    member x.Session = session

You walk the property tree like this:

let nameOpt = app.Session
              |> Option.bind (fun s -> s.User)
              |> Option.bind (fun u -> u.Name)
let name = defaultArg nameOpt "Guest"

Now if any property is None, from Session to User to Name, nameOpt is None, and name is "Guest".