Converting a float to a fraction as a string

Question

I was inspired by this video by Matt Parker to use the Farey Sequence to convert a float into a string representation of a fraction, how did I do? How well did I follow F# workflow and patterns (I'm new to the language)? Can it be done better, or rather, how would a "professional" F# developer write this function? Thanks in advance!

let toFraction num =
  let rec farey n0 d0 n1 d1 =
    let n2 = n0 + n1
    let d2 = d0 + d1

    match (n2 / d2) with
    | x when abs (x - num) < 1e-5 -> string n2 + " / " + string d2
    | x when x < num -> farey n2 d2 n1 d1
    | x when x > num -> farey n0 d0 n2 d2
    | _ -> "" // Compiler detects "incomplete pattern matches on this expression without this wildcard, 
    // maybe this is where my method can be improved?

  farey 0. 1. 1. 1.

Additionally, this problem assumes the input num is in the set 0 <= num < 1

Answer 1

There isn't much to say about the function and algorithm it self. It's an ordinary recursive function - with tail call - which is optimal for recursive functions.

I don't find a string as return value really useful. Instead I think, I would return a tuple of two integers representing the numerator and denominator

let toFraction (num: float): (int * int) = etc...

Alternatively you could define a discriminated union as something like:

type Fraction = Fraction of int * int

... used like:

let toFraction num =
if num <= 0.0 || num >= 1.0 then
    failwith "Invalid input"
else
  let rec farey n0 d0 n1 d1 =
    let n2 = n0 + n1
    let d2 = d0 + d1

    match float n2 / float d2 with
    | x when abs (x - num) < 1e-10 -> Fraction(n2, d2)
    | x when x < num -> farey n2 d2 n1 d1
    | x when x > num -> farey n0 d0 n2 d2
    | _ -> failwith "Something went completely wrong" // just to fulfill the pattern matching - it should never happen

  farey 0 1 1 1

and called as

let (Fraction(num, denom)) = toFraction value
printfn "%d / %d" num denom

As shown, I've chosen to run farey with integers instead of floats. You should test if that is more efficient than using floats.

---

match (n2 / d2) with

You don't need the parentheses.

---

num is in the set 0 <= num < 1

0 = num is an edge case that is calculated wrongly to

1 / 100001

If you want 0 to be included in the domain, you need to start faray with the values -1 0 1 1. Then it will return "0 / 1".

---

Even though you specify in the comment, that it is assumed that num should be between zero and one, you should guard against invalid input, especially because invalid input may result in an infinite recursive loop.