22 October 2012

The Math of the First Scala Assignment

Math and Scala with a Little Bit of Clojure




Martin Odersky is teaching Functional Programming Principles in Scala on Coursera and I attempted to complete this course, I completed the first assignment on recursion before the hard deadline which was hard given my work schedule at the time, however, I decided not to submit it, I remembered how much I hate school, or at least being a student in a school even a virtual one, I have my own timeline and my own interests.  While doing the problems I realized, and I know this is not a major revelation, that these first three problems are set in the context of math.  However, some of that math may not be immediately obvious to everyone so I thought it would make a nice post.  I was originally going to publish my solutions in this post, after the hard deadline of course, but there was recently some unpleasantness about publishing solutions and cheating and it seems that it is still possibly a violation of the honor code.  I feel having some code for two of the problems increases the quality of this posting so I will provide my examples for those solutions in Clojure, the non solution code will be in Scala so it’s now a hybrid posting.  Also the ideas for this post forced me to finally write my previous post on Pascal’s Triangle, which this post will draw on.


Exercise 1: Pascal’s Triangle


The first problem is to recursively compute a binomial coefficient within Pascal’s triangle, this is fairly trivial if you have exposure to recurrence relations and recognize it as such, it is expressed as follows:




Some other common recurrence relations that are popular in CS educational circles include, Fibonacci numbers, triangular numbers and of course the factorial function these are expressed as:





I chose a term based representation of the factorial function over the more traditional:



These can be implemented recursively in Scala as:


 

def fibonacci(n : Int) : Long = {

if(n <= 1)

1

else

fibonacci(n - 1) + fibonacci(n - 2) 

}

 

def triangularNumber(n : Int) : Long = {

if(n <= 1)

1

else

n + triangularNumber(n - 1) 

}

 

def factorial(n : Int) : Long = {

if(n <= 1)

1

else

n * factorial(n - 1) 

}

 


All of the above examples are inefficient and in many cases considered to be naïve solutions.  The Fibonacci example is terrible as it incurs an exponential number of function calls, fortunately there ways to optimize these algorithms.  One potential approach would be to use the closed formulas for triangular numbers or Binet’s formula for Fibonacci numbers.  I will ignore those as I have covered them previously and they are not what I am going for here.  I want to look at two optimizations, one is a way is the use of the tail call optimization and the second is to reduce the number of function calls.


Tail call optimization, put simply, is a mechanism that allows certain recursive functions that are written in a tail recursive form to be converted to iteration when they are executed.  It is my understanding that this requires some extra work in the JVM, at least in the older versions, I think 7 and 8 makes changes for this.  So this extra work requires some special syntax beyond simply putting your code in tail recursive form, Lisp and Scheme for example do this automatically, in Scala this requires the @tailrec annotation, using this form our functions get converted as follows:


def triangularNumber(n:Int) : Long = {

 

@tailrec

def triangularNumberAcc(acc: Long, n: Int): Long = {

if (n <= 1) acc

else triangularNumberAcc(n + acc, n - 1)

}

 

triangularNumberAcc(1, n)

}

 

 

def factorial(n:Int) : Long = {

 

@tailrec

def factorialAcc(acc: Long, n: Int): Long = {

if (n <= 1) acc

else factorialAcc(n * acc, n - 1)

}

 

factorialAcc(1, n)

}


As you can see the tail recursive forms take on an accumulator parameter.  The other optimization  I mentioned was to get rid of the extra function call for the Fibonacci, this is done by calculating the series using a second accumulator parameter, so that term Fn and term Fn+1 are passed as accumulator parameters.   This following example came out really nice as the base function sequenceGenerator can also generate the Lucas numbers if seeded appropriately:


@tailrec

def sequenceGenerator(n: Int, t0: Long, t1: Long): Long = {

 

if(n <= 0)

t0

else

sequenceGenerator(n - 1, t1, t0 + t1)

}

 

 

