Monthly Archives: November 2014

Functional Programming Principles in Scala (1)

This is online course, named functional programming principles in Scala. I use this course to practice my Scala programming. So here I do summary of my solutions according to its assignments online. Please I don’t follow its restriction, I only want to implement my solution by Scala. Don’t compare my idea with their online course exactly. Follow your heart. 🙂

Exercise 1: Pascal’s Triangle.

Do this exercise by implementing the pascal function, which takes a column c and a row r, counting from 0 and returns the number at that spot in the triangle. For example,pascal(0,2)=1, pascal(1,2)=2 and pascal(1,3)=3

def pascal(c: Int, r: Int): Int = {
  if (c == 0 || c == r) 1
  else pascal(c - 1, r - 1) + pascal(c, r - 1)
}
pascal(0, 2) // output: 1
pascal(1, 2) // output: 2
pascal(1, 3) // output: 3

Exercise 2: Parentheses Balancing

Write a function which verifies the balancing of parentheses in a string, which we represent as a List[Char] not a String. For example, the function should return true for the following strings:

  • (if (zero? x) max (/ 1 x))
  • I told him (that it’s not (yet) done). (But he wasn’t listening)

The function should return false for the following strings:

  • 🙂
  • ())(

The last example shows that it’s not enough to verify that a string contains the same number of opening and closing parentheses.

import scala.collection.mutable.Stack
def balance(chars: List[Char]): Boolean = {
  val stack = new Stack[Char]()
  var flag = true
  for (c <- chars if flag == true) {
    if (c == '(') stack.push(c)
    else if (c == ')') {
      if (stack.size == 0) flag = false
      else stack.pop
    }
  }
  if (stack.size == 0 && flag == true) flag = true
  else flag = false
  flag
}
balance("(if (zero? x) max (/ 1 x))".toList) // output: true
balance("I told him (that it’s not (yet) done). (But he wasn’t listening)".toList) // output: true
balance(":-)".toList) // output: false
balance("())(".toList) // output: false

Exercise 3: Counting Change

Write a recursive function that counts how many different ways you can make change for an amount, given a list of coin denominations. For example, there are 3 ways to give change for 4 if you have coins with denomination 1 and 2: 1+1+1+1, 1+1+2, 2+2.

def countChange(money: Int, coins: List[Int]): Int = {
  if (money <= 0) 0
  else if (money == 1) 1
  else {
    var sum: Int = 0
    for (coin <- coins) {
      sum += countChange(money - coin, coins)
    }
    sum
  }
}

countChange(4, List(1,2)) // output: 3

Scala (17): JDBC connection pool with Hive

JDBC means Java Database Connection. So when we need to read data from database, we use JDBC to get connection between application layer and database layer. In fact, we can directly connect with database by JDBC, why we need to use connection pool. The benefit of it is that a connection pool is a cache of database connections maintained so that the connections can be used when future requests to the database are required. Connection pools are used to enhance the performance of executing commands on a database.

Benefit

Dynamic web pages without connection pooling open connections to database services when they are needed and close them when the page is done servicing a particular request. Pages that use connection pooling instead maintain open connections in a pool. When the page requires access to the database, it simply uses an existing connection from the pool, and establishes a new connection only if no pooled connections are available. This reduces the overhead associated with connecting to the database to service individual request. To summarize, there are three advantages:

  1. In connection pool, connection or set of connection objects are created single time (usually at the start of the application)
  2. The connections can be reused when future requests to the database are required.
  3. It can enhance the performance of executing commands on a database.

Here our target database is Hive, first we need to start hive. Its default port is 10000.

./hive --service hiveserver -p 10002
Starting Hive Thrift Server

So you will see that you already start hiveserver on 10002, and then you can use java proxy to connect hiveserver.

There are several methods to do this thing; here we only introduce two ways, BoneCP and c3p0.

BoneCP

The reason why we use BoneCP is that Play 2.0 JDBC datasource is managed by it.

Configuration

You need to go build.sbt to add “jdbc”.

libraryDependencies ++ = Seq (
  jdbc,
  "mysql" % "mysql-connector-java" % "5.1.31",
  "org.apache.hive" % "hive-jdbc" % "0.12.0"
)

And then go to conf/application.conf to modify database engine connection properties.

db.orders.driver=org.h2.Driver
db.orders.url="jdbc:h2:mem:orders"
db.customers.driver=org.h2.Driver
db.customers.url="jdbc:h2:mem:customers"

Accessing the JDBC datasource

import play.api.db._
DB.withConnection("order") { conn =>
  // TODO
}
DB.withConnection("customers") { conn =>
  // TODO
}

If you use default configuration, you only need to use “DB.withConnection” to get connection.

c3p0

Configuration

The build.sbt part is partially same with BoneCp. We need to add one more.

"com.mchange" % "c3p0" % "0.9.2.1"

Accessing

import com.mchange.v2.c3p0.ComboPooledDataSource
// implement a datasource
val cpds = new ComboPooledDataSource()
cpds.setDriverClass(...)
cpds.setJdbcUrl(...)
cpds.setUser(...)
cpds.setPassword(...)
cpds.setInitialPoolSize(...)
// when number of connections is over than this value, you only can wait for the connection until other connection is free. 
cpds.setMaxPoolSize(...)
cpds.setMinPoolSize(...)
cpds.setMaxStatements(...)
// get a connection
cpds.getConnection
cpds.getJdbcUrl

Scala (15): Regular Expressions

In Scala, it supports regular expressions and provides API to implement it. Here we give example to show them one by one.

findFirstIn

import scala.util.matching.Regex
val pattern = "Scala".r // <=> val pattern = new Regex("Scala")
val str = "Scala is very cool"
val result = pattern findFirstIn str
result match {
  case Some(v) => println(v)
  case _ =>
} // output: Scala

Please note: findFirstIn returns a Option[T], so you need to use pattern matching to get real value.

findAllIn

import scala.util.matching.Regex
val pattern = "Scala".r
val str = "Scala is very cool"
val result = (pattern findAllIn str).mkString(",")
println(result) // Output: Scala

Please note: findAllIn returns non-empty iterator, you can use mkString to collect.

replaceFirstIn/replaceAllIn

import scala.util.matching.Regex
val pattern = "Scala".r
val str = "Scala is very cool "
val result = pattern replaceFirstIn(str, "Java") // String = Java is very cool
val result1 = pattern replaceAllIn(str, "Java") // String = Java is very cool

Please note: both replaceFirstIn and replaceAllIn return String.

Pattern Matching

val date = """(\d\d\d\d)-(\d\d)-(\d\d)""".r
"2014-11-20" match {
  case date(year, month, day) => "hello"
} // output: hello
val pattern = "(boo|foo).*".r
"boo123" match {
  case pattern(m) => m
  case _ => "no match"
} // output: boo
val pattern = "(boo|foo).{4}".r
"boo1234" match {
  case pattern(m) => m
  case _ => "no match"
} // output: boo

So in Scala, regular expression always combines with pattern matching to finish some tasks. And then, we do summary of some useful regular expressions.

  1. ^the” : a string which begins with “the”
  2. “of material$“: a string which ends with “of material”
  3. ^abc$“: a string which starts with “abc” and ends with “abc”, so exactly the string is “abc”
  4. “ab*“: a string which starts with “a”, and following is 0 or n-more “b”, like “a”, “ab”, “abb”, etc
  5. “ab+“: a string which starts with “a”, and following is 1-more “b”, like “ab”, “abb”, etc
  6. “ab?“: a string which starts with “a”, and following is 0 or 1 “b”, like “a”, “ab”
  7. “a?b+$“: a string which starts with 0 or 1 “a”, following is 1-more “b” as end
  8. “ab{2}“: there must be 2 “b”, exactly. “abb”
  9. “ab{2,}“: there must be 2-more “b”, like “abb”, “abbb”, etc
  10. “ab{3,5}“: there must be 3-5 “b”, like “abbb”, “abbbb”, “abbbbb”
  11. “a(bc)*“: there must be 0-more “bc”
  12. “hi|hello”: “hi” or “hello”
  13. “(b|cd)ef”: “bef” or “cdef”
  14. “.” can be expressed as any char, except ‘\n’
  15. “a.[0-9]“: “a” combines with any char and any number from 0 to 9

So, we only need to know important chars’s meaning, like: “^“, “$“, “?“, “.“, “+“, “{}“, “|“, “[]” and “*“. That’s enough.

Scala (12): How to select collection in different scenario

Scala provides so many powerful collections, but how to select the suitable in different scenario. We need to consider several factors.

Hierarchy

  • Iterable[T] is any collection that can be iterated over, they provide an iterator method  which gives us an Iterator to loop the elements) and foreach, Seq[T]s are collections that are ordered, Set[T]s are mathematical sets (unordered collections of unique items), and Map[T]s are associative arrays, also unordered.
    Screenshot 2016-05-13 14.27.59
  1. All collections can be traversed.
  2. Seq is Sequence of items with ordering.
  3. Set is a collection of items with no duplicates.
  4. Map is a key-value pairs.

