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
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.
numis 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.
Answered by user73941 on November 11, 2021
Get help from others!