Lecture 7 — Error handling in functional programs: "railway oriented" programming

This lecture follows Scott Wlaschin's Railway Oriented Programming (https://fsharpforfunandprofit.com/rop/): the two-track picture, its vocabulary and the use case are his. The code uses the Result type that F# has had since 2017. The complete programs (the list selector, the typed pipeline) and the exercises are in the worked examples at the end of these notes.

1. The happy path is a composition
2. A function can have two outputs
3. Bind is the adapter
4. Other shapes fit with adapters
5. Errors are part of the domain
6. No result, one result, many results: one shape

1 · The happy path is a composition

A use case is a pipeline of functions glued with >>, and error handling must not break that shape.

A use case

"As a user I want to update my name and email address": receive the request, validate it, canonicalize the email, update the user record, send a verification mail, return a message to the user. The model is pure: the user records are a map keyed by a user identifier (lecture 5), and sending a mail produces a value.

type UserId = UserId of int
type User = { id: UserId; name: string; email: string }
type Request = { userId: UserId; name: string; email: string }
type Users = Map<UserId, User>
type Message = { recipient: string; text: string }

let users: Users =
  Map.ofList
    [ UserId 1, { id = UserId 1; name = "Kati"; email = "kati@taltech.ee" }
      UserId 2, { id = UserId 2; name = "Mart"; email = "mart@taltech.ee" } ]

let request =
  { userId = UserId 1; name = "Kati Karu"
    email = " Kati.Karu@TalTech.ee " }

Request and User share the labels name and email, so every function over the model annotates its parameter: the annotation states which record is meant (lecture 5).

Imperative code, functional flow

Wlaschin's imperative version of the use case (C#), written as if nothing could fail (the "happy path"):

string ExecuteUseCase()
{
  var request = receiveRequest();
  validateRequest(request);
  canonicalizeEmail(request);
  db.updateDbFromRequest(request);
  smtpServer.sendEmail(request.Email);
  return "Success";
}

In F#, the five steps are "one-track" functions and the use case is their composition with >> (lecture 5: (f >> g) x = g (f x)). Three of them can only fail by raising an exception: validateOrFail, updateOrFail, and sendEmail when the mail server has no route to the address (our server delivers to taltech.ee only):

let validateOrFail (r: Request) : Request =
  if r.name = "" then failwith "Name must not be blank"
  elif r.email = "" then failwith "Email must not be blank"
  else r

let canonicalizeEmail (r: Request) : Request =
  { r with email = r.email.Trim().ToLowerInvariant() }

let updateOrFail (users: Users) (r: Request) : User =
  match Map.tryFind r.userId users with
  | Some u -> { u with name = r.name; email = r.email }
  | None -> failwith "User not found"

let sendEmail (u: User) : Message =
  if not (u.email.EndsWith "@taltech.ee") then
    failwith $"no route to {u.email}"
  { recipient = u.email; text = $"Hello {u.name}, please verify your email address." }

let confirm (m: Message) : string =
  $"Success: verification mail sent to {m.recipient}"

let happyPath (users: Users) =
  validateOrFail
  >> canonicalizeEmail
  >> updateOrFail users
  >> sendEmail
  >> confirm

What is happyPath users request?

let happy = happyPath users request

"Success: verification mail sent to kati.karu@taltech.ee"

The composition hides that it was built from parts: happyPath users is one function from a request to a message. The record the update step produces is the user with the new name and the canonical email:

let updated = updateOrFail users (canonicalizeEmail request)

{ id = UserId 1
  name = "Kati Karu"
  email = "kati.karu@taltech.ee" }

Straying from the happy path