def fibonacci(n : Int) : Long = {

 

sequenceGenerator(n, 0, 1)

}

 

 

def lucas(n : Int) : Long = {

 

sequenceGenerator(n, 2, 1)

}


Going back to Pascal’s Identity if we look at the example from my last post:



We can represent the values that get calculated for this example visually as:



This gives some sense of how the recursive solution moves up through the triangle to sum the values, the example code, in Clojure, the naïve solution is:


(defn bc [r c]

(if (or (<= c 0) (<= r 0) (<= r c))

1

(+ (bc (dec r) (dec c)) (bc (dec r) c))

)

)


Additionally the Clojure version of our Binomial Coefficient can be similarly single call/tail call optimized:


(defn bc [rr cc]

(loop [r rr c cc acc 1]

(if (or (= c 0) (= r 0) (= r c))

acc

(recur (dec r) (dec c) (/ (* acc r) c)))

)

)


As mentioned most of these have closed form formulas like Binet’s formula for Fibonacci numbers.  Also if we take the formula for the binomial coefficient and since r ≥ c we can get the following cancelation of c!:



Which can be implemented in Scala, using the factorial function defined above, as:


def partialFactorial(s : Int, e: Int) : Long = {

 

@tailrec

def partialFactorialAcc(s : Int, e: Int, acc: Long): Long = {

if(e >= s) acc

else  partialFactorialAcc(s - 1, e, s * acc)

}

 

partialFactorialAcc(e, s, e)

}

 

def binomialCoefficient(r : Int , c : Int) : Long = {

if((c <= 0) || (r <= 0) || (r <= c))

1

else

partialFactorial(r, c+1)/factorial(r-c)

}


Both of these two “optimized” solutions for the binomial coefficient introduce division which can be problematic due to remainders and floating point rounding errors this would also be the case for the closed form approaches to calculating these numbers.  There is a variant for the binomial coefficient that is discussed in a paper which uses a gcd calculation to try to deal with these issues.


Another interesting observation in terms of how values are calculated between the naïve recursive approach and the tail recursive accumulator approach is that there seems to be some order duality on how the calculations are performed.  In the naïve approaches the recursion goes to the bottom and accumulates as it comes back up in the call stack.  In the accumulator versions the values are accumulated on the way down and returned from the bottom of the call stack.


Exercise 2: Parentheses Balancing


The next problem is not so much about the solution as it is about the combinatorial properties of the input values.  The problem was to take a string and determine if the parenthesis in the string matched, this is also probably pretty common CS educational fodder.  So there will be no code for this problem.


The math that we are interested in here relates to the central binomial coefficient, it is a number sequence known as the Catalan numbers after the Belgian mathematician Eugène Charles Catalan.  It is given by the following equations:




In the original problem the text containing parentheses was the input, since a parenthesis counting algorithm would need to filter the text or implement some type of get next parenthesis function, we will assume that we have a string that only has only parenthesis.  First thing to notice that valid input strings need to be of even length.  Each term of the Catalan numbers describes how many possible sets of matching parenthesis you can have for each number n.  The table below illustrates the first five possibilities:


n

Cn

Matching parentheses set

Total String Size 22n

n=0

1 way

λ

0

n=1

1 way

()

2

n=2

2 ways

()(), (())

16

n=3

5 ways

()()(), ()(()), (())(), (()()), ((()))

64

n=4

14 ways

()()()(), ()()(()), ()(())(), ()(()()), ()((())),

(())()(), (())(()), (()())(), ((()))(), (()()()),

(()(())), ((())()), ((()())), (((())))

256

n=5

42 ways

()()()()(), ()()()(()), ()()(())(), ()()(()()), ()()((())),

()(())()(), ()(())(()), ()(()())(), ()((()))(), ()(()()()),

()(()(())), ()((())()), ()((()())), ()(((()))), (())()()(),

(())()(()), (())(())(), (())(()()), (())((())), (()())()(),

(()())(()), ((()))()(), ((()))(()), (()()())(), (()(()))(),

