Tag: F#

It’s like that time you played basketball in the living room. You knew you should never have done it. But it was just so tempting! And how did that work out for you? Broken lamp? Hole in the wall? And, if you grew up in a house like mine, a tanned hide to follow. You could have avoided it all: the property damage, the wounded pride, the tender backside.

That’s what playing with null is like. You know you shouldn’t, but it’s just so easy! Then you get burned in the end.

The Problem with Null

The problem with null is that it can crop up anywhere an object can. Consider a function that returns a string. This is always OK, right?

let foo : unit -> string = // ...
let len = foo().Length // No worries?

It certainly is in this case:

let foo : unit -> string = fun () -> "foo"
let len = foo().Length
// val len : int = 3

But what about this?

let foo : unit -> string = fun () -> null
let len = foo().Length
// System.NullReferenceException:
//   Object reference not set to an instance 
//   of an object.

Yeah, not so much. And the problem is that the compiler cannot help us: null is a perfectly legal return value.

We need better semantics! A return type of string ought to guarantee me that I get a string. An empty string would be fine; it just needs to be a string!

Even the guy who invented the concept of null has regretted it:

I call it my billion-dollar mistake. It was the invention of the null reference in 1965. At that time, I was designing the first comprehensive type system for references in an object oriented language (ALGOL W). My goal was to ensure that all use of references should be absolutely safe, with checking performed automatically by the compiler.

But I couldn’t resist the temptation to put in a null reference, simply because it was so easy to implement. This has led to innumerable errors, vulnerabilities, and system crashes, which have probably caused a billion dollars of pain and damage in the last forty years.

Sir Charles Antony Richard “Tony” Hoare
Turing Award Winner, Inventor of the Quicksort
Null References: The Billion Dollar Mistake (2009)

Fine! All this lamenting that null is a bad idea is great, but don’t you need a way to represent the idea that sometimes a function may not return a result, or at least, not what you would consider a valid result? That’s what Java does: If you call Map.get(key), and that map does not contain an entry for key, you get null. As we saw couple of weeks ago, F#’s List.find (and the other collections’ find functions, too) is not any more elegant: It throws an exception!

There’s got to be a better way!

Option to the Rescue

When you need to represent the idea that a function may not return a result, use F#’s Option. You can think of an Option as a bucket (pronounced BUCK-et, not boo-KAY):

When a function returns an Option<'T>, it may contain a value of type T; it may not. You don’t know until you look into it. It’s Schrödinger’s cat! If the Option is empty, we call it None. If it is full, we call it Some.

The advantage of using Option is that now the compiler can help you out. You cannot assign an Option<'T> to a variable of type T. Take this example using List.tryFind:

let opt = [1..4] |> List.tryFind (fun n -> n > 5)
let n : int = opt
//   let n : int = opt;;
//   --------------^^^
// 
// This expression was expected to have type
//     int    
// but here has type
//     int option

So then, you cannot forget and accidentally assign a null, only to have it bite you later. The compiler reminds you that you need to test the result before trying to use it:

let ns = [1..4]

let none = ns |> List.tryFind (fun n -> n > 5)
if none.IsSome then
    printfn "Found one greater than 5: %d" none.Value
else
    printfn "None found greater than 5"
// None found greater than 5

let some = ns |> List.tryFind (fun n -> n < 5)
if some.IsSome then
    printfn "Found one less than 5: %d" some.Value
else
    printfn "None found less than 5"
// Found one less than 5: 1

Of course, you can override the safeguard, but at least then, you cannot claim ignorance:

let ns = [1..4]
let none = ns |> List.tryFind (fun n -> n > 5)
printfn "Found one greater than 5: %d" none.Value
// System.NullReferenceException:
//   Object reference not set to an instance 
//   of an object.

Next week, we will look at Option some more to see how we can use it in a more functional fashion.

The filter function takes a collection and a predicate and returns only the items in a collection that meet the predicate. It discards the ones that don’t.

