It has been a while that I posted something (grad school applications !). For past few weeks I have been learning Standard ML (SML), my first foray into functional programming language. I must say, I was skeptical at first due to ‘no-state’ concept but it is turning out to be great experience. Recursion can only be appreciated when you have to write programs without loop. This makes me rethink about learning Scala and Haskell.

For a nice 73 slide introduction on SML see this. One of power of SML lies in doing proofs. For those who are already intiated with SML, you might want to look SML Proof Manipulation. If you want to learn how to start writing proofs in SML then here is a nice tutorial on the same Implementing Constructive Proof Rules for SML in MetaSML

I like to write Pascal’s triangle as my generic hello world program. Given below is my attempt at pascal’s triangle, a beautiful binomial expansion tree. Though I will confess that this is not the most elegant solution to Pascal’s triangle but I have considered readibility over conciseness.

1
2
3
4
5
6
7
8
9
10
11
12

fun choose(r : int, k : int) = 
    if k = 1 then r
    else if k =  orelse k = r then 1
    else choose(r-1,k) + choose(r-1,k-1)
 
fun pascal_triangle(x : int) =
    if (x <=1) then [[1]]
    else
        let fun count (from:int) =
            if from=x then 1::[] else choose(x,from) :: count(from+1)            
        in count()::pascal_triangle(x-1)
    end

*Note while the “choose” function could have been written as nested function inside “pascal_triangle” (like the “count” function), for the reasons of simplicity and comprehension I have put is as separate code. Same goes for the parenthesis around attributes, which are not required by the compiler.