((())())(), ((()()))(), (((())))(), (()()()()), (()()(())),

(()(())()), (()(()())), (()((()))), ((())()()), ((())(())),

((()())()), (((()))()), ((()()())), ((()(()))), (((())())),

(((()()))), ((((()))))

1024


The table above also includes the number of possible strings with only the two parentheses, which grows at a rate 22n.  This table is based on one from a paper by Tom Davis on Catalan numbers.  It is quite interesting paper as Catalan numbers also describe diagonal avoiding paths, “mountain ranges”, noncrossing partitions, multiplication orderings, the number of different ways a convex polygon with n + 2 sides can be cut into triangles, to mention a few.  Another interesting thing about Catalan numbers is they can be described by a recurrence relation:







I confess that this may not be that pragmatic in terms of solving the problem, but I think it is interesting and possibly gives a larger context to the problem. 


Exercise 3: Counting Change


The last problem, which is probably something of a CS classic problem as it appears in SICP, is the problem of counting change, given some numerical amount and some set of coin denominations we need to count the number of ways that we can represent the amount given the set of denominations. I confess to having cheated a little bit, well ok a lot, I found this post by Bill the Lizard. I also found this post with a more elegant solution and translated these into both Scala and Clojure, well ok I guess it’s not cheating since I didn’t submit it.  The clojure version is:


(defn count-change [amount coin-values]

(cond (= amount 0) 1

(or (< amount 0) (empty? coin-values)) 0

:else

(+ (count-change amount (rest coin-values))

(count-change (- amount (first coin-values)) coin-values))

)

)


The math here is from number theory and combinatorics, actually it might fall under combinatorial number theory.  In number theory there are two pretty big areas, one is multiplicative number theory which dates back at least to the Greeks and deals with how numbers divide and remainders and prime numbers which includes things like the well known fundamental theorem of arithmetic.  A relatively newer area of number theory is known as arithmetic number theory and is mostly attributed to Euler. In fact it was Euler who initiated the study of number partitions in his book Introduction to the Analysis of the Infinite in 1748.  It is the math of number partitions that our change problem falls under.   We are basically counting a subset of the partitions of a number’s full partition set.  In fact we can create a function that uses a Clojure list comprehension to create a number partition function from our change counting function:


(defn number-partition [n]

(count-change n (for [x (range 1 (inc n))] x ))

)


Functions to count partitions have been studied over the years and Euler invented a generating function that gives rise to, you guessed it, a recurrence equation to count partitions:



School’s out


So there it is some (hopefully) interesting math context for these problems. I guess it’s kind of a gray area but I am pretty sure I didn’t cross the line on the whole honor code thing but even if I did I believe it’s covered by the People's Freedom of Choices and Voices Act.


Well it was a fun post to write, I got some code in a post, something I haven't done lately, which is only fitting for a blog called Elegant Coding, I think it came out pretty decent but remember I am still learning Scala and Clojure so my code examples here may not be as elegant as they could be.  I guess another objective of this post and my blog in general is to explore ways to mix programming and math education, while I think this post makes for a nice start along these lines, it could probably be improved which would be nice.



4 comments:

  1. AFAIK, @tailrec just instructs the compiler to generate a warning/error if the function cannot be tail call optimized. The Scala compiler will always attempt to apply TCO to any function otherwise. This is consistent with the documentation here: http://www.scala-lang.org/api/current/scala/annotation/tailrec.html

    ReplyDelete
  2. Check out some cool Clojure ways of doing Fibonacci Lazily:
    http://en.wikibooks.org/wiki/Clojure_Programming/Examples/Lazy_Fibonacci

    I especially liked the version using iterate: #6

    ReplyDelete
  3. You have a mistake in code:
    Should be
    partialFactorialAcc(s, e, e) not partialFactorialAcc(e, s, e)

    ReplyDelete
  4. Good analysis. Interesting to read the Maths perspective of this assignments

    ReplyDelete