Well, what if you want to retain all the items in the collection, but you just want them separated into two groups–the sheep from goats, as it were? That’s where partition comes in. The partition operation takes a collection and a predicate, just as filter does, but instead of tossing the items that don’t meet the predicate, partition returns a second collection along with the first: one containing all the items that meet the predicate and one containing all the rest.

Maybe you run a business, and once per quarter, you want to send a message to all your customers. You send a thank you note to the customers that have made a purchase in the last quarter. To the customers who have not, you send a we-miss-you note, perhaps containing a coupon. So then, you need to partition your customer list:

Here is the Customer type:

type Customer(name : string, email : string, latestPurchase : DateTime) =
    member x.Name = name
    member x.Email = email
    member x.LatestPurchase = latestPurchase
    override x.ToString() = 
        latestPurchase.ToString("dd MMM yyyy")
        |> sprintf "Customer(%s, %s, %s)" name email

Now given a list of customers, here is how you partition that list into those who have made recent purchases and those who have not:

let customers = [
    Customer("Bob", "bob@bob.com", DateTime.Parse "5 Jun 2015")
    Customer("Barb", "barb@barbara.com", DateTime.Parse "15 May 2015")
    Customer("Chuck", "chuck@charles.com", DateTime.Parse "26 Jan 2015")
    Customer("Charlie", "charlie@charlotte.com", DateTime.Parse "1 Mar 2015")
    Customer("Dan", "dan@dan.com", DateTime.Parse "21 Dec 2014")
    Customer("Deb", "deb@deborah.com", DateTime.Parse "24 Jan 2015")
    Customer("Ed", "ed@theodore.com", DateTime.Parse "15 Mar 2015")
    Customer("Elle", "elle@elle.com", DateTime.Parse "15 Jun 2015")
]

let threeMosAgo = DateTime.Now.AddMonths -3
let recent, distant =
    customers
    |> List.partition (fun c -> c.LatestPurchase > threeMosAgo)
// val recent : Customer list =
//   [Customer(Bob, bob@bob.com, 05 Jun 2015);
//    Customer(Barb, barb@barbara.com, 15 May 2015);
//    Customer(Elle, elle@elle.com, 15 Jun 2015)]
// val distant : Customer list =
//   [Customer(Chuck, chuck@charles.com, 26 Jan 2015);
//    Customer(Charlie, charlie@charlotte.com, 01 Mar 2015);
//    Customer(Dan, dan@dan.com, 21 Dec 2014);
//    Customer(Deb, deb@deborah.com, 24 Jan 2015);
//    Customer(Ed, ed@theodore.com, 15 Mar 2015)]

Now you can send that thank you note to each of the customers in the recent list and a miss-you note to each customer in the distant list.

The F# collections modules define the find function. The find operation traverses a collection and returns the first item in the collection that meets the given condition(s).

Perhaps you are a teacher. You have a type that represents a student with a name and a grade:

type Student(name: string, grade: int) =
    member x.Name = name
    member x.Grade = grade
    override x.ToString() =
        sprintf "(%s, %d)" name grade

And you have a randomized list of those students:

let students = [ Student("Sally", 79);
                 Student("Giedrius", 81);
                 Student("Aryana", 98);
                 Student("Ty", 94);
                 Student("Eloise", 86);
                 Student("Vergil", 89);
                 Student("Doug", 66);
                 Student("Delmar", 77);
                 Student("Makenna", 88);
                 Student("Orval", 93) ]

Maybe you want to reward a random A-student (i.e., a student with a grade of 90 or above) with a candy bar. You can use find to return the first A-student in the list:

let scholar = students 
               |> List.find (fun s -> s.Grade >= 90)
// val scholar : Student = (Aryana, 98)

So, that’s great: Aryana gets a Twix! (It is the only one with the cookie crunch, after all.)

You also happen to be one of those sadistic teachers, though, who likes to embarrass the students who are not living up to their potential. Therefore you pick a random F-student (i.e., with a grade less than 65) and outfit him/her with a dunce cap:

let dunce = students 
            |> List.find (fun s -> s.Grade < 65)

// An unhandled exception of type 
// 'System.Collections.Generic.KeyNotFoundException'
// occurred in FSharp.Core.dll

Whoa! Exception? Where did that come from? (Who’s the dunce now?)