"A program is a spell cast over a computer, turning input into error messages" (quoted on Wlaschin's slides). The name may be blank, the email malformed, the user unknown, the mail server down — and the user wants a sensible message for each. validateOrFail, updateOrFail and sendEmail hide the failure in an exception: nothing in their types says that they can fail. Handling the errors in the imperative style turns Wlaschin's six clean lines into eighteen:

string ExecuteUseCase()
{
  var request = receiveRequest();
  var isValidated = validateRequest(request);
  if (!isValidated) { return "Request is not valid"; }
  canonicalizeEmail(request);
  try {
    var result = db.updateDbFromRequest(request);
    if (!result) { return "Customer record not found"; }
  } catch {
    return "DB error: Customer record not updated";
  }
  if (!smtpServer.sendEmail(request.Email)) {
    log.Error("Customer email not sent");
  }
  return "OK";
}

"200% extra, and sadly typical of error-handling code" (Wlaschin). Can we handle the errors and keep the composition? That is the question of this lecture; the answer is yes.

2 · A function can have two outputs

A function that can fail has two outputs, and Result makes both visible in its type.

Two tracks

F# has the type type Result<'T, 'TError> = Ok of 'T | Error of 'TError (in FSharp.Core since 2017). Its constructors are Ok and Error; Wlaschin's slides call them Success and Failure. A function of type 'a -> Result<'b, 'e> has one track in and two tracks out: Wlaschin calls it a "switch".

A switch

let nameNotBlank (r: Request) =
  if r.name = "" then
    Error "Name must not be blank"
  else
    Ok r

What type does F# infer for nameNotBlank?

val nameNotBlank: r: Request -> Result<Request,string>

What does nameNotBlank return for a request with a blank name, and for request?

let blankName = nameNotBlank { request with name = "" }
let okName = nameNotBlank request

Error "Name must not be blank"

Ok { userId = UserId 1
     name = "Kati Karu"
     email = " Kati.Karu@TalTech.ee " }

Option or Result?

None says that something is missing; Error says why. Which type would you give these functions?

• A map lookup (Map.tryFind): an option. Absence is normal and needs no reason; lecture 5's enrolled treated a course nobody has taken as the empty set.
• Parsing a number typed by a user: a Result. The reason matters to the user, and there is more than one ("not a number", "too large").
• Removing a value that is not in a search tree (lecture 6's remove returned the tree unchanged): a design question. Silent when the caller does not care, an option when "nothing was removed" is all it needs to know, a Result when the caller must know what was missing (exercise 1).

3 · Bind is the adapter

Two switches do not compose, but bind turns a switch into a two-track function, and those compose.

Switches do not compose

A second check:

let name50 (r: Request) =
  if r.name.Length > 50 then
    Error "Name must not be longer than 50 chars"
  else
    Ok r

What is wrong with nameNotBlank >> name50?

> nameNotBlank >> name50;;
  nameNotBlank >> name50;;
  ----------------^^^^^^
error FS0001: Type mismatch. Expecting a
    'Result<Request,string> -> 'a'
but given a
    'Request -> Result<Request,string>'
The type 'Request' does not match the type 'Result<Request,string>'

Two tracks come out of nameNotBlank, one goes into name50: the tracks do not meet. Composing one-track functions is fine, composing two-track functions is fine, but a switch needs an adapter: nameNotBlank >> Result.bind name50 type-checks.

bind

bind takes a switch and returns a "two-track" function: on the Ok track it applies the switch, on the Error track it passes the error on.

let bind f x =
  match x with
  | Ok a -> f a
  | Error e -> Error e

val bind: f: ('a -> Result<'b,'c>) -> x: Result<'a,'c> -> Result<'b,'c>

The library has it as Result.bind, with the same type:

> Result.bind;;
val it: (('a -> Result<'b,'c>) -> Result<'a,'c> -> Result<'b,'c>)

The validation chain

Two more switches, and the chain of all four:

let emailNotBlank (r: Request) =
  if r.email = "" then
    Error "Email must not be blank"
  else
    Ok r

let emailHasAt (r: Request) =
  if r.email.Contains '@' then
    Ok r
  else
    Error $"Email {r.email} is not valid"

let validateRequest =
  nameNotBlank
  >> Result.bind name50
  >> Result.bind emailNotBlank
  >> Result.bind emailHasAt

The first switch needs no bind: its input is one track. What does validateRequest return for a request with a 60-character name, and for request?

let longName = validateRequest { request with name = String.replicate 60 "x" }
let validOne = validateRequest request

Error "Name must not be longer than 50 chars"

Ok { userId = UserId 1
     name = "Kati Karu"
     email = " Kati.Karu@TalTech.ee " }

The chain stopped at the second check: the first passed, and the error of name50 bypassed the two checks after it. The same chain can be written with |>, applying the checks to a request one by one:

let piped =
  request
  |> nameNotBlank
  |> Result.bind name50
  |> Result.bind emailNotBlank
  |> Result.bind emailHasAt

let pipedSame = (piped = validOne)

true

Wlaschin writes the |> form with an operator >>= ("bind symbol = F# composition symbol + railway track"); |> Result.bind says the same with library names.

Bind is about shape

bind only cares that its argument is a switch; the type on the track may change from step to step. findUser is a switch from a request to a user:

let findUser (users: Users) (r: Request) =
  match Map.tryFind r.userId users with
  | Some u -> Ok u
  | None -> Error "User not found"

let validatedUser = validateRequest >> Result.bind (findUser users)

validateRequest >> Result.bind (findUser users)
  : Request -> Result<User, string>

The track entered with a Request and leaves with a User.

let found = validatedUser request
let notFound = validatedUser { request with userId = UserId 9 }

Ok { id = UserId 1
     name = "Kati"
     email = "kati@taltech.ee" }

Error "User not found"

4 · Other shapes fit with adapters

Functions of other shapes fit the two-track model through small adapters: map, tee, tryCatch and mapError.

Four shapes

Not every step is a switch. Wlaschin lists four other shapes:

• a one-track function 'a -> 'b that cannot fail (canonicalizeEmail);
• a "dead-end" function 'a -> unit that returns nothing (logging);
• a function that throws an exception (sendEmail when the mail server has no route; int "forty-two");
• a supervisory function that handles both tracks (translating an error).

Each gets an adapter.

One-track functions: map

map applies a one-track function on the Ok track and passes an error on:

let map f x =
  match x with
  | Ok a -> Ok (f a)
  | Error e -> Error e

> Result.map;;
val it: (('a -> 'b) -> Result<'a,'c> -> Result<'b,'c>)

How would you define map with bind? A one-track function followed by Ok is a switch that never fails:

let mapViaBind f = bind (f >> Ok)

let mapped: Result<Request, string> = map canonicalizeEmail (Ok request)
let mappedViaBind: Result<Request, string> = mapViaBind canonicalizeEmail (Ok request)
let mapsAgree = (mapped = mappedViaBind)

Ok { userId = UserId 1
     name = "Kati Karu"
     email = "kati.karu@taltech.ee" }

true

Dead ends: tee

A function that returns unit (logging, printing) ends the track. tee calls it and passes the input on, like a T-junction in a pipe:

let tee f x =
  f x
  x

> request |> tee (fun r -> printfn "got %s" r.name) |> nameNotBlank;;
got Kati Karu
val it: Result<Request,string> = Ok { userId = UserId 1
                                      name = "Kati Karu"
                                      email = " Kati.Karu@TalTech.ee " }

Exceptions

F# has exceptions, and library functions use them: failwith "message" raises one with a message (validateOrFail above), exception Name of … declares your own, raised with raise (lecture 5's UnknownArticle), and try … with catches them. An uncaught exception stops the program:

> validateOrFail { request with name = "" };;
System.Exception: Name must not be blank
Stopped due to error

> int "forty-two";;
System.FormatException: The input string 'forty-two' was not in a
correct format.
Stopped due to error

Wlaschin's guideline: convert exceptions into errors at the boundary where they arise, and do not use exceptions for control flow.

tryCatch

tryCatch turns a function that may throw into a switch:

let tryCatch f x =
  try Ok (f x)
  with ex -> Error ex.Message

val tryCatch: f: ('a -> 'b) -> x: 'a -> Result<'b,string>

What are tryCatch int "42" and tryCatch int "forty-two"?

let parsed = tryCatch int "42"
let notParsed = tryCatch int "forty-two"

Ok 42

Error "The input string 'forty-two' was not in a correct format."

In the pipeline, tryCatch sendEmail makes the mail step a switch. What is tryCatch sendEmail for a user at example.com?

let mailFail = tryCatch sendEmail { id = UserId 1; name = "Kati"; email = "kati@example.com" }

Error "no route to kati@example.com"

tryCatch validateOrFail likewise turns concept 1's fail-fast check into a switch:

let caught = tryCatch validateOrFail { request with name = "" }

Error "Name must not be blank"

Which adapter?

• canonicalizeEmail : Request -> Request, a one-track function: Result.map canonicalizeEmail.
• a logging function Request -> unit, a dead end: tee log, then compose.
• sendEmail : User -> Message, which may throw: tryCatch sendEmail, a switch, then Result.bind.
• updateUser : Request -> Result<User, string>, a switch: Result.bind updateUser.
• a function on the error text, string -> string: Result.mapError f applies it on the Error track and passes an Ok on.

let prefixed = Result.mapError (fun e -> "Validation failed: " + e) blankName

Error "Validation failed: Name must not be blank"

Putting it together

A lookup returns an option; ofOption names the reason for None and puts the lookup on two tracks (there is no such function in the library):

let ofOption err opt =
  match opt with
  | Some a -> Ok a
  | None -> Error err

let updateUser (users: Users) (r: Request) =
  Map.tryFind r.userId users
  |> ofOption "User not found"
  |> Result.map (fun u ->
     { u with name = r.name; email = r.email })

let returnMessage (r: Result<Message, string>) =
  match r with
  | Ok m -> $"Success: verification mail sent to {m.recipient}"
  | Error e -> e

let executeUseCase (users: Users) =
  validateRequest
  >> Result.map canonicalizeEmail
  >> Result.bind (updateUser users)
  >> Result.bind (tryCatch sendEmail)
  >> returnMessage

The use case has its shape back: one composition, every step adapted to two tracks, and returnMessage joins the tracks at the end (Ok m becomes the success text, Error e is e). What does executeUseCase users return for request, for the email kati.karu, for userId = UserId 9, and for the email Kati@example.com?

let run = executeUseCase users
let okRun = run request
let badEmailRun = run { request with email = "kati.karu" }
let unknownRun = run { request with userId = UserId 9 }
let mailFailRun = run { request with email = "Kati@example.com" }

"Success: verification mail sent to kati.karu@taltech.ee"

"Email kati.karu is not valid"

"User not found"

"no route to kati@example.com"

Before and after

Wlaschin's review: compare happyPath (before, no error handling) with executeUseCase (after, every error handled). The imperative version grew from six lines to eighteen; the functional one kept its shape, five steps each fitted to two tracks, and is still clean.

5 · Errors are part of the domain

Errors are domain data: a union of error cases documents everything that can go wrong, and text is produced once, at the end.

Strings are poor errors

A string error cannot be matched on, carries no data and is easy to mistype. A union of error cases is type-safe documentation of everything that can go wrong, and it cannot go out of date:

type UseCaseError =
  | NameMustNotBeBlank
  | NameTooLong of int
  | EmailMustNotBeBlank
  | EmailNotValid of string
  | UserNotFound of UserId
  | MailNotSent of string

The validations over it get a T suffix ("typed"), because a script cannot redefine a name (lecture 1). MailNotSent carries the mail server's message as data; worked example B shows how the exception's text becomes that case.

let nameNotBlankT (r: Request) =
  if r.name = "" then Error NameMustNotBeBlank else Ok r

let name50T (r: Request) =
  if r.name.Length > 50 then Error (NameTooLong r.name.Length) else Ok r

let emailNotBlankT (r: Request) =
  if r.email = "" then Error EmailMustNotBeBlank else Ok r

let emailHasAtT (r: Request) =
  if r.email.Contains '@' then Ok r else Error (EmailNotValid r.email)

let validateRequestT =
  nameNotBlankT
  >> Result.bind name50T
  >> Result.bind emailNotBlankT
  >> Result.bind emailHasAtT

What does validateRequestT return for the email kati.karu?

let typedBad = validateRequestT { request with email = "kati.karu" }

Error (EmailNotValid "kati.karu")

The error carries the offending email as data.

Text once, at the end

Each case is converted to text in one place, at the end of the pipeline; all the messages are together, so a translation changes one function, and a log can use a different one:

let errorText e =
  match e with
  | NameMustNotBeBlank -> "Name must not be blank"
  | NameTooLong n -> $"Name must not be longer than 50 chars ({n} given)"
  | EmailMustNotBeBlank -> "Email must not be blank"
  | EmailNotValid s -> $"Email {s} is not valid"
  | UserNotFound (UserId i) -> $"User {i} not found"
  | MailNotSent s -> $"Mail not sent: {s}"

What does Result.mapError errorText make of the error above, typedBad?

let typedBadText = typedBad |> Result.mapError errorText

Error "Email kati.karu is not valid"

Result.mapError is the translation at a boundary: the same mapError turns a library's error cases into the use case's own. The typed pipeline in full is worked example B.

Constrained types

An email address is not just a string. A one-case union (lecture 5's StudentId) keeps it distinct, and a function that builds it is a switch:

type EmailAddress = EmailAddress of string

let createEmail (s: string) =
  if s.Contains '@' then Ok (EmailAddress s)
  else Error (EmailNotValid s)

What are createEmail "kati@taltech.ee" and createEmail "kati"?

let goodEmail = createEmail "kati@taltech.ee"
let badEmail = createEmail "kati"

Ok (EmailAddress "kati@taltech.ee")

Error (EmailNotValid "kati")

In a project the constructor is made private to its module, so that createEmail is the only way to obtain an EmailAddress, and every EmailAddress in the program is a valid one.

Illegal states unrepresentable

Lecture 5 said that a type is a promise. Errors as types and constrained types are the same idea: a value that reaches the Ok track has been checked, and the type says so. Wlaschin's example: "a contact must have an email or a postal address". A record with two optional fields allows a contact with neither; a union with the cases email only, address only and both makes the rule a type, and the invalid contact cannot be written down.

All errors at once?

The chain reports the first error only: a form with a blank name and a bad email tells the user about the name, and about the email only after the name is fixed. Wlaschin's picture of "parallel validation": the input goes to every switch, and the outputs are combined.

Collecting all errors needs a different error type, Result<'a, 'e list>, and a different way of combining the switches than bind, which stops at the first error. Exercise 2.

When not to use Result

Wlaschin's "Against railway oriented programming" lists the reasons not to: when you need a stack trace (diagnostics), when the workflow throws at the end anyway (fail fast), when nobody cares about the error (apathy), when every I/O error would have to be modelled, when performance or interoperability with other .NET code matters. Use Result for domain errors; leave panics and infrastructure failures to exceptions.

Wlaschin's deck goes one step further and carries domain events (information for later steps that is not an error, such as "mail sent") on the Ok track beside the value; that is beyond this lecture.

6 · No result, one result, many results: one shape

*option, Result and list answer "how many results?", and they share one composition shape.*

One shape

A function may return no result ('b option), one result or an error (Result<'b, 'e>) or many results ('b list). Each type has its bind, which turns such a function into a function on such values:

Option.bind  : ('a -> 'b option)       -> 'a option       -> 'b option
Result.bind  : ('a -> Result<'b, 'e>)  -> Result<'a, 'e>  -> Result<'b, 'e>
List.collect : ('a -> 'b list)         -> 'a list         -> 'b list

List.collect (lecture 4) is the bind of lists: for every element, the results of the function, all in one list.

let optionExample = Some 4 |> Option.bind (fun n -> if n > 0 then Some (n * 10) else None)
let resultExample = Ok 4 |> Result.bind (fun n -> if n > 0 then Ok (n * 10) else Error "not positive")
let listExample = [1; 2; 3] |> List.collect (fun n -> [n; n * 10])

Some 40

Ok 40

[1; 10; 2; 20; 3; 30]

Selecting positions

Lecture 6's selectors Here, Next, Seq (a, b) and Star a describe positions in a list; a position is the suffix of the list that starts there.

type Sel =
  | Here
  | Next
  | Seq of Sel * Sel
  | Star of Sel

reach d ys lists the suffixes d reaches in ys:

let rec reach d ys =
  match d, ys with
  | Here, _ -> [ys]
  | Next, [] -> []
  | Next, _ :: rest -> [rest]
  | Seq (a, b), _ ->
      reach a ys |> List.collect (reach b)
  | Star a, _ ->
      ys :: (reach a ys
             |> List.collect (reach (Star a)))

Seq (a, b): for every position a reaches, what b reaches from there — List.collect. How many positions does Seq (Star Next, Star Next) reach in ['a' .. 'e']? (An empty suffix is not a position.)

let reachCount =
  reach (Seq (Star Next, Star Next)) ['a' .. 'e']
  |> List.filter (not << List.isEmpty)
  |> List.length

15

Fifteen reaches of five positions: a position is reached once for every way of splitting the steps to it between the two Star Next. Each position is selected once however many ways reach it, so the selection keeps every position once (List.distinct). Worked example A completes the selector.

Summary

Wlaschin's recipe for handling errors in a functional way:

1. Use Result<'T, 'TError>: a function that can fail returns Ok or Error.
2. Turn switches into two-track functions with bind; fit one-track functions with map, dead ends with tee, throwing functions with tryCatch.
3. Compose the two-track functions with >>, as on the happy path.
4. Make the error cases a union: first-class, documented, converted to text once at the end.

And the shape of bind is the shape of Option.bind and List.collect.

Homework and reading

Homework 5 is out this week.

Reading: Scott Wlaschin, Railway Oriented Programming (https://fsharpforfunandprofit.com/rop/) and Against Railway-Oriented Programming (https://fsharpforfunandprofit.com/posts/against-railway-oriented-programming/); Scott Wlaschin, Domain Modeling Made Functional, chapter 10, "Implementation: Working with Errors".

The complete programs and the exercises follow.

Worked examples

Complete programs for self-study; every result is computed by the build.

A. Selecting positions in a list (lecture 6, exercise 3)

selectByDesc d xs returns the elements of xs that d selects, in list order and each once. A suffix identifies a position by its length; List.distinct removes the positions reached more than once:

let selectByDesc d xs =
  reach d xs
  |> List.filter (not << List.isEmpty)
  |> List.map (fun ys -> List.length xs - List.length ys)
  |> List.distinct
  |> List.sort
  |> List.map (fun i -> List.item i xs)

Lecture 6's table, recomputed:

let selHere = selectByDesc Here ['a' .. 'e']
let selNext = selectByDesc Next ['a' .. 'e']
let selHereNext = selectByDesc (Seq (Here, Next)) ['a' .. 'e']
let selNextNext = selectByDesc (Seq (Next, Next)) ['a' .. 'e']
let selStarNext = selectByDesc (Star Next) ['a' .. 'e']
let selStarNextNext = selectByDesc (Star (Seq (Next, Next))) ['a' .. 'e']
let selNextStar = selectByDesc (Seq (Next, Star (Seq (Next, Next)))) ['a' .. 'e']
let selStarStar = selectByDesc (Seq (Star Next, Star Next)) ['a' .. 'e']

['a']

['b']

['b']

['c']

['a'; 'b'; 'c'; 'd'; 'e']

['a'; 'c'; 'e']

['b'; 'd']

['a'; 'b'; 'c'; 'd'; 'e']

Equal values at different places are different elements: Star Next applied to [1; 1; 1]:

let selOnes = selectByDesc (Star Next) [1; 1; 1]

[1; 1; 1]

B. The typed pipeline in full

The use case over UseCaseError: the update step names the missing user, the mail step translates the exception's text into MailNotSent with Result.mapError (the translation at a boundary), returnMessageT uses errorText, and the composition is the one of concept 4.

let updateUserT (users: Users) (r: Request) =
  Map.tryFind r.userId users
  |> ofOption (UserNotFound r.userId)
  |> Result.map (fun u -> { u with name = r.name; email = r.email })

let returnMessageT (r: Result<Message, UseCaseError>) =
  match r with
  | Ok m -> $"Success: verification mail sent to {m.recipient}"
  | Error e -> errorText e

let executeUseCaseT (users: Users) =
  validateRequestT
  >> Result.map canonicalizeEmail
  >> Result.bind (updateUserT users)
  >> Result.bind (tryCatch sendEmail >> Result.mapError MailNotSent)
  >> returnMessageT

let runT = executeUseCaseT users
let okRunT = runT request
let badEmailRunT = runT { request with email = "kati.karu" }
let unknownRunT = runT { request with userId = UserId 9 }
let longNameT = runT { request with name = String.replicate 60 "x" }
let mailFailRunT = runT { request with email = "Kati@example.com" }

"Success: verification mail sent to kati.karu@taltech.ee"

"Email kati.karu is not valid"

"User 9 not found"

"Name must not be longer than 50 chars (60 given)"

"Mail not sent: no route to kati@example.com"

Exercises

Exercise 1: Result on search trees

From lecture 6: binary trees, insertion, the in-order list, the example tree t and the total tryRemoveMin.

type 'a BinTree =
  | Empty
  | Node of 'a BinTree * 'a * 'a BinTree

let leaf x = Node (Empty, x, Empty)

let rec insert x t =
  match t with
  | Empty -> Node (Empty, x, Empty)
  | Node (l, y, r) ->
      match compare x y with
      | 0 -> t
      | c when c < 0 -> Node (insert x l, y, r)
      | _ -> Node (l, y, insert x r)

let rec inOrder t =
  match t with
  | Empty -> []
  | Node (l, x, r) ->
      inOrder l @ [x] @ inOrder r

let t = Node (Node (leaf 2, 7, Empty),
              9,
              Node (leaf 13, 21, leaf 25))

let rec tryRemoveMin t =
  match t with
  | Empty -> None
  | Node (Empty, x, r) -> Some (x, r)
  | Node (l, x, r) ->
      tryRemoveMin l
      |> Option.map (fun (m, l') ->
           (m, Node (l', x, r)))

Lecture 6's remove x t returned t unchanged when x was not in it. Make the two ways of failing visible in the type:

type 'a TreeError =
  | EmptyTree
  | NotFound of 'a

(a) Define

removeMinR : 'a BinTree -> Result<'a * 'a BinTree, 'a TreeError>

which returns the smallest value and the remaining tree, or Error EmptyTree. For example, removeMinR Empty is Error EmptyTree, and removeMinR t gives 2 and a tree whose in-order list is [7; 9; 13; 21; 25].

(b) Define

removeR : 'a -> 'a BinTree -> Result<'a BinTree, 'a TreeError>

which removes x from a search tree, or fails with NotFound x when x is not in the tree. For example, removeR 9 t is Ok of a tree whose in-order list is [2; 7; 13; 21; 25], and removeR 4 t is Error (NotFound 4).

(c) Define

removeAll : 'a list -> 'a BinTree -> Result<'a BinTree, 'a TreeError>

which removes the values in order and stops at the first error (List.fold with Result.bind). For example, removeAll [2; 25] t is Ok of a tree whose in-order list is [7; 9; 13; 21], and removeAll [2; 4; 25] t is Error (NotFound 4).

(d) When is the silent remove the right function, when tryRemoveMin's option, and when removeR's Result?

Exercise 2: all errors at once

Define

validateAll : ('a -> Result<'a, 'e>) list -> 'a -> Result<'a, 'e list>

which applies every check in the list to the same input and returns Ok with the input when all pass, or Error with every error, in the order of the checks. For example, with the typed validations of concept 5:

• validateAll [nameNotBlankT; name50T; emailNotBlankT; emailHasAtT] { request with name = ""; email = "kati" } is Error [NameMustNotBeBlank; EmailNotValid "kati"];
• validateAll [nameNotBlankT; name50T; emailNotBlankT; emailHasAtT] request is Ok request.

Why can Result.bind not do this? What would bind have to look like for Result<'a, 'e list>?