Algorithms and data structures in rust - mergesort

Bets about rust are turning out to be right. Initially proposed as system programming language(read servo - rewrite of firefox browser) - numerous front end web frameworks are appearing and becoming ubiquitous. Rust has a steep learning curve - but that is a reasonable investment considering the low level power it gives to do system level things at the same time high level abstraction that comes without the price(zero cost). Borrow and ownership prevent memory issues, move semantics avoids data races, effort less C binding, avoidance of a runtime are some of the salient features of rust. Its implementation of Async & wait is also novel.

Its has been quite some time following the developments in rust - have been utilizing rust in one of my projects currently. I am going to be publishing some posts on rust and what better way than implementing algorithms and data structures to start with?

Following is an implementation of merge sort algorithm in rust. 

Rust allows defining local functions. Which is kind of neat & compact. Below is merge sort algorithm implemented using local functions. 




We make use of life times to return the sorted array. There does not seem to be an easy way to create arrays at runtime - the reason being arrays are allocated at the stack.

Source: https://github.com/ratulb/algos_in_rust

Quick sort routine in rust

A quick sort routine in rust:



Source: https://github.com/ratulb/algos_in_rust

Install PySpark on windows

1. Install java and expose JAVA_HOME
2. Install spark and expose SPARK_HOME
3. Install findspark:

Launch jupyter lab and use pyspark in notebook:

Kubernetes Secrets in plain English

Want to get a high level view of kubernetes secrets? Read on...

Back propagation in neural network training

Back propagation fundamental to neural network training. As always, Andrej Karpathy does a fantastic job explaining how it is calculated and applied during neural network training. Check this out!

The essence of a monad

Many people when they encounter the term 'monad' for the the first time, they decide to look it up, at least the curious bunch. But when they do consult the blogs, articles, Wikipedia, haskell documentations- explaining the term monad - they become deeply confused and angry at themselves for not being able to make any sense of it - at least people like me, whose brain is not bigger than the size of a peanut. They curse themselves and grok more blogs, articles, try to learn haskell in the hope that, may be this time they would be able to grasp it - but to no avail. Their brain hurts and they become even more confused. As they keep persisting in their efforts - they come across monads being described as elephants, space suits/burritos/fluffy clouds and what not! Some say - you need to know category theory to understand monad, some say no you do not - while people trying understand monad remain in a state of utter confusion for months or maybe years on end. This happened to me also - couple of years back(As I said before my brain is not bigger than a peanut!).

People say, "when you finally figure out what a monad is - you write a blog about it - that is a tradition". Well, I had decided to break with that tradition and not to write about it then - when that enlightenment happened! But I have now decided to go with tradition mainly because functional programming is being so ubiquitous and terms like monad/functors etc keep appearing all over the web and many people out their may be languishing to come to terms with monads. Hope this post would help them see what a monad is.

Then, why is monad so difficult to understand? I suppose there are couple of reasons for this. First, expectation on part of the person trying to understand monad. He/she expects monad to be self describing one whole thing. Once you read couple of blogs and articles, you expect to get a self explanatory picture of a concrete thing. That is a wrong expectation on the part of the learner. Monad is an abstraction of a design concept and there are different concrete implementations of this concept specific to particular problems. We need to keep this in mind.

Second, except for couple of blogs/presentations, people who try to explain monad to the uninitiated, are also, to some extent, to be blamed for the confusion they cause to the people trying learn monads. I just googled for "what is a monad" - opened three top links that came up.

This one straight away goes into examples like 'List comprehension', 'Input/Output', 'A parser' and ending with an example of 'Asynchronous programming'.The questioner was asking for a brief, succinct, practical explanation as to what a monad essentially is! Straight away jumping to some arbitrary examples does not help. Not to speak of the haskell syntax that may be unfamiliar to the user. So the user trying to learn monad become bewildered, deeply confused and perplexed. Here questioner's mistake was that - he asked for a a brief, succinct, practical explanation. That is a wrong expectation.

Second one from Wikipedia says, "In functional programming, a monad is a structure that represents computations defined as sequences of steps. A type with a monad structure defines what it means to chain operations, or nest functions of that type together. This allows the programmer to build pipelines that process data in steps, in which each action is decorated with additional processing rules provided by the monad". This one does not help. It sounds too abstract.

