A great place to start when thinking about the F# type system is the option type. As discussed in Chapter 5, "Composite Types," the option type allows you to encode the lack of a value in a much more type safe way than null. The reason the option type is such a great place to start is that this same idea of encoding meaning in the type system can be used in many other ways.

let getFormattedWebData url =
    let webData = getWebData url
    match webData with
    | Some(data) -> formatData data
    | None -> None

Option wraps another type and must be explicitly unwrapped later to be used. The returned information about the state must be dealt with before the data can be touched. As Option<T> must be explicitly checked before being opened, you are forced to verify its contents before trying to perform any computation with it. The great value in this is that when you have instances of types that aren't options, you can be sure that they contain a value. This is in contrast with null, which may always be present and so must repeatedly be checked for, thus littering your code with frequent precondition checks and potentially causing unexpected runtime null reference exceptions.

Now, it is important to know that when dealing with standard CLR libraries you may still encounter null in F#. In these cases it is always best to wrap these calls to return an option type immediately. However, when using with the F# specific libraries, the option type is used by default and this need not be a consideration.

You just learned about how the option type gives you the advantage of no longer having to perform runtime precondition null checks on data's state as your checks are instead being enforced by the type system. This same idea can be extended beyond simply replacing null. In actuality, it can be used to encode and enforce any discretely identifiable piece of state information.

As a trivial example, consider an ordered list. With some algorithms the difference between having an appropriately ordered data set or an unordered data set can be the difference between O(n) and possible O(n^2) performance. Others, which are written to depend on ordering, will not function at all.

One example of the later is the removal of duplicates. With a sorted list this is a simple O(n) operation. Without ordering, this process requires a completely different, and much more complex, algorithm.

let removeDupesFromOrdered orderedList =
    List.foldBack (fun element noDupes ->
        match noDupes with
        | [] -> [element]
        | (h::_) -> if element = h then noDupes
                    else [element] @ noDupes)
        orderedList []

> removeDupesFromOrdered [0; 1; 1; 2; 3; 4; 5; 5; 6];;
val it : int list = [0; 1; 2; 3; 4; 5; 6]

What if you want to ensure that only a sorted list could be passed in to your function? In C# this would likely mean inheriting from ReadOnlyCollection and perhaps adding an extension method to list which returned a new sorted instance. However, this would mean writing a significant amount of code and, as constructors are not inherited, potentially updating that code with each additional .NET framework release.

However, in F# you can leverage the discriminated union feature and do the same thing with significantly less code, in a similar way to how the option type is implemented.

type OrderedList<'a> = | OrderedList of 'a list

let toOrderedList list = OrderedList(List.sort list)

let toList (OrderedList orderedList) = orderedList