That’s a shortcoming of find. If no element meets the condition, find throws an exception.

Enter tryFind. The tryFind function returns an Option. Even on an empty collection, tryFind does not throw an exception.

let dunceOpt = students 
               |> List.tryFind (fun s -> s.Grade < 65)
// val dunceOpt : Student option = None

Of course, you may give a test one week that slays the entire class: you may not have an A-student that week. You’d better use tryFind to find an A-student, too:

let scholarOpt =
    students 
    |> List.tryFind (fun s -> s.Grade >= 90)
// val scholarOpt : Student option =
//   Some (Aryana, 98)

Now you can test dunceOpt and scholarOpt before you use them to make sure someone is supposed to get a candy bar or a dunce cap before you start handing them out.

You don’t have to program for very long before you need to sort a list of things. F#’s collections modules are nice enough to give you a canned sort function.

Maybe you have a list of words, and you want to sort them:

let xs =
  [
    "To"; "be"; "or"; "not"; "to"; "be";
    "That"; "is"; "the"; "question"
  ]
let sorted = List.sort xs
// val sorted : string list =
//   ["That"; "To"; "be"; "be"; "is"; "not"; 
//    "or"; "question"; "the"; "to"]

Easy enough. But isn’t that interesting? ‘T’ words come before ‘B’ words. Or rather, more correctly, ‘T’ words come before ‘b’ words because, by default, all capital letters are sorted before lowercase letters. And that’s all that sort does for you: It sorts using the default sorting mechanism.

Wouldn’t it be great if you could alter what sort uses to sort by? Well, you can: Use sortBy.

Here’s how to sort this list of words the way your 2^nd-grade teacher taught you, that is, without respect to case. Pass sortBy a lambda that returns the lowercase version of each string:

let sortedCaseInsensitive =
  xs |> List.sortBy (fun x -> x.ToLower())
// val sortedCaseInsensitive : string list =
//   ["be"; "be"; "is"; "not"; "or";
//    "question"; "That"; "the"; "To"; "to"]

Or maybe you need to sort a list of words in order of length. Employ a lambda that returns the length of each word:

let sortedByLength =
  xs |> List.sortBy (fun x -> x.Length)
// val sortedByLength : string list =
//   ["To"; "be"; "or"; "to"; "be"; "is";
//    "not"; "the"; "That"; "question"]

The sortBy function also works really well for classes and record types. You can use sortBy to specify which member or combination of members to sort by.

Maybe you have a record type for album tracks. It has two members: track length (in minutes) and track title.

type Track = { Length : float; Name : string }

Let’s say that you have the tracks of Spock’s Beard’s V:

let ts =
  [ { Length = 16.467; 
      Name = "At the End of the Day" };
    { Length = 6.083; 
      Name = "Revelation" };
    { Length = 4.65; 
      Name = "Thoughts (Part II)" };
    { Length = 4.067; 
      Name = "All on a Sunday" };
    { Length = 4.65; 
      Name = "Goodbye to Yesterday" };
    { Length = 27.03; 
      Name = "The Great Nothing" } ]

Sort the tracks by track length by passing a lambda to sortBy that returns the length of each track:

let sortedByTrackLength =
  ts |> List.sortBy (fun t -> t.Length)
// val sortedByTrackLength : Track list =
//   [{Length = 4.067;
//     Name = "All on a Sunday";};
//    {Length = 4.65;
//     Name = "Thoughts (Part II)";};
//    {Length = 4.65;
//     Name = "Goodbye to Yesterday";};
//    {Length = 6.083;
//     Name = "Revelation";};
//    {Length = 16.467;
//     Name = "At the End of the Day";};
//    {Length = 27.03;
//     Name = "The Great Nothing";}]

To sort according to track name instead, use a lambda that returns the track name rather than track length:

let sortedByTrackName =
  ts |> List.sortBy (fun t -> t.Name)
