

I'm working through the Functional Programming in Scala track on Coursera; one of the early exercises consists of writing a recursive algorithm to calculate an element in Pascal's Triangle for a given row and column. The function should have the following signature:
pascal(c: Int, r: Int): Int
I should say upfront that I'm not looking for help with the exercise. It was fairly easy to solve:
def pascal(c: Int, r: Int): Int = { if (c == 0  c == r) 1 else pascal(c  1, r  1) + pascal(c, r  1) }
This is simple and works, but is inefficient. I uncovered a bug while working at a (less readable) more efficient implementation, and I'm at my wit's end trying to understand it. The revised algorithm is simple enough. Here's a working version in JavaScript (written to prove that the algorithm works, and to preserve my sanity):
function pascal(c, r) { function loop(c, r) { return (c == 0) ? 1 : (loop(c  1, r) * ((r + 1  c) / c)) }
return (c * 2 > r) ? loop(r  c, r) : loop(c, r) }
// A few tests; All pass pascal(0, 0) == 1 pascal(1, 2) == 2 pascal(0, 4) == 1 pascal(1, 4) == 4 pascal(2, 4) == 6
However, an apparently identical implementation in Scala yields unexpected results, and I can't see why. I've even resulted to manual execution with pen and paper (haven't managed to get the IntelliJ debugger working yet).
def pascal(c: Int, r: Int): Int = { def loop(c: Int, r: Int): Int = { if (c == 0) 1 else loop(c  1, r) * ((r + 1  c) / c) }
if (c * 2 > r) loop(r  c, r) else loop(c, r) }
// Same tests; The last fails pascal(0, 0) == 1 pascal(1, 2) == 2 pascal(0, 4) == 1 pascal(1, 4) == 4 pascal(2, 4) == 4 !!! < WHY NOT 6?!
Any light that can be shed would be greatly appreciated. I've only just started digging into Scala, and have been quite pleasantly surprised so far. This has been the first unpleasant surprise. I feel sure it's just a gap in my early Scala knowledge and someone more experienced will spot the issue quickly. Thanks!

You received this message because you are subscribed to the Google Groups "scalauser" group.
To unsubscribe from this group and stop receiving emails from it, send an email to [hidden email].
For more options, visit https://groups.google.com/d/optout.



You received this message because you are subscribed to the Google Groups "scalauser" group.
To unsubscribe from this group and stop receiving emails from it, send an email to [hidden email].
For more options, visit https://groups.google.com/d/optout.


Brian,
Thanks for the reply! I realized this morning that the problem was truncating integer division. I was able to fix my implementation easily in this case by moving parentheses around.
def pascal(c: Int, r: Int): Int = { def loop(c: Int, r: Int): Int = { if (c == 0) 1 else (loop(c  1, r) * (r + 1  c)) / c }
if (c * 2 > r) loop(r  c, r) else loop(c, r) }
As a followup question, what strategies are helpful for avoiding lurking bugs from precision killing integer division? I come from a background in mostly dynamically typed languages where division operators typically do the expected thing with more/less safety. On Thursday, January 12, 2017 at 3:54:08 PM UTC5, BrianS wrote: Hi Will
It boils down to this:
In Scala, Int / Int = Int
In ECMAScript, the result of dividing is always a Double.
Kind regards
Brian On 12 January 2017 at 06:02, Will Clardy <<a href="javascript:" target="_blank" gdfobfuscatedmailto="PQmtJxwKAAAJ" rel="nofollow" onmousedown="this.href='javascript:';return true;" onclick="this.href='javascript:';return true;">que...@...> wrote: I'm working through the Functional Programming in Scala track on Coursera; one of the early exercises consists of writing a recursive algorithm to calculate an element in Pascal's Triangle for a given row and column. The function should have the following signature:
pascal(c: Int, r: Int): Int
I should say upfront that I'm not looking for help with the exercise. It was fairly easy to solve:
def pascal(c: Int, r: Int): Int = { if (c == 0  c == r) 1 else pascal(c  1, r  1) + pascal(c, r  1) }
This is simple and works, but is inefficient. I uncovered a bug while working at a (less readable) more efficient implementation, and I'm at my wit's end trying to understand it. The revised algorithm is simple enough. Here's a working version in JavaScript (written to prove that the algorithm works, and to preserve my sanity):
function pascal(c, r) { function loop(c, r) { return (c == 0) ? 1 : (loop(c  1, r) * ((r + 1  c) / c)) }
return (c * 2 > r) ? loop(r  c, r) : loop(c, r) }
// A few tests; All pass pascal(0, 0) == 1 pascal(1, 2) == 2 pascal(0, 4) == 1 pascal(1, 4) == 4 pascal(2, 4) == 6
However, an apparently identical implementation in Scala yields unexpected results, and I can't see why. I've even resulted to manual execution with pen and paper (haven't managed to get the IntelliJ debugger working yet).
def pascal(c: Int, r: Int): Int = { def loop(c: Int, r: Int): Int = { if (c == 0) 1 else loop(c  1, r) * ((r + 1  c) / c) }
if (c * 2 > r) loop(r  c, r) else loop(c, r) }
// Same tests; The last fails pascal(0, 0) == 1 pascal(1, 2) == 2 pascal(0, 4) == 1 pascal(1, 4) == 4 pascal(2, 4) == 4 !!! < WHY NOT 6?!
Any light that can be shed would be greatly appreciated. I've only just started digging into Scala, and have been quite pleasantly surprised so far. This has been the first unpleasant surprise. I feel sure it's just a gap in my early Scala knowledge and someone more experienced will spot the issue quickly. Thanks!

You received this message because you are subscribed to the Google Groups "scalauser" group.
To unsubscribe from this group and stop receiving emails from it, send an email to <a href="javascript:" target="_blank" gdfobfuscatedmailto="PQmtJxwKAAAJ" rel="nofollow" onmousedown="this.href='javascript:';return true;" onclick="this.href='javascript:';return true;">scalauser+...@googlegroups.com.
For more options, visit <a href="https://groups.google.com/d/optout" target="_blank" rel="nofollow" onmousedown="this.href='https://groups.google.com/d/optout';return true;" onclick="this.href='https://groups.google.com/d/optout';return true;">https://groups.google.com/d/optout.

You received this message because you are subscribed to the Google Groups "scalauser" group.
To unsubscribe from this group and stop receiving emails from it, send an email to [hidden email].
For more options, visit https://groups.google.com/d/optout.


I'm deleting the original post since it included an answer to the exercise. There are plenty of places online to look up information about integer division so it's not helpful to have this around.

You received this message because you are subscribed to the Google Groups "scalauser" group.
To unsubscribe from this group and stop receiving emails from it, send an email to [hidden email].
For more options, visit https://groups.google.com/d/optout.