let removeDuplicatesFromOrderedList (orderedList: OrderedList<'a>) =
    let removeDupes list =
        List.foldBack (fun element noDupes ->
            match noDupes with
            | [] -> [element]
            | (h::_) -> if element = h then noDupes
                        else element :: noDupes)
            list []
    match orderedList with
    | OrderedList list -> OrderedList(removeDupes list)
                                                                 

As you can see here, you can no longer use normal lists with this version of the removeDuplicates.

removeDuplicatesFromOrderedList [0; 1; 1; 2; 2; 3]
error FS0001: This expression was expected to have type
    OrderedPropertyList<'a>
but here has type
    'b list

To use this function you now must wrap your list to encode in the type system that it is ordered.

> let orderedList = toOrderedList [0; 1; 1; 2; 2; 3]
val orderedList : OrderedList<int> = OrderedList [0; 1; 1; 2; 2; 3]

> removeDuplicatesFromOrderedList orderedList
val it : OrderedList<int> = OrderedList [0; 1; 2; 3]

Even more interesting, you can encode several different possible data states into one discriminated union type. This allows your functions to take or return many different information states and, in so doing, behave in the best possible way for every possible situation.

type PropertyList<'a> =
    | Normal of 'a list
    | Ordered of 'a list
    | NoDuplicates of 'a list

let CreateNoDuplicatesListFromPropertyList list =
    function
    | NoDuplicates(_) -> list
    | Normal(noProperty) ->
        NoDuplicates (noProperty |> Set.ofList |> List.ofSeq)
    | Ordered(ordered) ->
        NoDuplicates (List.foldBack (fun element noDupes ->
            match noDupes with
            | [] -> [element]
            | (h::_) -> if element = h then noDupes
                        else element :: noDupes) ordered [])
                                                                

By taking information that would have been implicit in the ordering of your calls and using a type wrapper to make this assumption explicit, you are moving contextual constraints into the type system. This will increase the compile-time safety of your code by ensuring that your data will only go into the correct functions. This also allows you to verify things that would otherwise be time consuming to explicitly verify with preconditions or class wrappers, such as the internal state of a list.

One significant enhancement that comes from the wrapping of state in a type is the lack of need for exceptions. Exceptions are both costly in terms of performance and dangerous in terms of behavior. Also, the need for many try blocks detracts significantly from the readability of your code.

In most cases, exceptions are not all that exceptional and so need not behave differently than a normal function return value. In the vast majority of cases, they are simply a way of having multiple function output types in languages that lack discriminated unions.

In F#, instead of frequently using exceptions, it is better to encode your various return states within discriminated unions. In cases where you might be tempted to return null, you use the option type as previously described. However, when you want to create your own set of return types, you need to define your own discriminated union.

type UriOutput =
    | Uri of System.Uri
    | Malformed of string

let buildUri stringUri =
    try Uri( new System.Uri(stringUri) )
    with | _ -> Malformed(stringUri)

As in this example, it is often advantageous to wrap existing .NET method calls in functions that return discriminated unions. In this way, you can greatly increase code readability. In F#, exceptions, along with their unseemly try-with blocks, are no longer necessary in most cases. When every state is enumerated explicitly, your code is much easier to maintain and is significantly easier to read.

Just as you saw with exceptions, discriminated unions allow you to encode many different data states directly into your type and so ensure that they are properly handled. Designing systems to behave in this way is a simple four-step process. As an example, consider a WebClient interface that takes either a Uri or a String and returns the correct data structure for the type of data found.

First, enumerate your input states with a discriminated union type.

type WebClientInput =
    | StringInput of String
    | UriInput of System.Uri
                                                    

Second, do the same for your possible output states.

type WebClientOutput =
    | MalformedUri of string
    | TextContent of string
    | BinaryContent of byte []
    | NoContent
    | WebClientException of System.Net.WebException
                                                        

Third, you must build your function to return each of these states in the appropriate situation.

let downloadWithWebClient (inputUri: WebClientInput) =
    let downloadFromUri (uri: System.Uri) =
        try
            use client = new System.Net.WebClient()
            let dlData = client.DownloadData(uri)
            if dlData.Length = 0 then NoContent
            else if (client.ResponseHeaders.["content-type"]
                           .StartsWith(@"text/"))
                then
                    let dlText =
                        System.Text.Encoding.Default.GetString(dlData)
                    TextContent(dlText)
                else
                    BinaryContent(dlData)
        with
           | :? System.Net.WebException as e -> WebClientException(e)
    match inputUri with
    | UriInput(classUri) -> downloadFromUri classUri
    | StringInput(stringUri) ->

match buildUri stringUri with
        | Uri(s) -> downloadFromUri s
        | Malformed(s) -> MalformedUri(s)
                                                         

Finally, consume and appropriately handle your expected return states.

let printWebClientOutput clientOutput =
    match clientOutput with
    | MalformedUri(uri) -> printfn "Input Uri was malformed: %s" uri
    | TextContent(content) -> printfn "Page Content: %s" content
    | BinaryContent(content) -> printfn "Binary Data: %d" content.Length
    | NoContent -> printfn "No content was found."
    | WebClientException(e) -> printsn "Exception: %s" (e.ToString())

                                                     

The F# compiler issue warnings when not all returned states are handled. This provides a much safer style of data handling than exceptions that are in no way encoded in the function signature. Also, as match statements support wildcards, you need to consider only the relevant states to your current context.

open System.IO

let downloadToFile (inputUri: WebClientInput) outputLocation =
    match downloadWithWebClient inputUri with
    | TextContent(text) -> File.WriteAllText( outputLocation, text )
    | BinaryContent(binary) -> File.WriteAllBytes( outputLocation, binary )
    | _ -> printfn "Download Failed"
                                                              

It is important to keep in mind that when using wildcards you will no longer receive compiler warnings when some states are not covered in your match statement. For this reason, it is usually best to explicitly match all states in production code. This ensures that potentially relevant states will not be missed with future code changes.

In this example, all your possible inputs and outputs are discretely defined. The beauty in this is that you can now handle these cases in an explicit and elegant way. If you wanted to add an additional input type, you would need only extend WebClientInput and add another case to your match statement. Similarly, if you wanted to add another output case, you simply extend WebClientOutput and add that case as a new return value of your function. This makes it simple to add new input types and output states as the need arises.

Beyond their use in increasing type safety, discriminated unions may also be used to define complex data structures through recursive type definitions. Recursive type definitions are discriminated unions in which some subtypes leverage either themselves or a child type in its definition. One simple example of this would be a binary tree.

type BinaryTree<'a> =
    | Node of BinaryTree<'a> * BinaryTree<'a>
    | Leaf of 'a
                                                             

In this case, a node may either be a leaf or contain a tuple of two more binary trees. This technique can be leveraged to quickly build data structures that would have taken orders of magnitude more code in other languages.

One might argue that, although the definition is simplified, it may be more difficult to implement functionality for this data structure based on the nodes themselves not containing any methods. As you'll see in the following depth-first search example, this is not the case. It is a simple matter to externalize what would have previously been object-oriented code.

let rec dfs tree leafData =
    match tree with
    | Leaf(l) -> if l = leafData then Some(l) else None
    | Node(a,b) -> let dfsA = dfs a leafData in
                   if Option.isSome dfsA then dfsA
                   else dfs b leafData

let binaryTree =
    Node(
        Node( Leaf(1), Leaf(2) ),
        Node( Leaf(3), Node( Leaf(4), Leaf(5) ) ) );;
val binaryTree : BinaryTree<int> =
  Node (Node (Leaf 1,Leaf 2),Node (Leaf 3,Node (Leaf 4,Leaf 5)))

dfs binaryTree 5;;
val it : int option = Some 5

dfs binaryTree 33;
val it : int option = None
                                                                  

As you can see here, recursive data type definitions are quite powerful constructs. When combined with recursive functions, they can be leveraged to build what would otherwise be complex data and difficult to maintain structures with very little code.

Although perhaps a bit intimidating at first, with a little practice it's a trivial matter to go from a definition in which an object calls its children to one in which a function recurses on each data structure node. In most cases, this can be done by replacing what would have been the this construct with the object operated on. Getting your head around this is one of many paradigm shifts necessary to become effective at F# when coming from an imperative language.