// val sortedByTrackName : Track list =
//   [{Length = 4.067;
//     Name = "All on a Sunday";};
//    {Length = 16.467;
//     Name = "At the End of the Day";};
//    {Length = 4.65;
//     Name = "Goodbye to Yesterday";};
//    {Length = 6.083;
//     Name = "Revelation";};
//    {Length = 27.03;
//     Name = "The Great Nothing";};
//    {Length = 4.65;
//     Name = "Thoughts (Part II)";}]

Last week we looked at the reduce operation, and we observed three properties:

• Using reduce on an empty collection yields an exception.
• You can only reduce a collection to a value of the same type as the elements in the collection.
• The order of the items in the collection (usually) matters.

We also noticed that there are several common operations—sum, product, and string concatenation—that are just special cases of reduce.

As it happens, reduce is itself a special case of a more fundamental operation: fold. Furthermore, while order still matters, fold can

• handle empty collections, and
• reduce a collection of one type to a value of a different type.

Why is that? First, fold takes a binary operation just as reduce does, but it also takes a starting value in addition to the collection. That is how fold can handle empty collections. If the collection is empty, you’re just left with the starting value. Second, because you give fold a starting value, that starting value could be of any type; it doesn’t have to match the type of the items in the collection. The reason reduce can only reduce a collection to a value of the same type is because the only starting value it has is the first value in the collection.

Let’s put fold into action.

Our Product Line

We implemented a product operation last week with reduce. Let’s do it this week with fold. This figure illustrates what’s going on:

In multiplication, 1 is the identity value. That is, 1 times x is always x. So then, if you want to calculate the product of a list of integers, make your starting value 1. Here is the code:

let product = [5;3;6] |> List.fold (*) 1
// val product : int = 90

Notice, by the way, that we are doing something we did not do last week: Using the multiplication operator as the input function rather than defining a lambda. In other words, it is superfluous to define a lambda (fun x y -> x * y) because the multiplication operator (*) is already a function that takes two numbers and multiplies them together. Let’s just use it and cut down on some noise!

Now what if the list is empty? We cannot handle an empty list with reduce, but what does fold do?

let product = [] |> List.fold (*) 1
// val product : int = 1

So then, when fold receives an empty collection, it just returns the starting value—in this case, 1.

Stringing You Along

Last week we also implemented String.concat with reduce. We can do the same thing with fold but there are some gotchas.

Try a straightforward approach:

let illJoined =
  ["do";"mi";"sol"]
  |> List.fold (fun x y -> x + "-" + y) ""
// val illJoined : string = "-do-mi-sol"

Eek! What happened? You don’t want the extra hyphen on the front! You just want hyphens in between the elements!

What if you have a list with just one item?

let illJoined =
  ["do"]
  |> List.fold (fun x y -> x + "-" + y) ""
// val illJoined : string = "-do"

No better. The following figure shows you what has happened:

While reduce cannot handle an empty collection, it only starts applying the reduction operation on the first two elements. On the other hand, fold applies the binary operation on the starting value and the first item in the list.

To do String.concat right with fold, you have to account for some special cases:

let join xs =
  if xs |> List.isEmpty then "" 
  elif xs |> List.length = 1 then
    xs.Head.ToString()
  else
    xs.Tail
    |> List.fold (fun x y -> x + "-" + y) xs.Head
let emptyJoined = join []
// val emptyJoined : string = ""
let singleJoined = join ["do"]
// val singleJoined : string = "do"
let manyJoined = join ["do";"mi";"sol"]
// val manyJoined : string = "do-mi-sol"

From Type to Type

Finally, consider an example of something fold can do that reduce cannot. If reduce receives a list of integers, it can only produce a single integer. If it receives a list of strings, its result is a single string. In contrast, fold can take a list of integers and produce a string. Or it could take a list of strings and produce a list of integers.

For instance, you can use fold to reverse a list:

let reversed =
  [1..10]
  |> List.fold (fun xs x -> x :: xs) []
// val reversed : int list =
//   [10; 9; 8; 7; 6; 5; 4; 3; 2; 1]

Notice how the starting value is a list, but the type of the elements in the input list int, not int list. Because the starting value can be a type that is different from the type of the input list elements, the binary operation can transform the elements in the list to match the type of the starting value. In fact, that is the constraint with fold: the type of the result must be type of the starting value. If your starting value is a list, fold must return a list. If your starting value is an integer, fold must return an integer.

