F Sharp Programming/Sets and Maps
F# : Sets and Maps |
In addition to lists and sequences, F# provides two related immutable data structures called sets and maps. Unlike lists, sets and maps are unordered data structures, meaning that these collections do not preserve the order of elements as they are inserted, nor do they permit duplicates.
Sets
[edit | edit source]A set in F# is just a container for items. Sets do not preserve the order in which items are inserted, nor do they allow duplicate entries to be inserted into the collection.
Sets can be created in a variety of ways:
Adding an item to an empty set
The Set
module contains a useful function Set.empty
which returns an empty set to start with.
Conveniently, all instances of sets have an Add
function with the type val Add : 'a -> Set<'a>
. In other words, our Add
returns a new set containing our new item, which makes it easy to add items together in this fashion:
> Set.empty.Add(1).Add(2).Add(7);;
val it : Set<int> = set [1; 2; 7]
Converting lists and sequences into sets
Additionally, the we can use Set.ofList
and Set.ofSeq
to convert an entire collection into a set:
> Set.ofList ["Mercury"; "Venus"; "Earth"; "Mars"; "Jupiter"; "Saturn"; "Uranus"; "Neptune"];;
val it : Set<string> = set ["Earth"; "Jupiter"; "Mars"; "Mercury"; ...]
The example above demonstrates the unordered nature of sets.
The Set
Module
[edit | edit source]The FSharp.Collections.Set module contains a variety of useful methods for working with sets.
val add : 'a -> Set<'a> -> Set<'a>
- Return a new set with an element added to the set. No exception is raised if the set already contains the given element.
val compare : Set<'a> -> Set<'a> -> int
- Compare two sets. Places sets into a total order.
val count : Set<'a> -> int
- Return the number of elements in the set. Same as "size".
val difference : Set<'a> -> Set<'a> -> Set<'a>
- Return a new set with the elements of the second set removed from the first. That is a set containing only those items from the first set that are not also in the second set.
> let a = Set.ofSeq [ 1 .. 10 ]
let b = Set.ofSeq [ 5 .. 15 ];;
val a : Set<int>
val b : Set<int>
> Set.difference a b;;
val it : Set<int> = set [1; 2; 3; 4]
> a - b;; (* The '-' operator is equivalent to Set.difference *)
val it : Set<int> = set [1; 2; 3; 4]
val exists : ('a -> bool) -> Set<'a> -> bool
- Test if any element of the collection satisfies the given predicate.
val filter : ('a -> bool) -> Set<'a> -> Set<'a>
- Return a new collection containing only the elements of the collection for which the given predicate returns "true".
val intersect : Set<'a> -> Set<'a> -> Set<'a>
- Compute the intersection, or overlap, of the two sets.
> let a = Set.ofSeq [ 1 .. 10 ]
let b = Set.ofSeq [ 5 .. 15 ];;
val a : Set<int>
val b : Set<int>
> Set.iter (fun x -> printf "%O " x) (Set.intersect a b);;
5 6 7 8 9 10
val map : ('a -> 'b) -> Set<'a> -> Set<'b>
- Return a new collection containing the results of applying the given function to each element of the input set.
val contains: 'a -> Set<'a> -> bool
- Evaluates to
true
if the given element is in the given set.
val remove : 'a -> Set<'a> -> Set<'a>
- Return a new set with the given element removed. No exception is raised if the set doesn't contain the given element.
val count: Set<'a> -> int
- Return the number of elements in the set.
val isSubset : Set<'a> -> Set<'a> -> bool
- Evaluates to "true" if all elements of the first set are in the second.
val isProperSubset : Set<'a> -> Set<'a> -> bool
- Evaluates to "true" if all elements of the first set are in the second, and there is at least one element in the second set which is not in the first.
> let a = Set.ofSeq [ 1 .. 10 ]
let b = Set.ofSeq [ 5 .. 15 ]
let c = Set.ofSeq [ 2; 4; 5; 9 ];;
val a : Set<int>
val b : Set<int>
val c : Set<int>
> Set.isSubset c a;; (* All elements of 'c' exist in 'a' *)
val it : bool = true
> Set.isSubset c b;; (* Not all of the elements of 'c' exist in 'b' *);;
val it : bool = false
val union : Set<'a> -> Set<'a> -> Set<'a>
- Compute the union of the two sets.
> let a = Set.ofSeq [ 1 .. 10 ]
let b = Set.ofSeq [ 5 .. 15 ];;
val a : Set<int>
val b : Set<int>
> Set.iter (fun x -> printf "%O " x) (Set.union a b);;
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 val it : unit = ()
> Set.iter (fun x -> printf "%O " x) (a + b);; (* '+' computes union *)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Examples
[edit | edit source]open System
let shakespeare = "O Romeo, Romeo! wherefore art thou Romeo?"
let shakespeareArray =
shakespeare.Split([| ' '; ','; '!'; '?' |], StringSplitOptions.RemoveEmptyEntries)
let shakespeareSet = shakespeareArray |> Set.ofSeq
let main() =
printfn "shakespeare: %A" shakespeare
let printCollection msg coll =
printfn "%s:" msg
Seq.iteri (fun index item -> printfn " %i: %O" index item) coll
printCollection "shakespeareArray" shakespeareArray
printCollection "shakespeareSet" shakespeareSet
Console.ReadKey(true) |> ignore
main()
shakespeare: "O Romeo, Romeo! wherefore art thou Romeo?" shakespeareArray: 0: O 1: Romeo 2: Romeo 3: wherefore 4: art 5: thou 6: Romeo shakespeareSet: 0: O 1: Romeo 2: art 3: thou 4: wherefore
Maps
[edit | edit source]A map is a special kind of set: it associates keys with values. A map is created in a similar way to sets:
> let holidays =
Map.empty. (* Start with empty Map *)
Add("Christmas", "Dec. 25").
Add("Halloween", "Oct. 31").
Add("Darwin Day", "Feb. 12").
Add("World Vegan Day", "Nov. 1");;
val holidays : Map<string,string>
> let monkeys =
[ "Squirrel Monkey", "Simia sciureus";
"Marmoset", "Callithrix jacchus";
"Macaque", "Macaca mulatta";
"Gibbon", "Hylobates lar";
"Gorilla", "Gorilla gorilla";
"Humans", "Homo sapiens";
"Chimpanzee", "Pan troglodytes" ]
|> Map.ofList;; (* Convert list to Map *)
val monkeys : Map<string,string>
You can use the .[key]
to access elements in the map:
> holidays.["Christmas"];;
val it : string = "Dec. 25"
> monkeys.["Marmoset"];;
val it : string = "Callithrix jacchus"
The Map
Module
[edit | edit source]The FSharp.Collections.Map module handles map operations.
val add : 'key -> 'a -> Map<'key,'a> -> Map<'key,'a>
- Return a new map with the binding added to the given map.
val empty<'key,'a> : Map<'key,'a>
- Returns an empty map.
val exists : ('key -> 'a -> bool) -> Map<'key,'a> -> bool
- Return true if the given predicate returns true for one of the bindings in the map.
val filter : ('key -> 'a -> bool) -> Map<'key,'a> -> Map<'key,'a>
- Build a new map containing only the bindings for which the given predicate returns
true
.
val find : 'key -> Map<'key,'a> -> 'a
- Lookup an element in the map, raising
KeyNotFoundException
if no binding exists in the map.
val containsKey: 'key -> Map<'key,'a> -> bool
- Test if an element is in the domain of the map.
val remove : 'key -> Map<'key,'a> -> Map<'key,'a>
- Remove an element from the domain of the map. No exception is raised if the element is not present.
val tryFind : 'key -> Map<'key,'a> -> 'a option
- Lookup an element in the map, returning a
Some
value if the element is in the domain of the map andNone
if not.
Examples
[edit | edit source]open System
let capitals =
[("Australia", "Canberra"); ("Canada", "Ottawa"); ("China", "Beijing");
("Denmark", "Copenhagen"); ("Egypt", "Cairo"); ("Finland", "Helsinki");
("France", "Paris"); ("Germany", "Berlin"); ("India", "New Delhi");
("Japan", "Tokyo"); ("Mexico", "Mexico City"); ("Russia", "Moscow");
("Slovenia", "Ljubljana"); ("Spain", "Madrid"); ("Sweden", "Stockholm");
("Taiwan", "Taipei"); ("USA", "Washington D.C.")]
|> Map.ofList
let rec main() =
Console.Write("Find a capital by country (type 'q' to quit): ")
match Console.ReadLine() with
| "q" -> Console.WriteLine("Bye bye")
| country ->
match capitals.TryFind(country) with
| Some(capital) -> Console.WriteLine("The capital of {0} is {1}\n", country, capital)
| None -> Console.WriteLine("Country not found.\n")
main() (* loop again *)
main()
Find a capital by country (type 'q' to quit): Egypt The capital of Egypt is Cairo Find a capital by country (type 'q' to quit): Slovenia The capital of Slovenia is Ljubljana Find a capital by country (type 'q' to quit): Latveria Country not found. Find a capital by country (type 'q' to quit): USA The capital of USA is Washington D.C. Find a capital by country (type 'q' to quit): q Bye bye
Set and Map Performance
[edit | edit source]F# sets and maps are implemented as immutable AVL trees, an efficient data structure which forms a self-balancing binary tree. AVL trees are well-known for their efficiency, in which they can search, insert, and delete elements in the tree in O(log n) time, where n is the number of elements in the tree.