Another post mentions- "Douglas Crockford once said that monads are cursed – that once you understand monads for yourself you lose the ability to explain them to others". Then goes on to talk about 'Maybe' & JQuery being monad. This does not help either - why should we be not able to explain what a monad is?

All these and many more explanations have one thing in common. And that is that - they lack the motivation for monad and where it came from. That is where Brian Beckman: Don't fear the Monads and sigfpe shines. They talk about the motivation for monad.

So what is a monad?

In functional programming, functions are first class as is function composition. We build small functions and compose them to build bigger functions. So the way to tackle complexity is composition - it's of paramount importance. If functions do not compose, there arises an impedance mismatch. In pure functional languages like Haskell function are considered to be mathematical- no side effect, no logging, no exceptions. Same function called with same input should give the same output irrespective of who called it, when called it or however called it. Period. No deviation from this contract. But real world is not like this - Exception occur, latency happens, we need to handle unexpected result. So how do we account for these deviations? Well, taking recourse to monads of course! Monad is the vehicle we hop on to stay in course in face of these unavoidable deviations. Let's see some examples:

Example 1:

def getConnection(c: Credentials): Connection 

If we look at the signature of the method above carefully, we are lying about something! We are hiding something. What if the network is down or the database is down? We might not get a connection at all. We are not being explicit about this aspect of getConnection method failing to give us connection. That is where motivation for using or designing Maybe/Option monad comes from.

So the correct signature should be:

def getConnection(c: Credentials): Option[Connection]

If indeed getConnection returns a connection, we return Some(connection) or None if it fails. That we say beforehand so that caller may take alternate processing pipe line in the event of failing to get a connection.

While previous fails to compose, second composes and the signature speak out loudly what the contract is.

Example 2:

In scala, it is very idiomatic to do things like following:

 (1 to 10).toList.filter(_ % 2 == 0).flatMap(x => (0 to x).toList

Basically we like to keep piping or chaining output of one function call as the input to the other function till we compute our desired result(Like after each semi-colon we keep executing statement afer statement in imperative programming). But many very times output of one function call does not conform to the input of another function which is to say they do not compose. We need to coerce the output of a function to a format that can be fed as input to other function, we need to get rid of the impedance mismatch. That is the role flatMap/bind in monads. And each monad will have its own implementation of this method that is specific to the problem it is trying to solve. To drive home the point, we conjure up the following fictitious problem:

val urls = List("facebook.com", "twitter.com")

class Page

def getPage(url: String): Page = new Page

def outGoingLinks(page: Page): List[String] =List("bbc.com", "cnn.com")

What we want do to is this: we start with list of urls, crawl the pages corresponding to those urls & get the total count of outgoing urls for all those pages. To achieve this we have defined our functions above. So following is the call to get the job done:

 urls.map(url => getPage(url)).flatMap(page => outGoingLinks(page)).size

res5: Int = 4

And we are done. 'outGoingLinks' function takes a page and returns a List[String]. This is the crucial point to understand. So, when all the pages(here two) considered, the result would be List(List[String], List[String]). But this not what we want - we want List[String]. This where output is deviating. But 'flatMap' apart from calling the 'outGoingLinks' function for each page also does one more thing. It concatenates the List[List[String], List[String]) to one List[String]. 'flatMap' implementation in the case of List monad just happens to be that it takes a function (something) -> List[something] and concatenates the resulting lists into a single List[something] - so that we can stay the course. 'flatMap' guides you to the happy path as Erik Meijer(of Rx/Link fame) says while teaching 'Principles of Reactive Programming' . It keeps you from falling off the cliff.

So, monad is an abstraction of a design concept in functional programming and the motivation comes from recognizing the fact that composition is important. There are various implementation of this concept like Try, Either, Future, Option etc.

Of course, there are monadic laws that monad should hold. But they are not a prerequisite to an understanding of what the essence of monads is. When monads hold all three monad laws, it is a guarantee that they will not misbehave. In fact, the Try monad above holds only two of the monad laws and but for all practical purposes, it behaves like a monad. 

As a last note, monads are not specific to functional programming alone. The .Net implementation Rx(Reactive extention) has been ported to java by Netflix and it is all monadic underneath. Its changing the the whole game of event/stream processing and how to write reactive applications that scales up to millions of user requests.

It has been a long post. But hope it helps people who are trying to get on with monad and removes some of the mists surrounding monads.

Fun with scala's for comprehension: Solving sudoku in 11 lines!

Scala's for loop(comprehension) may look deceptively similar to java's for loop, but it is much more powerful than java's for loop. While java's for loop is just to repeat some computation for specified number of times, scala's for comprehension has a mathematical underpining to it. They are analogous to set comprehensions, which are normally used for building more specific sets out of general sets. Shown below is a basic set comprehension of 10 even natural numbers.

 S = {2*x; x <- N; x <= 10}

The first part 2*x is called the output, N is the input set and x <= 10 is the predicate filter. The same translated to for comprehension along with output is shown below:

scala> val s = for {

     |  x <- 1 to Integer.MAX_VALUE

     |  if(x <= 10)

     | } yield 2*x

s: (2, 4, 6, 8, 10, 12, 14, 16, 18, 20)

Problem: Given a positive integer n, find all the pairs of integers (i,j) such that 1 <= j < i < n, and i+j is a prime number.

Such combinatorial problems lend themselves to be solved beautifully with for comprehensions. Let's first define a function that tells us if a number is prime or not!

We know a number is a prime if it's only divisors are 1 and the number itself. While in imperative style we would start out with how to do it, in functional style we state what the problem is! So here goes our definition of isPrime.

scala> def isPrime(n: Int) = (2 until n).forall(d => n % d != 0)
isPrime: (n: Int)Boolean

Now, to find all the pairs of numbers such that each two elements of the pairs sum up to a prime number, we just make use of for comprehensions and the isPrime function defined above:

scala> def findPrimePairs(n: Int) =

     |  for {

     |   i <- 1 until n

     |   j <- 1 until i

     |   if isPrime(i+j)

     |  } yield(i,j)

findPrimePairs: (n: Int) IndexedSeq[(Int, Int)]

scala> val primePairs = findPrimePairs(10)

primePairs: IndexedSeq[(Int, Int)] = Vector((2,1), (3,2), (4,1), (4,3), (5,2), (6,1), (6,5), (7,4), (7,6), (8,3), (8,5), (9,2), (9,4), (9,8))

Neat, elegant and concise.

Let's try one more problem before we delve into solving sudoku in less than 11 line!

Let's try find the numbers x,y,z below n such that x^2 + y^2 == z^2. Let's call the function rightAngledNumbers!

scala> def rightAngledNumbers(n: Int) =
     |  for {
     |   x <- 1 until n
     |   y <- x+1 until n
     |   z <- y+1 until n
     |   if(x*x + y*y == z*z)
     |  } yield (x,y,z)

rightAngledNumbers: (n: Int)IndexedSeq[(Int, Int, Int)]

val result = rightAngledNumbers(100)

result: = Vector((3,4,5), (5,12,13), (6,8,10), (7,24,25), (8,15,17), (9,12,15), (9,40,41), (10,24,26), (11,60,61), (12,16,20), (12,35,37), (13,84,85), (14,48,50), (15,20,25), (15,36,39), (16,30,34), (16,63,65), (18,24,30), (18,80,82), (20,21,29), (20,48,52), (21,28,35), (21,72,75), (24,32,40), (24,45,51), (24,70,74), (25,60,65), (27,36,45), (28,45,53), (30,40,50), (30,72,78), (32,60,68), (33,44,55), (33,56,65), (35,84,91), (36,48,60), (36,77,85), (39,52,65), (39,80,89), (40,42,58), (40,75,85), (42,56,70), (45,60,75), (48,55,73), (48,64,80), (51,68,85), (54,72,90), (57,76,95), (60,63,87), (65,72,97))

I am not sure how many lines of code will be needed, if we try to do the same thing in an imperative way!

Now, let's get back to solving sudoku in 11 lines. Let me clarify here - though our main logic of solving sudoku is confined to only 11 lines, yet the whole program is hardly but 11 lines. That is because, we have to do things like read the input from a file, index the cells with row, column and cell value etc. Also, we have to check on which box an empty cell falls along with a helper function to tell us if a particular value is allowed in an empty cell. Barring these, actual logic is, indeed confined to 11 lines. Let's first define few type aliases and show the function with 11 lines which solves the problem.

type Cell = (Int,Int,Int)

Cell represents a sudoku cell with ._1 being the value,._2 being the row and ._3

being column of the cell.

type Solutions = List[List[Cell]]

We can have more than one possible solution to a sudoku problem depending on how many cells are already filled in. That is why our Solutions type alias is List of List of Cells. Shown below is the function that solves the sudoku.

def fillCells(emptyCells: List[Cell]): Solutions = {
   if(emptyCells == Nil) List(List())
   else {
   for {
     filledCells <- fillCells(emptyCells.init)
     cellValue <- 1 to 9
     cell = (cellValue,emptyCells.last._2, emptyCells.last._3)
     if(isOk(cell, filledCells ::: nonEmpties))  
    } yield cell :: filledCells
   }}

Explanation: We first take all the empty cells. Out of these empty cells, take all but last one and call fillCells recursively, which in turn repeats the process until we hit the base case when we call fillCells(Nil) - this returns an empty list of list. Now call stack unfolds inside out, calling fillCells with one empty cell and trying fill that with one of the possible values in the range from 1 to 9 and checking if that value is ok(isOk) for that cell. If so, that cell is concatenated to the base case, giving us one partial solution. And process continues till we fill all the empty cells.

Shown below is couple of inputs and along with their solutions. The whole Sudoku code is to be found at:

https://github.com/ratulb/sudoku/

Problem 1:

1 9 0 2 0 0 8 0 0
4 0 7 0 9 0 0 0 0
0 3 0 0 0 1 4 0 0
0 0 3 0 0 0 0 0 2
9 8 0 0 0 0 0 7 3
2 0 0 0 0 0 6 0 0
0 0 5 3 0 0 0 1 0
0 0 0 0 4 0 9 0 6
0 0 9 0 0 6 0 5 4 


scala> val sol1: Sudoku.Solution = List(List((3,8,6), (8,8,4), (1,8,3), (2,8,1), (7,8,0), (2,7,7), (7,7,5), (5,7,3), (8,7,2), (1,7,1), (3,7,0), (8,6,8), (7,6,6), (9,6,5), (2,6,4), (4,6,1), (6,6,0), (9,5,8), (8,5,7), (5,5,5), (3,5,4), (4,5,3), (1,5,2), (7,5,1), (5,4,6), (2,4,5), (1,4,4), (6,4,3), (4,4,2), (4,3,7), (1,3,6), (8,3,5), (7,3,4), (9,3,3), (6,3,1), (5,3,0), (5,2,8), (9,2,7), (6,2,4), (7,2,3), (2,2,2), (8,2,0), (1,1,8), (6,1,7), (2,1,6), (3,1,5), (8,1,3), (5,1,1), (7,0,8), (3,0,7), (4,0,5), (5,0,4), (6,0,2)))

Problem 2:

0 0 6 9 0 0 3 0 1
0 0 4 0 3 1 0 0 7
2 0 0 0 0 0 0 6 0
1 0 0 0 0 0 0 0 0
0 2 0 7 0 3 0 8 0
0 0 0 0 0 0 0 0 3
0 4 0 0 0 0 0 0 2
3 0 0 1 7 0 9 0 0
8 0 9 0 0 2 1 0 0

scala> val sol2 = Sudoku.solution
sol2: Sudoku.Solution = List(List((6,8,8), (3,8,7), (4,8,4), (5,8,3), (7,8,1), (8,7,8), (4,7,7), (6,7,5), (2,7,2), (5,7,1), (7,6,7), (5,6,6), (9,6,5), (8,6,4), (3,6,3), (1,6,2), (6,6,0), (1,5,7), (7,5,6), (5,5,5), (9,5,4), (2,5,3), (8,5,2), (6,5,1), (4,5,0), (4,4,8), (6,4,6), (1,4,4), (5,4,2), (9,4,0), (5,3,8), (9,3,7), (2,3,6), (8,3,5), (6,3,4), (4,3,3), (7,3,2), (3,3,1), (9,2,8), (4,2,6), (7,2,5), (5,2,4), (8,2,3), (3,2,2), (1,2,1), (2,1,7), (8,1,6), (6,1,3), (9,1,1), (5,1,0), (5,0,7), (4,0,5), (2,0,4), (8,0,1), (7,0,0)))

Following listing shows the complete sudoku code.

import io.Source
object Sudoku {
  type Input = List[List[Int]]
  type Cell = (Int,Int,Int)
  type Solutions = List[List[Cell]]
 def readFile = {
  val lines = io.Source.fromFile("sudoku1.txt").getLines.toList
  lines.map { line => line.split(" ").toList.map(e => e.toInt)
 }
}
 def solution = {
  val in = readFile
  val cells = index(in)
  val empties = emptyCells(cells)
  val nonEmpties = nonEmptyCells(cells)
  solve(empties,nonEmpties)
 }
 def solve(empties: List[Cell], nonEmpties: List[Cell]): Solutions = {
  //Actual logic
  def fillCells(emptyCells: List[Cell]): Solutions = {
   if(emptyCells == Nil) List(List())
   else {
   for {
     filledCells <- fillCells(emptyCells.init)
     cellValue <- 1 to 9
     cell = (cellValue,emptyCells.last._2, emptyCells.last._3)
     if(isOk(cell, filledCells ::: nonEmpties))
    } yield cell :: filledCells
   }
  }
  fillCells(empties)
 }
 def isOk(c:Cell, cells: List[Cell]) = {
  (colCells(c,cells) ::: rowCells(c,cells) ::: boxCells(c,cells)).forall(e => e._1 != c._1)
 }
 def colCells(c: Cell, cells: List[Cell]) = cells.filter(e => e._3 == c._3)
 def rowCells(c: Cell, cells: List[Cell]) = cells.filter(e => e._2 == c._2)
 def emptyCells(cells: List[Cell]) = cells.filter(e => e._1 == 0) 

 def nonEmptyCells(cells: List[Cell]) = cells.filterNot(e => e._1 == 0) 

 def boxCells(c: Cell, cells: List[Cell]) = {
  val inBox = cellAt(c)
  val filtered = inBox match {
    case 1 => cells.filter{e =>(e._2 < 3 && e._3 < 3)}
    case 2 => cells.filter{e =>(e._2 < 3 && (e._3 > 2 && e._3 < 6))}
    case 3 => cells.filter{e => (e._2 < 3 && e._3 > 5)}
    case 4 => cells.filter{e => ((e._2 > 2 && e._2 < 6) && e._3 < 3)}
    case 5 => cells.filter{e => ((e._2 > 2 && e._2 < 6) && (e._3 > 2 && e._3 < 6))}
    case 6 => cells.filter{e => ((e._2 > 2 && e._2 < 6) && (e._3 > 5))}
    case 7 => cells.filter{e => (e._2 > 5 && e._3 < 3)}
    case 8 => cells.filter{e => (e._2 > 5 && (e._3 > 2 && e._3 < 6))}
    case 9 => cells.filter{e => (e._2 > 5 && e._3 > 5)}
  }
 filtered
 }
 def index(in: Input) = in.zipWithIndex.map{r => r._1.zipWithIndex.map { c => (c._1, r._2, c._2) }}.flatMap(l => l) 

 def cellAt(c: Cell) = c match {
   case (_,x,y) if(x < 3 && y < 3) => 1
   case (_,x,y) if (x < 3 && ( y > 2 && y < 6)) => 2
   case (_,x,y) if (x < 3 && (y > 5 && y < 9)) => 3
   case (_,x,y) if ((x > 2 && x < 6) && y < 3) => 4
   case (_,x,y) if ((x > 2 && x < 6) && (y > 2 && y < 6)) => 5
   case (_,x,y) if ((x > 2 && x < 6) && (y > 5 && y < 9)) => 6
   case (_,x,y) if (x > 5 && y < 3) => 7
   case (_,x,y) if (x > 5 && (y > 2 && y < 6)) => 8
   case _ => 9
 }
}

Conclusion: Scala's for comprehensions might look very ordinary - but they are not. They turn out to be extremely handy while trying to solve combinatorial problems like the ones shown above. Like many other constructs of functional programming, for comprehensions allow programmers to tackle complicated problems from a higher level of abstraction.