Another example is determining the length of the longest string in a list of strings:

let longest =
  ["a";"borborygmus";"sesquipedalian";"small"]
  |> List.fold (fun n s -> max n s.Length) 0
// val longest : int = 14

Here is the documentation on fold in each collection module that defines it:

• Array.fold
• List.fold
• Seq.fold
• Set.fold
• Map.fold

As an exercise, you could try implementing map with fold.

If you have a sequence of numbers that you want to sum, F# defines the sum operation in all of the sequential collection modules:

• Array.sum
• List.sum
• Seq.sum

But what if you want to multiply all those numbers together? Well, it turns out that sum is just a special case of a more general function that the sequential collection modules also define: reduce. The reduce operation takes all the elements in a collection and combines them in some way to produce a single value. It uses a binary operation to combine the first two values. Then it takes the result of that first combination and combines it with the next element in the collection, and then the next, and so on through the end of the collection.

Here’s an illustration of how to use reduce to implement a product operation:

The code looks like this:

let product =
  [2;5;3;6]
  |> Seq.reduce (fun x y -> x * y)
// val product : int = 180

Another special case of reduce is String.concat—also known as a join operation—which allows you to concatenate a sequence of strings together with a separator in between each. Here’s how it works:

See how similar it is to the product operation above? If you should want to implement String.concat yourself, you could use reduce like this:

let joined =
  ["do";"mi";"sol";"do"]
  |> Seq.reduce (fun x y -> x + "-" + y)
// val joined : string = "do-mi-sol-do"

Here is the documentation on reduce in each of the sequential collection modules:

• Array.reduce
• List.reduce
• Seq.reduce

Now a few of caveats about reduce:

• You cannot use reduce on an empty collection. You will get an exception if you do, so make sure you check to make sure your collection is not empty before you pass it to reduce.

• The result of a reduce operation is always the same type as the elements in the collection. In other words, you can only reduce a collection of type A to a value of type A. You cannot reduce a collection of type A to a value of type B.

• Finally, order matters if the order of your binary operation matters. In other words, with addition and multiplication, order does not matter. That is, a + b is the same as b + a. (Mathematicians say that such a function is commutative.) But with something like subtraction, order does matter. In other words, a − b does not necessarily produce the same result as b − a. So make sure that your binary operation applies the reduction to its operands in the correct order.

Having noted these caveats, next week, we will cover the fold operation. It operates almost the same way as reduce in that it walks a collection, applying a binary operation to each element. The fold operation cannot help us with that last point—order still matters—but it can handle an empty collection and, if necessary, produce a result that is of a type different from the type of the source collection’s elements.

Last week we looked at Set.union. This week we look at Set.intersect. When dealing with sets (which, remember, by definition, cannot contain duplicate elements), sometimes you have two sets, and you want to know what elements they have in common. That is called the intersection of two sets.

From Genesis to Revelation

The band Genesis, like many bands that have been around as long as they have, has undergone several lineup changes. When they recorded their first album, From Genesis to Revelation, Genesis consisted of Peter Gabriel, Tony Banks, Anthony Phillips, Mike Rutherford, and John Silver. You can put their names in a set:

let on1stAlbum =
  set ["Gabriel"; "Banks"; "Phillips";
       "Rutherford"; "Silver"]

Calling All Stations

Almost thirty years later, Genesis recorded their last studio album (to date), Calling All Stations. They had had several lineup changes through the years, and by this time, the members of Genesis were Ray Wilson, Tony Banks, and Mike Rutherford. Put their names into a set:

let onLastAlbum =
  set ["Wilson"; "Banks"; "Rutherford"]

Were there any members—keepers of the flame, as it were—who stayed with the band the entire time? Perform a set intersection to find out:

let keepersOfTheFlame =
  Set.intersect on1stAlbum onLastAlbum
// val keepersOfTheFlame : Set<string> =
//   set ["Banks"; "Rutherford"]