Use

  • Iterable
def iterator: Iterator[A]
def hasNext(): Boolean
def next(): A
e.g.
Iterable(1,2,3) // Iterable[Int] = List(1,2,3)
val i = Iterable(1,2,3).iterator
i.hasNext // true
i.next() // Int = 1
  • Set
def contains(key: A): Boolean
def +(elem: A): Set[A]
def -(elem: A): Set[A]
e.g.
val s = Set(1,2,3)
s.contains(2) // output: True
s + 4 // Set(1,2,3,4)
s - 2 // Set(1,3)
  • Map
Map("a" -> 1, "b" -> 2)
Map(("a", 1), ("b", 2))

 

Scala (11): Type System

Why do we talk about type system in Scala? There are several reasons:

  1. The first one is that Scala allows us to define parameter’s type.
  2. We can make our class/function to be fit for different types. (generic programming or parametric polymorphism)
  3. Sometimes, Scala helps us to do type inference.
  4. We can limit the class/function’s type scope

I think the most important point is to implement generic programming in Scala. So first we talk about parametric polymorphism.

Parametric polymorphism

We use one example to explain it.

def drop1[A](l: List[A]) = l.tail
drop1(List(1,2,3))
drop1(List("a","b","c"))

Obviously, this function can be applied in Int, String and etc. We don’t need to write down two or more functions to satisfy different types; we only use type parameter to give a generic method to implement the function. It saves our time.

