4
\$\begingroup\$

How can I make the solution to this https://www.codewars.com/kata/5506b230a11c0aeab3000c1f/train/fsharp more "functional"?

module Evaporator
    let evaporator (content: double) (evapPerDay: double) (threshold: double): int =
        let minUsefulAmount = content * (threshold / 100.)
        let evapAsPercentage = evapPerDay / 100.
        let rec solve (content: double) (dayCount: int) =
            let amountLost = content * evapAsPercentage
            let newContent = content - amountLost
            let stillUseful = newContent > minUsefulAmount
            let result = 
                match stillUseful with
                | true -> solve newContent dayCount + 1
                | false -> dayCount
            result
        solve content 1
  
\$\endgroup\$
1
  • \$\begingroup\$ Hello, to increase odds of receiving more answers you could add the description of the task to the link you already provided and the tag programming-challenge. \$\endgroup\$ Jul 4, 2020 at 5:16

1 Answer 1

2
\$\begingroup\$

The first thing that comes into my mind is that if evapPerDay is <= 0 the function will continue infinitely - or more precise: until a stack overflow is encountered. So you have to guard against that:

let evaporatorReview (content: float) (evapPerDay: float) (threshold: float): int =
    if evapPerDay <= 0. then 
        failwith "evapPerDay must be greater than 0.0"
    else
        // ... The original algorithm

The next is that by having the unnecessary local result variable solve() isn't tail recursive. You can fix that by simply return directly from the match-entries:

let evaporator (content: float) (evapPerDay: float) (threshold: float): int =
    let minUsefulAmount = content * (threshold / 100.)
    let evapAsPercentage = evapPerDay / 100.

    let rec solve (content: float) (dayCount: int) =
        let amountLost = content * evapAsPercentage
        let newContent = content - amountLost
        let stillUseful = newContent > minUsefulAmount

        match stillUseful with
        | true -> solve newContent (dayCount + 1)
        | false -> dayCount
    solve content 1

IMO all the temporary variables in solve() blur what actually is going on. By skipping them and do the calculations directly in the recursive call to solve() the picture is more clear:

let evaporator (content: float) (evapPerDay: float) (threshold: float): int =
    if evapPerDay <= 0. then 
        failwith "evapPerDay must be greater than 0.0"
    else
        let limit = content * threshold / 100.
        let rec solve (content: float) (dayCount: int) =
            match content with
            | x when x <= limit -> dayCount
            | _ -> solve (content * (1. - evapPerDay / 100.)) (dayCount + 1)

        solve content 0

In fact you don't have to calculate on the content, you can do it percentage wise:

let evaporatorReview (content: float) (evapPerDay: float) (threshold: float): int =
    if evapPerDay <= 0. then 
        failwith "evapPerDay must be greater than 0.0"
    else
        let limit = threshold / 100.
        let rec solve (remaining: float) (dayCount: int) =
            match remaining with
            | x when x <= limit -> dayCount
            | _ -> solve (remaining * (1. - evapPerDay / 100.)) (dayCount + 1)

        solve 1. 0

The mathematical "discipline" in question here is exponential growth (r > 0) or decay (r < 0) and there is a formula for that:

Xn = X0 * (1 + r)^n

Where Xn is threshold, X0 is 100 or content, r is evapPerDay / 100. and n is the number of days = the result.

This can be use in sequential calculations ending when the threshold is met:

let evaporatorSeq (content: float) (evapPerDay: float) (threshold: float): int =
    if evapPerDay <= 0. then 
        failwith "evapPerDay must be greater than 0.0"
    else
        let limit = threshold / 100.0
        Seq.initInfinite (fun i -> i) 
        |> Seq.takeWhile (fun n -> Math.Pow(1.0 - evapPerDay / 100.0, float n) > limit)
        |> Seq.last
        |> (+) 1

But even better, it can be solved in respect to n as :

n = log(Xn/X0) / log(1 + r)

which can be used in the function as an O(1) - solution:

let evaporator content evapPerDay threshold = 
    match evapPerDay with
    | x when x = 100. -> 1
    | x when x <= 0.0 -> failwith "evapPerDay must be greater than 0.0"
    | _ -> int (Math.Ceiling(Math.Log((threshold / 100.) / 1.) / Math.Log(1. - evapPerDay / 100.)))

The division by 1. is of cause redundant, but it emphasize the relation of the expression to its origin.

if evapPerDay = 100. then 1 is necessary here because if evapPerDay = 100 then Math.Log(1.0 - evapPerDay / 100.) becomes Math.Log(0.) which isn't defined.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.