A defining property of mathematical set is that it contain no duplicates. Sometimes you need to combine two sets. But what if those sets contain some of the same elements, so that the combination would contain duplicates? No worries! That’s where Set.union comes in.

Shock to the System

The classic lineup of progressive rock band Yes in the 1970s consisted of Jon Anderson, Steve Howe, Chris Squire, Rick Wakeman, and Bill Bruford. However, over the years, the lineup changed so that the most stable incarnation of Yes in the 1980s was Jon Anderson, Chris Squire, Trevor Rabin, Tony Kaye, and Alan White.

You can represent these two lineups as sets:

let yes70s = 
  ["Anderson"; "Howe"; "Squire"; "Wakeman"; "Bruford"]
  |> Set.ofList
let yes80s =
  ["Anderson"; "Rabin"; "Squire"; "Kaye"; "White"]
  |> Set.ofList

Union

In 1990, the record company was ready for a new Yes album. Someone had the bright idea of recording an album called Union: It would unite the classic 70s Yes lineup with the 80s lineup all on one album.

How would the lineup look on the Union album? Just pass both sets to Set.union:

let yesUnion = Set.union yes70s yes80s
// val yesUnion : Set<string> =
//   set
//     ["Anderson"; "Bruford"; "Howe"; "Kaye";
//      "Rabin"; "Squire"; "Wakeman"; "White"]

Notice how the union of the two sets does not contain duplicates even though Anderson and Squire were in both lineups.

In a previous F# Friday post, we looked at the map function. As a quick review, map lets you take a collection of elements, calculate a new value from each source element, and create a new collection containing those new values. The mapping function has the following signature:

'T -> 'U

In other words, the function takes a single value of type 'T and returns a single value of type 'U.

But what if you have a mapping function with this signature?

'T -> 'U list

In other words, this function does not take one value and produce one value. Rather it takes one value and produces multiple values. What if you’re OK with that, but you just need to take those many values returned from each mapping and smash them all together into one list?

The Universe Divided

The guys in Canadian power trio Rush didn’t just stick to one instrument on their Hemispheres album. Each of them played a collection of instruments. So let’s create a Musician record type to represent a musician and the list of instruments he plays on the album:

type Musician = {
  Name : string
  Instruments : string list
}

Now you can create a list of musicians:

let rush = [
  {
    Name = "Geddy Lee";
    Instruments = 
    [
      "vocals"; "bass guitar"; 
      "Oberheim polyphonic"; 
      "Minimoog"; "Moog Taurus pedals"
    ]
  };
  {
    Name = "Alex Lifeson";
    Instruments = 
    [
      "electric and acoustic guitars";
      "classical guitar"; "guitar synthesizer"; 
      "Moog Taurus pedals"
    ]
  };
  {
    Name = "Neil Peart";
    Instruments =
    [
      "drums"; "orchestra bells"; "bell tree";
      "timpani"; "gong"; "cowbells";
      "temple blocks"; "wind chimes"; "crotales"
    ]
  }
]

Maybe you want one long list of every instrument the fellows in Rush used on the album. You just have to map each musician to his list of instruments, and then concatenate those lists together:

You could do this with two functions you’ve read about already on F# Fridays: map and concat:

let instruments =
  rush
  |> List.map (fun m -> m.Instruments)
  |> List.concat
// val instruments : string list =
//   ["vocals"; "bass guitar"; "Oberheim polyphonic";
//    "Minimoog"; "Moog Taurus pedals"; ...]

Heart and Mind United

What if there were a function that could do both of those things—perform the transformation and the concatenation all in one? Turns out that there is: collect!

let instruments =
  rush |> List.collect (fun m -> m.Instruments)
// val instruments : string list =
//   ["vocals"; "bass guitar"; "Oberheim polyphonic";
//    "Minimoog"; "Moog Taurus pedals"; ...]

How ’bout that? The very same results all in one function!

So then, collect performs a map and a concatenation, or a flatten, all in one function call. In fact, some languages name this operation flatMap or flat_map.

You’ve seen collect examples here only in terms of lists, but the F#’s Array and Seq modules define the collect operation, too:

• Array.collect
• Seq.collect

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.