And then we talk about in some conditions, we don’t need to point out its type. Scala helps us to infer its type.

Type inference

Of course, we use codes to express how does Scala infer the type.

def id[T](x: T) = x
val x = id(322) // Int = 322
val x = id("hey") // java.lang.String = hey
val x = id(Array(1,3,4)) // Array[Int] = Array[1,3,4]

As you seen, it is quite easy for us to understand the return type; we don’t need to point out its type by ourselves.

It seems type system is so easy, right? No. Another problem is coming. If T” is a subclass of T, what is relationship between Container[T] and Container[T”]? Let’s talk about variance to express the relationship.

Variance

If T” is a subclass of T,

  1. covariant          [+T]          C[T”] is a subclass of C[T]
  2. contravariant   [-T]           C[T] is a subclass of C[T”]
  3. invariant           [T]           C[T] and C[T”] are not related

Here, I give each an example.

covariant

class Covariant[+A]
val cv: Covariant[AnyRef] = new Covariant[String]

contravariant

class Contravariant[-A]
val cv: Contravariant[String] = new Contravariant[AnyRef]

invariant

class Invariant[A]
val cv: Invariant[String] = new Invariant[String]

That’s all? oh, no. Scala allows us to restrict polymorphic variables by bounds, which express subtype relationships.

bounds

bounds can be separated to upper bounds and lower bounds.

upper bounds

upper bounds mean a type is another type’s sub-class, using extends(Java). For example:

T extends Test // Java
[T <: Test] // Scala
def pr(list: List[_ <: Any]) {
  list.foreach(println)
}

lower bounds

lower bounds mean a type is another type’s super-class, using super(Java). For example:

T super Test // Java
[T >: Test] // Scala
def append[T >: String](buf: ListBuffer[T]) = {
  buf.append("hi")
}

In fact, there is another kind of bounds, named view bounds.

view bounds

To be honest, I don’t know why its name is “view bounds”, here I only talk what I know. “view bounds” is related to implicit class; it demand a function exists for the given type. We can use “<%” to specify a view bound. Here is the example:

implicit def strToInt(x: String) = x.toInt
class Container[A <% Int]{def addInt(x: A) = 123 + x}
(new Container[String]).addInt("123") // Int = 246
(new Container[Int]).addInt(123) // Int = 246
(new Container[Float]).addInt(123.2F) 
// error: no implicit view available from Float=>Int

There are still other type of bounds. I will add them in the future when I really understand them.

That’s all for type system. It is quite useful when we need to implement generic programming.

Algorithm (2): Linked Lists

Before we enter into “Question and Answer” model, we need to know how to use LinkedList in Scala. In Scala, it already provides LinkedList collection directly. by “import scala.collection.mutable.LinkedList”.

import scala.collection.mutable.LinkedList
val temp = new LinkedList[String]
val temp1 = temp append LinkedList("abc", "efg")
println(temp1)
// output: LinkedList("abc", "efg")
// Note: now temp is still LinkedList()

2.1 Write code to remove duplicates from an unsorted linked list. Follow up: how would you solve this problem if a temporary buffer is not allowed?

import scala.collection.mutable.LinkedList
import scala.collection.mutable.HashMap
def removeDuplicate(data: LinkedList[String]): LinkedList[String] = {
  val record = new HashMap[String, Int]
  var dataTemp = data
  var previous: LinkedList[String] = LinkedList()
  while (dataTemp != LinkedList()) {
    if (record.isDefinedAt(dataTemp.elem)) {
      previous.next = dataTemp.next
    } else {
      record.put(dataTemp.elem, 1)
      previous = dataTemp
    }
    dataTemp = dataTemp.next
  }
  data
}

Here we use hashmap to store each element and its appearance time. We use record.isDefinedAt to check whether this key exists or not and use record.put to add new pair to map.

For linkedlist, we use dataTemp.elem to get current data and dataTemp.next to its tail: linkedlist. Also in Scala, you can directly use “dataTemp.distinct” to remove duplicates.

2.2 Implement an algorithm to find last n elements of a singly linked list

def getNth(data: LinkedList[String], n: Int): LinkedList[String] = {
  var length = 0
  var dataTemp = data
  while (dataTemp != LinkedList()) {
    length += 1
    dataTemp = dataTemp.next
  }
  if (n == length) {
    data
  } else if (n > length) {
    LinkedList()
  } else {
    dataTemp = data 
    var count = 1
    while (dataTemp != LinkedList() && count + n != length) {
      count += 1
      dataTemp = dataTemp.next
    }
    dataTemp.next
  }
}

Note: I change the question content which is different with the book.

2.3 Implement an algorithm to delete a node in the middle of a single linked list, given only access to that node.

Example:

Input: the node ‘c’ from the linked list a->b->c->d->e

Result: nothing is returned, but the new linked list looks like a->b->d->e

def removeMiddle(data: LinkedList[String], middle: String) = {
  var dataTemp = data
  var returnData = data
  var previous = data
  while(dataTemp.next.elem != middle) {
    previous = dataTemp.next
    dataTemp = dataTemp.next
  }
  previous.next = dataTemp.next.next
  println(returnData)
}

2.4 You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, such that 1’s digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list.

Example:

Input: (3->1->5), (5->9->2)

Output: 8->0->8

This question looks like to implement an add function for linked list.

def addLinkedList(first: LinkedList[Int], second: LinkedList[Int]): LinkedList[Int] = {
  var sum = LinkedList[Int]()
  var firstTemp = first
  var secondTemp = second
  var flag = 0
  while (firstTemp != LinkedList() && secondTemp != LinkedList()) {
    val temp = firstTemp.elem + secondTemp.elem + flag
    sum = sum append LinkedList(temp % 10)
    flag = if (temp <= 9) 0 else 1
    firstTemp = firstTemp.next
    secondTemp = secondTemp.next
  }
  if (firstTemp == LinkedList()) {
    while (secondTemp != LinkedList()) {
      val temp = secondTemp.elem + flag
      sum = sum append LinkedList(temp % 10)
      flag = if (temp <= 9) 0 else 1
      secondTemp = secondTemp.next
    }
  } 
  if (secondTemp == LinkedList()){
    while (firstTemp != LinkedList()) {
      val temp = firstTemp.elem + flag
      sum = sum append LinkedList(temp % 10)
      flag = if (temp <= 9) 0 else 1
      firstTemp = firstTemp.next
    }
  }
  if (flag != 0) {
    sum = sum append LinkedList(flag)
  }
  sum
}

2.5 Given a circular linked list, implement an algorithm which returns node at the beginning of the loop.

Definition:

Circular linked list: A(corrupt) linked list in which a node’s next pointer points to an earlier node, so as to make a loop in the linked list.

example:

Input: A->B->C->D->E->C [the same C as earlier]

Output: C

What is Typesafe Reactive Platform

I use Play Framework to build web application. I also use Akka and Spark in my projects. Currently, my programming language is Scala, even though in the past, I used C/C++, Python, and etc. But I’m still not really understand what is Typesafe Reactive Platform. In this post, I want to reveal its truth.

What is the Problem?

Every solution should try to solve one problem. So what is the problem which Typesafe Reactive Platform wants to deal with?

In the past, a large application had tens or so servers, seconds of response time, hours of offline maintenance and gigabytes of data. Old solutions emphasized on managing servers and containers. Scaling was achieved through buying more larger servers and concurrent processing via multi-threading.

But today applications are deployed on cloud-based clustering running thousands of multicore processors, dealing with thousand requests and handling petabytes. So old traditional scaling method is not suitable for new updated requirements.

What is Reactive Platform?

Because old solution is not good enough, we introduce a new solution, named Reactive Platform. This platform allows developers to build systems which are responsive resilient, elastic, and message-driven in order to deliver highly responsive user experiences with a real-time feel, backed by a elastic and resilient application stack, ready to be deployed on multicore and cloud computing architectures.

So Typesafe Reactive Platform is this kind of platform, which contains Play Framework, Akka, Scala, Activator and Spark. It is powerful tool to build modern applications that react to events, react to load, react to failure, and react to users.

If you want to know more detailed info, please go to read its document carefully. https://typesafe.com/platform