StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Obviously, the 2 algorithms have a lot in common: the overall workflow/steps are virtually the same, the only difference is the specifics of what is happening in the steps. This is one place where functional approaches shine: you want to replace specific functions / evaluations while keeping the overall structure intact. </p> <p>Without going into details, looking at your code, you can see that: </p> <ol> <li>they use the same input V</li> <li>at each iteration, using V and some parameters, an updated value of V is produced</li> <li>at each iteration, using old and new V, and some parameters, a condition is evaluated - is the new V good enough, or should the algorithm continue?</li> </ol> <p>Here is a sketch on how you could approach it to avoid duplication:</p> <p>You can rephrase 2. as "at each iteration, we'll apply a function to the current value of V, which will return an updated value V' " - and obviously, that function has signature <code>Updater: fun 't -> 't</code> (the Updater function takes in an input of type t, and returns an output of same type). </p> <p>Similarly, step 3 can be stated as "at each step, we'll apply a function to the pair (V, V'), which will tell us if yes or no this is good enough" - and this function needs a signature like <code>Finished: fun ('t * 't) -> bool</code>. (Given a tuple of two items of type 't, evaluate and give me a true/false answer). </p> <p>You can now extract out the specifics of the Updater and Finished functions, and pass them as arguments to the main algorithm (let's call the loop Search), along these lines:</p> <pre><code>let Search (Updater: fun 't -> 't) (Finished: fun ('t * 't) -> bool) currentV: 't = v' = v while not Finished (v, v') v' <- Updater v return v </code></pre> <p>(Example above is actually not quite right, but conveys the spirit. You would typically write this as a recursion in a functional style, which would look like that:</p> <pre><code>let rec Search (Updater: fun 't -> 't) (Finished: fun ('t * 't) -> bool) currentV: 't = if Finished (v, v') then return v' else Search Updater Finished v' </code></pre> <p>Now instead of having to rewrite the overall loop, you can define specific functions you want to apply for the update step and finish step, and your code duplication is gone - the overall loop/structure remains unchanged, and you just write functions that are completely specific to the problem at hand. </p> <p>I did lots of hand-waving here, hopefully this helps. If you are interested, I can provide a code sample in F# or C# illustrating the idea on working code.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload