Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>There are lots of different ways to solve problems in functional style. Often you start by analysing the problem in a different way than you would when designing an imperative algorithm, so writing an imperative algorithm and then "converting" it to a functional one doesn't produce very natural functional algorithms (and you often miss out on lots of the potential benefits of functional style). But when you're an experienced imperative programmer just starting out with functional programming, that's all you've got, and it is a good way to begin getting your head around the new concepts. So here's how you can approach "converting" such a function as the one you wrote to functional style in a fairly uncreative way (i.e. not coming up with a different algorithm).</p> <p>Lets just consider the <code>else</code> expression since the rest is fine.</p> <p>Functional style has no loops, so if you need run a block of code a number of times (the body of the imperative loop), that block of code must be a function. Often the function is a simple non-recursive one, and you call a higher-order function such as map or fold to do the actual recursion, but I'm going to presume you need the practice thinking recursively and want to see it explicitly. The loop condition is calculated from the quantities you have at hand in the loop body, so we just have the loop-replacement function recursively invoke itself depending on exactly the same condition:</p> <pre><code>} else { var cnt = 0 var i = 0 def loop(????) : ??? = { if (money - (i * coins.head) &gt; 0) { cnt += countChange_sort(money - (i * coins.head), coins.tail) i = i + 1 loop(????) } } loop(????) cnt } </code></pre> <p>Information is only communicated <em>to</em> a function through its input arguments or through its definition, and communicated <em>from</em> a function through its return value.</p> <p>The information that enters a function through its definition is constant when the function is created (either at compile time, or at runtime when the closure is created). Doesn't sound very useful for the information contained in <code>cnt</code> and <code>i</code>, which needs to be different on each call. So they obviously need to be passed in as arguments:</p> <pre><code>} else { var cnt = 0 var i = 0 def loop(cnt : Int, i : Int) : ??? = { if (money - (i * coins.head) &gt; 0) { cnt += countChange_sort(money - (i * coins.head), coins.tail) i = i + 1 loop(cnt, i) } } loop(cnt, i) cnt } </code></pre> <p>But we want to use the final value of <code>cnt</code> after the function call. If information is only communicated <strong>from</strong> <code>loop</code> through its return value, then we can only get the last value of <code>cnt</code> by having <code>loop</code> return it. That's pretty easy:</p> <pre><code>} else { var cnt = 0 var i = 0 def loop(cnt : Int, i : Int) : Int = { if (money - (i * coins.head) &gt; 0) { cnt += countChange_sort(money - (i * coins.head), coins.tail) i = i + 1 loop(cnt, i) } else { cnt } } cnt = loop(cnt, i) cnt } </code></pre> <p><code>coins</code>, <code>money</code>, and <code>countChange_sort</code> are examples of information "entering a function through its definition". <code>coins</code> and <code>money</code> are even "variable", but they're constant at the point when <code>loop</code> is defined. If you wanted to move <code>loop</code> out of the body of <code>countChange_sort</code> to become a stand-alone function, you would have to make <code>coins</code> and <code>money</code> additional arguments; they would be passed in from the top-level call in <code>countChange_sort</code>, and then passed down unmodified in each recursive call inside <code>loop</code>. That would still make <code>loop</code> dependent on <code>countChange_sort</code> itself though (as well as the arithmetic operators <code>*</code> and <code>-</code>!), so you never really get away from having the function know about external things that don't come into it through its arguments.</p> <p>Looking pretty good. But we're still using assignment statements inside <code>loop</code>, which isn't right. However all we do is assign new values to <code>cnt</code> and <code>i</code> and then pass them to a recursive invocation of <code>loop</code>, so those assignments can be easily removed:</p> <pre><code>} else { var cnt = 0 var i = 0 def loop(cnt : Int, i : Int) : Int = { if (money - (i * coins.head) &gt; 0) { loop(cnt + countChange_sort(money - (i * coins.head), coins.tail), i + 1) } else { cnt } } cnt = loop(cnt, i) cnt } </code></pre> <p>Now there are some obvious simplifications, because we're not really doing anything at all with the mutable <code>cnt</code> and <code>i</code> other than initialising them, and then passing their initial value, assigning to <code>cnt</code> once and then immediately returning it. So we can (finally) get rid of the mutable <code>cnt</code> and <code>i</code> entirely:</p> <pre><code>} else { def loop(cnt : Int, i : Int) : Int = { if (money - (i * coins.head) &gt; 0) { loop(cnt + countChange_sort(money - (i * coins.head), coins.tail), i + 1) } else { cnt } } loop(0, 0) } </code></pre> <p>And we're done! No side effects in sight!</p> <p>Note that I haven't thought much at all about what your algorithm actually does (I have made no attempt to even figure out whether it's actually correct, though I presume it is). All I've done is straightforwardly applied the general principle that information only enters a function through its arguments and leaves through its return values; all mutable state accessible to an expression is really extra hidden inputs and hidden outputs of the expression. Making them immutable <em>explicit</em> inputs and outputs, and then allows you to prune away unneeded ones. For example, <code>i</code> doesn't need to be included in the return value from <code>loop</code> because it's not actually needed by anything, so the conversion to functional style has made it clear that it's purely internal to <code>loop</code>, whereas you had to actually read the code of the imperative version to deduce this.</p> <p><code>cnt</code> and <code>i</code> are what is known as <em>accumulators</em>. Accumulators aren't anything special, they're just ordinary arguments; the term only refers to how they are used. Basically, if your algorithm needs to keep track of some data as it goes, you can introduce an accumulator parameter so that each recursive call can "pass forward" the data from what has been done so far. They often fill the role that local temporary mutable variables fill in imperative algorithms.</p> <p>It's quite a common pattern for the return value of a recursive function to be the value of an accumulator parameter once it is determined that there's no more work left to do, as happens with <code>cnt</code> in this case.</p> <p>Note that these sort of techniques don't necessarily produce <em>good</em> functional code, but it's very easy to convert functions implemented using "local" mutable state to functional style using this technique. Pervasive non-local use of mutability, such as is typical of most traditional OO programs, is harder to convert like this; you can do it, but you tend to have to modify the entire program at once, and the resulting functions have large numbers of extra arguments (explicitly exposing all the hidden data-flow that was present in original program).</p>
    singulars
    1. This table or related slice is empty.
    1. POTranslating snippet to functional from imperative
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USBen
    1. USBen
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POTranslating snippet to functional from imperative
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTAcceptedByOriginator
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COThank you very much!
      singulars
      1. PO
      1. USB. VB.
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

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