Project Euler 12 - Scala Streams, creating triangle numbers

Just a short blog today on Scala Streams and generating numeric progressions, such as a simple arithmetic series

This is a solution to project Euler problem 12: "What is the value of the first triangle number to have over five hundred divisors?"

This is actually a fairly easy problem to solve, providing you use a sufficiently efficient function to count the divisors!

The method I've adopted for this is particularly simple, but performs sufficiently well to solve this problem as stated within a few seconds.

Triangle Numbers:

Just a quick refresher, the triangle numbers are the sum of integers from 1 to n.

An Arithmetic series is a number series of the form:

a + (a + b) + (a + 2b) + ....

and using this form the Triangle numbers can be written as:

1 + (1 + 1) + (1 + 2) + (1 + 3) + ...

so they clearly are of the form of an Arithmetic series.


The more interesting aspect of this problem was the generation of the Triangle number sequence. Naturally, wanting to use Scala to solve this problem, the idea of using a Stream to evaluate the triangle number sequence lazily on demand is a natural approach.

The implementation I settled on to produce the Stream of triangle numbers was the iterative version as follows:

val trianglesI = Stream.iterate((1L,0L)){
            case (n, sum) => (n + 1L, sum + n) }.map(_._2)

Which is a fairly natural way to solve via the additive definition of the triangle numbers.

What's perhaps more interesting is finding some alternative ways to achieve the same thing, here are some alternatives to the iterative additive stream definition:

Using the multiplicative definition of the Triangle numbers and the map function:

// use a stream map and the multiplicative solution for triangle numbers
val trianglesM = Stream.from(1).map(n => n * (n + 1) / 2)
       
println("trianglesM take(5)")
trianglesM.take(5).foreach(println)

Using "inits" - inits are a concept that can be found in languages such as Haskell:

// using inits (not efficient)
// inits -> inits(Stream.from(1)) is Stream(Stream(), Stream(1), Stream(1, 2), Stream(1, 2, 3), ...)
// and tails -> tails(Stream(1)) = Stream(Stream(1,2,3,...), Stream(2,3,4,...), Stream(3,4,5,...), ...)
def inits[T](xs: Stream[T]) = Stream.from(0).map(xs.take(_))
      
val trianglesInits = inits(Stream.from(1)).tail.map(_.sum)

println("trianglesInits take(5)")
trianglesInits.take(5).foreach(println)

Using Stream.cons and a helper function zipWith that can zip tuples:

// using zipWith
def zipWith[T1,T2,T3](s1: Stream[T1], s2: Stream[T2])(fn: (T1,T2) => T3) = 
  s1.zip(s2).map(Function.tupled(fn))
       
lazy val trianglesZ: Stream[Int] = Stream.cons(1, zipWith(trianglesZ, 
  Stream.from(2))(_ + _))
       
println("trianglesZ take(5)")
trianglesZ.take(5).foreach(println)

So, whilst problem 12 is not too hard, the production of triangle numbers as lazy lists is quite interesting, being that there are several approaches that can be taken!


The whole program solution to problem 12 (and the alternative triangle number streams)

package projecteuler

object Problem12 {

 def main(args : Array[String]) {
 
  println("result = " + problem12(500))
 }
 
 def problem12(target : Int) {
 
  // using Stream.iterate to create a lazy stream of triangle numbers
  val trianglesI = Stream.iterate((1L,0L)){ 
   case (n, sum) => (n + 1L, sum + n) }.map(_._2)
  
  // test it
  //println("trianglesI take(5)")
  //trianglesI.take(5).foreach(println)
  
  // count the divisors (not massively efficient, but sufficient)
  def numDivisors(n : Long) = {
   
   var count = 0
   
   for (i <- 1L to Math.sqrt(n).toInt) {
    if (n % i == 0) {
     count = count + 2
    } 
   }
   count
  }
  
  trianglesI.find(p => numDivisors(p) > target)
  }
 
  def otherTriangleStreams {
   
    // use a stream map and the multiplicative solution for triangle numbers
  val trianglesM = Stream.from(1).map(n => n * (n + 1) / 2)
  
  println("trianglesM take(5)")
  trianglesM.take(5).foreach(println)
  
  // using inits (not efficient)
  // inits -> inits(Stream.from(1)) is Stream(Stream(), Stream(1), Stream(1, 2), Stream(1, 2, 3), ...)
  // tails -> tails(Stream(1)) = Stream(Stream(1,2,3,...), Stream(2,3,4,...), Stream(3,4,5,...), ...)
  def inits[T](xs: Stream[T]) = Stream.from(0).map(xs.take(_))
  
  val trianglesInits = inits(Stream.from(1)).tail.map(_.sum)
  
  println("trianglesInits take(5)")
  trianglesInits.take(5).foreach(println)
  
  // using zipWith
  def zipWith[T1,T2,T3](s1: Stream[T1], s2: Stream[T2])(fn: (T1,T2) => T3) = s1.zip(s2).map(Function.tupled(fn))
  
  lazy val trianglesZ: Stream[Int] = Stream.cons(1, zipWith(trianglesZ, Stream.from(2))(_ + _))
  
  println("trianglesZ take(5)")
  trianglesZ.take(5).foreach(println)
  }
}

.

Scala & GUIs, a simple maze generator and solver applet

In this blog we will touch on using Scala for a simple GUI, in the form of a simple 2D Maze Applet.

An example of this applet can be viewed running from here http://www.chillipower.com/examples/maze/maze1.html to give an illustration of what it does. This uses a maze space of 100x100 cells on a regular grid.

The applet illustrates 2 aspects of GUI programming in Scala, the first is how to interact with basic javax.swing APIs directly and the second is how to go one step further and achieve the same effect using the scala.swing wrapper API instead.

The function of the Applet can be broken down into 3 simple steps:

Step 1: Produce a random maze. This uses a modified version of Prim's algorithm, running backwards from the exit until all of the available space has been covered. This will produce a simple path from the source to the exit, which is the path we seek when we try to solve the maze by starting at the start. The standard Prim's algorithm is used to produce a minimum spanning tree from a directed acyclic graph by recursively adding safe edges to the current minimum spanning tree recursively, starting at a source node.

Step 2: Use a regular (recursive) DFS algorithm to search the maze, stopping only when the exit is reached (or all paths are explored fully if there were no reachable exit).

Step 3: Remove all backtrack paths and show the single simple path from start to exit as the solution to the maze.

During maze exploration, the parts of the maze explored are marked with coloured breadcrumbs, red indicates a forward search path and blue a backtracking path (which happens when a path reaches a dead-end).

In step 2, in order to stop immediately when the exit is found (rather than conclude all other possible search branches) the recursive maze solving function throws an exception to escape out of the call stack immediately.

The code given is compatible with the very latest Scala 2.8.x trunk development builds, and with 2.7.6 the latest stable release (some 2.7.6 only versions of functions such as shuffle are commented out in preference to the newer and better 2.8 versions). Note that there are currently some issues with Arrays in 2.8.x causing run time errors with trying to create a multidimensional array. The solution that still works with current 2.8 builds is to use the Array.tabulate function.

i.e. the following works in 2.7.6 but not currently in 2.8:

var cells : Array[Array[Cell]] = new Array[Array[Cell]](WIDTH, HEIGHT)

and there are similar problems with the new Array.ofDims function too. These issues should be resolved in 2.8 final release but recently arrays in scala have been undergoing some re-factoring and so stability in this area has not been too strong.

One interesting thing to note is the use of the new Scala 2.8+ Stream.iterate function to avoid undesirable vars instead of vals, here is an example of that extracted from the code.

A typical iterative piece of code, the while loops is used to iterate over some code block whilst a particular condition is met for a given variable. For this to work the variable n needs to be updated in the loop, hence it can't be a val and has to be a var instead. This is somewhat paradigmatic of iterative imperative programming, but doesn't sit well with the strive for a more functional style.

var n = cells(exit.x)(exit.y)

while (n != null) {

 n.trail = Forward
 n = n.pi
 update
}

What we can do here is make use of the Stream.iterate function to avoid the unsightly var n, as follows:

Stream.iterate(cells(exit.x)(exit.y))(_.pi).takeWhile(_ != null).foreach{
 n => {
   n.trail = Forward
   update
 }
}

Given that this is new in Scala 2.8 and 2.8 isn't released yet, you can augment existing 2.7.6 code with a helper function to aid the transition and improve 2.7 based code in readiness for 2.8. Here is an example of a util class that defines iterate so the same idea can be used in 2.7 based code:

def iterate[T](x:T)(f : T => T) : Stream[T] =
   Stream.cons(x, iterate(f(x))(f))

Another interesting thing to note in the code is the use of a permutation on a list (to create random directions when generating or exploring the maze), here is the code:

def shuffle[T](xs: List[T], r: scala.util.Random) = {
   xs.toStream.zip(Stream.const(r.nextDouble _).map(_())).toList.sort(_._2 < _._2).map(_._1)
}

The code maps the elements with a stream of random real numbers and then permutes by sorting the list, extracting the sorted items to create the random permutation (neat huh!)

The above code is 2.7.x & 2.8+ compatible, but perhaps even better is the following 2.8+ code that makes use of the new Stream.continually function:

def shuffle[T](xs: List[T])(implicit r: scala.util.Random) = {
 xs.zip(Stream.continually(r.nextDouble)).sortWith(_._2 < _._2).map(_._1)
}

In terms of the GUI aspects, the application is an applet, and the example code shows 2 ways of achieving this in Scala. The first, using the swing API directly is as follows:

class MazeApplet2 extends JApplet {

 override def init() {
   ...
 }

 override def start() {
 }
}

Which is familiar to any Java programmer, but the more interesting approach is using the scala.swing API instead, whereby we have:

class MazeApplet extends Applet {

 object ui extends UI with Reactor {

   def init() = {
     ...
   }

   override def start() = {
   }
 }
}

Where the abstract ui attribute (of type UI) is implemented using the Reactor mixin trait (http://www.scala-lang.org/docu/files/api/scala/swing/Reactor.html), to provide the framework for event handling.

One thing that's quite clear is the obviously similarity between the function to generate and the function to solve the maze. Using the DSL-like features of Scala it should be possible to extract the common control structure / algorithm and create a new utility function to provide built-in like support for this, passing in a body function to provide the difference implementation of maze generate vs. solve.


Full code example:

/**
* Scala 2.8+ Maze Applet v0.1 20-09-2009 Louis Botterill
*/
package maze

import scala.swing.Applet
import scala.swing.Panel
import scala.swing.Reactor

import javax.swing._;
import java.awt.Graphics;
import java.awt.Color;


object Direction extends Enumeration {
 type Direction = Value
   val North, South, East, West = Value
}

object Breadcrumb extends Enumeration {
 type Breadcrumb = Value
   val Forward, Backward, Clear = Value
}

import Direction._
import Breadcrumb._

class MazeModel {
 val HEIGHT = 100
 val WIDTH = 100

 // instantiate and initialise the 2d array - there is a direct 2d version but not working currently in scala 2.8.x
 var cells = Array.tabulate(WIDTH)(i => Array.tabulate(HEIGHT)(j => Cell(i, j)))

 // set everything as not visited and with no trail
 def clearVisited() = {

   cells.foreach(_.foreach(c => {
         c.visited = false;
         c.trail = Clear
     }))
 }

 // generate maze
 def generateMaze(update :  => Unit) {

   val exit = new Point(WIDTH - 1, HEIGHT - 1)
   val start = new Point(0, 0)

   // 1. Start at a particular cell, call it the "exit"
   // 2. Mark the current cell as visited, and get a list of all its neighbors.
   //      For each neighbor, starting with a randomly selected neighbor:
   //   1. If that neighbor hasn't been visited,
   //        remove the wall between this cell and that neighbor,
   //        and then recurse with that neighbor as the current cell.

   // cell 0,0 is the start, open the north wall to highlight this
   var s = cells(0)(0)
   s.clear(North);

   // cell width-1,height-1 is the exit, open the south wall to highlight this
   val c = cells(exit.x)(exit.y)
   c.clear(South);

   // recursively process the next cell
   def doNextCell(c : Cell) {

     c.visited = true
     c.trail = Forward

     var dirs = c.getRndDirections()

     while (!(dirs isEmpty)) {
       val dir = dirs.head
       val x = getCell(c, dir)

       x match {
         case Some(n) =>
          
           if (n.visited != true) {
             n.visited = true
             c.clear(dir)
             n.clear(getInv(dir))
             n.trail = Forward
             update
             doNextCell(n)
             n.trail = Clear
             update
           }

         case None =>
       }

       dirs = dirs.tail

       //Thread.sleep(1)
     }
   }

   doNextCell(c)
 }

 // find the maze solution using dfs from the start node until the end
 // node is located
 def solveMaze(update :  => Unit) {
  
   val start = new Point(0, 0)
   val exit = new Point(WIDTH - 1, HEIGHT - 1)

   val s = cells(0)(0)
   s.clear(North);

   def doNextCell(c : Cell) {

     c.visited = true
     c.trail = Forward

     var dirs = c.getDirections()
    
     while (!(dirs isEmpty)) {
       val dir = dirs.head
       val x = getCell(c, dir)

       x match {
         case Some(n) =>

           if (n.visited != true) {
             n.visited = true
             n.pi = c  // set predecessor node
             n.trail = Forward
             update
             if (n.i == exit.x && n.j == exit.y) throw new Exception("Done")
             doNextCell(n)
             n.trail = Backward
             update
           }

         case _ =>
       }

       // take the top item off and use the rest of the list
       dirs = dirs.tail
      
       Thread.sleep(1) // add a little delay so we can watch the dfs explore and find the solution
     }
   }

   doNextCell(s)
 }

 // from the exit recurse over the trail of predecessors,
 // marking with a forward trail
 def showSolution(update :  => Unit) {

   val exit = new Point(WIDTH - 1, HEIGHT - 1)

   // 2.8 avoid var using Stream
   // Stream.iterate(cells(exit.x)(exit.y))(_.pi).takeWhile(_ != null)
   Stream.iterate(cells(exit.x)(exit.y))(_.pi).takeWhile(_ != null).foreach{
     n => {
       n.trail = Forward
       update
     }
   }

   // the following works fine but replaced with the above to avoid unnecessary var
   /*
   var n = cells(exit.x)(exit.y)

   while (n != null) {

     n.trail = Forward
     n = n.pi
     update
   }
   */
 }

 // get the cell if possible based on current cell and the given direction
 def getCell(c : Cell, dir : Direction) : Option[Cell] = dir match {

   case North  => if (c.j > 0) Some(cells(c.i)(c.j-1)) else None
   case South  => if (c.j < east   =""> if (c.i < west   =""> if (c.i > 0) Some(cells(c.i-1)(c.j)) else None
 }

 // find the inverse direction for a given direction
 def getInv(dir : Direction) = dir match {

   case North => Direction.South
   case South => Direction.North
   case East => Direction.West
   case West => Direction.East
 }
}

// a scala.swing.Panel, override paint(Graphics2D) to paint each of the cells
class MazePanel(m : MazeModel) extends Panel {

 override def paint(g : java.awt.Graphics2D) {

   m.cells.foreach(_.foreach(_.draw(g)))
 }
}

// a javax.swing.JPanel, override paint(Graphics) to paint each of the cells
class MazePanel2(m : MazeModel) extends JPanel {

 override def paint(g : Graphics) {

   m.cells.foreach(_.foreach(_.draw(g)))
 }
}

// a scala.swing.Applet based applet using scala swing wrappers
class MazeApplet extends Applet {
 val m = new MazeModel()
 lazy val mp = new MazePanel(m)

 object ui extends UI with Reactor {

   def init() = {
     contents = mp
   }

   override def start() = {
     def update = {
       this.repaint()
     }

     m.generateMaze(update)

     Thread.sleep(2000)

     m.clearVisited

     try {
       m.solveMaze(update);
     }
     catch {
       case e : Exception =>
     }

     Thread.sleep(2000)

     m.clearVisited

     m.showSolution(update)

     mp.repaint()
     this.repaint()
   }
 }
}

// standard javax.swing.JApplet of the maze
class MazeApplet2 extends JApplet {

 val m = new MazeModel()
 lazy val mp = new MazePanel2(m)

 def MazeApplet2 = {
 }

 override def init() {

   this.add(mp)
 }

 override def start() {
   def update = {
     this.repaint()
   }
  
   m.generateMaze(update)

   Thread.sleep(2000)

   m.clearVisited

   try {
     m.solveMaze(update);
   }
   catch {
     case e : Exception =>
   }

   Thread.sleep(2000)

   m.clearVisited

   m.showSolution(update)

   mp.repaint()
   this.invalidate()
   this.repaint()
 }

 override def stop() {
 }

 override def destroy() {
 }
}

// standard Java app of the maze using JFrame
object Maze {

 def main(args: Array[String]) {

   val mazeApplet = new MazeApplet()
   val frame = new JFrame()
   frame.setBounds(50, 50, 750, 750)
   frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

   frame.add(mazeApplet)

   frame.setVisible(true)
   mazeApplet.init
   mazeApplet.start
 }
}

// represent a Cell of the maze
case class Cell(i: Int, j : Int) {

 val size = 7; // each cell is 7px by 7px
 var north : Boolean = true
 var south : Boolean = true
 var east : Boolean = true
 var west : Boolean = true
 var visited : Boolean = false
 var pi : Cell = null  // predecessor cell
 var trail : Breadcrumb = Clear;

 def draw(g : Graphics) {

   val x = i * size
   val y = j * size

   trail match {
     case Forward => {
       g.setColor(Color.RED);
       g.fillRect(x + 2, y + 2, size - 4, size - 4)
     }
     case Backward => {
       g.setColor(Color.BLUE);
       g.fillRect(x + 2, y + 2, size - 4, size - 4)
     }
     case _ =>
   }

   g.setColor(Color.BLACK);
   if (north) {
     g.drawLine(x, y, x + size, y);
   }
   if (south) {
     g.drawLine(x, y + size, x + size, y + size);
   }
   if (east) {
     g.drawLine(x + size, y, x + size, y + size);
   }
   if (west) {
     g.drawLine(x, y, x, y + size);
   }
 }

 def clear(dir : Direction) = dir match {

   case North => north = false
   case South => south = false
   case East => east = false
   case West => west = false
 }

 def getDirections() : scala.List[Direction] = {

   var d = scala.List[Direction]()

   if (!north) d = North :: d
   if (!south) d = South :: d
   if (!east) d = East :: d
   if (!west) d = West :: d

   d
 }

 def getRndDirections() : scala.List[Direction] = {

   val directions = North :: South :: East :: West :: Nil
   implicit val r = Rand.rand
   Utils.shuffle(directions) //, Rand.rand)
 }
}

// represent a 2d point
case class Point(x : Int, y : Int)

// init a random generator singleton
object Rand {
 val rand : scala.util.Random = new scala.util.Random();
}

object Utils {

 // ref: http://okmij.org/ftp/Haskell/perfect-shuffle.txt
 // scala 2.7+ here's an O(n log n) solution:
 /*
 def shuffle[T](xs: List[T], r: scala.util.Random) = {
   xs.toStream.zip(Stream.const(r.nextDouble _).map(_())).toList.sort(_._2 < nil =""> scala.List(Nil)
   case _ => xs.flatMap(x => permute(xs.filter(_ != x)).map(x :: _))
 }

 // make a stream of x, f(x), f(f(x)), etc.
 // in Haskell this is called "iterate".  it ought to be in the standard library
 // as Stream.iterate.  "unfold" should be more general, but nonetheless I'm
 // going to call this unfold for the moment...
 def unfold[T](x:T)(f:T=>T):Stream[T] =
   Stream.cons(x,unfold(f(x))(f))

 def iterate[T](x:T)(f:T=>T):Stream[T] =
   Stream.cons(x,iterate(f(x))(f))
}

.

Scala, trees, pattern matching and tree recursion

Hi! Long time no see...

Well after some outage due to Holiday (road trip around Europe and down to the Swiss Alps!), work commitments and some personal things to deal with, I'm back again.

I thought I'd start with some stuff on Tree structures, whilst continuing on with Scala too. The following code illustrates some good examples of case classes and pattern matching, along with extensive use of Some, None and Option (Scala's improved way of dealing with optional types, rather than relying on null everywhere).

The following code defines a simple recursive binary tree definition as a case class, using option to define the left and right children.

case class Tree[+T](value: T, left: Option[Tree[T]], right: Option[Tree[T]])

The above definition defines a tree recursively, exactly as a tree is defined as a data structure in computer science. Each tree node has a value of type T and an Optional left and right child node (bin tree). The +T makes the Tree type covarient about T, which is a generally useful property of a Tree.

A few helper functions are used that make life a little easier when working with Option types, by extracting the value or providing a safe default when no value exists. These help keep the code a little tidy and manageable.

 /**
  * Helper function: For o return f: A => Int if Some or 0 if None
  *   also could try opt map f getOrElse 0
  */
 def zeroIfNone[A](o: Option[A], f: A => Int): Int = o match {
   case None => 0
   case Some(x) => f(x)
 }

 /**
  * Helper function: Return value of function provided if Some, or 0 otherwise
  */
 def zeroIfNoneVal[A](o: Option[A], n: => Int) = zeroIfNone[A](o, _ => n)

 /**
  * Helper function: Default to provided value if option is None
  */
 def defaultIfNone[A](o: Option[A], f: A => Int, d : Int): Int = o match {
   case None => d
   case Some(x) => f(x)
 }

The example code demonstrates preorder, inorder and postorder recursive tree traversal (which are all simple permutations of a basic depth first search), applying the provided unit function to each node as it is visited.

Recall that the preorder, inorder and postorder functions are defined as follows:

• PreOrder - visit parent node, left and then right child node
• InOrder - visit left, parent and then right nodes
• PostOrder - visit left, right and then parent node

Using recursion and the call stack, depth first search based tree traversal is very simple and concise. The basic DFS inorder traversal looks like:

 /**
  * Perform an inorder tree traversal using the provided Tree[A] => Unit function
  */
 def inOrder[A](t: Option[Tree[A]], f: Tree[A] => Unit) : Unit = t match {

   case None =>
   case Some(x) =>
     if (x.left != None) inOrder(x.left, f)
     f(x)
     if (x.right != None) inOrder(x.right, f)
 }

The breadth first search algorithm is perhaps more interesting. This uses a List as a basic FIFO queue to provide the breadth first search tree traversal:

 /**
  * Breadth first search on a tree, a list is used as a basic fifo queue to
  *   give the bfs traversal
  */
 def breadthFirstSearch[A](t: Tree[A], f: Tree[A] => Unit): Unit = {
   def bfs(ts: List[Tree[A]]): Unit = ts match {
     case Nil => // ignore
     case _ =>
       val children = for{tree <- ts         
         Some(child) <- List(tree.left, tree.right)}         
         yield child      
     ts map f     
     bfs(children)   
   }     
   bfs(List(t))  
 } 

The example also shows a treeFold function. Whether this is a useful function as-is is perhaps debatable, but it makes for an interesting example. The code traverses the tree in a DFS inorder traversal and applies the mapping function f : A -> B and then it applies the join function j : B, B -> B to combine the results of the tree map. In this way the function is similar to say flatMap where a list is mapped and then flattened into a single list, or perhaps more closely to foldLeft/foldRight where items in a list a joined into a single resulting value.

 /**
  * Fold up a tree into a single value, using provided map and join functions
  */
 def treeFold[A, B](t: Option[Tree[A]],
                    f: Option[Tree[A]] => Option[B],
                    j: (Option[B], Option[B]) => Option[B]) : Option[B] = t match {

   case None => None
   case Some(x) => j(j(f(t), treeFold(x.left, f, j)), treeFold(x.right, f, j))
 }

Some utility functions are also defined, to return the size and depth of the tree for illustration of how this can be achieved.

In summary Scala can quite elegantly represent Tree data structures, using case classes and operate over them using pattern matching and higher order functions to provide powerful and concise support for trees and the operations that can be performed on them.

Some additional things that could be done here would be to provide an example of a binary search and perhaps insertion, update and delete too. A job for another followup blog perhaps...


The full example code (is complete and self contained) is as follows:

package trees

// Define a recursive Bin Tree structure
case class Tree[+T](value: T, left: Option[Tree[T]], right: Option[Tree[T]])

object TreeObj {

 /**
  * Helper function: For o return f: A => Int if Some or 0 if None
  *   also could try opt map f getOrElse 0
  */
 def zeroIfNone[A](o: Option[A], f: A => Int): Int = o match {
   case None => 0
   case Some(x) => f(x)
 }

 /**
  * Helper function: Return value of function provided if Some, or 0 otherwise
  */
 def zeroIfNoneVal[A](o: Option[A], n: => Int) = zeroIfNone[A](o, _ => n)

 /**
  * Helper function: Default to provided value if option is None
  */
 def defaultIfNone[A](o: Option[A], f: A => Int, d : Int): Int = o match {
   case None => d
   case Some(x) => f(x)
 }

 /**
  * Return the size of the tree
  */
 def size[A](t : Option[Tree[A]]) : Int = t match {

   case None => 0
   case Some(x) =>
     zeroIfNoneVal(x.left, size(x.left)) + zeroIfNoneVal(x.right, size(x.right)) + 1
     //zeroIfNone(x.left, (_:Tree[Any]) => (size(x.left))) +
     //zeroIfNone(x.right, (_:Tree[Any]) => (size(x.right))) + 1
 }

 /**
  * Alternative size using nested function
  */
 def size2[A](t : Option[Tree[A]]) : Int = {

   def sizeB(b : Option[Tree[A]]) : Int = b match {
     case None => 0
     case Some(x) => size(b);
   }

   t match {
     case None => 0
     case Some(x) =>
       sizeB(x.left) + sizeB(x.right) + 1
   }
 }

 /**
  * Return the max depth of the tree
  */
 def depth[A](t : Option[Tree[A]]) : Int = t match {

   case None => 0
   case Some(x) =>
     Math.max(zeroIfNoneVal(x.left, depth(x.left)), zeroIfNoneVal(x.right, depth(x.right))) + 1
 }

 /**
  * Alternative deptch, return the max depth of the tree using nested function
  */
 def depth2[A](t : Option[Tree[A]]) : Int = {

   def depthB(b : Option[Tree[A]]) : Int = b match {
     case None => 0
     case Some(x) => depth(b);
   }

   t match {

     case None => 0
     case Some(x) =>
       Math.max(depthB(x.left), depthB(x.right)) + 1
   }
 }

 /**
  * Breadth first search on a tree, a list is used as a basic fifo queue to
  *   give the bfs traversal
  */
 def breadthFirstSearch[A](t: Tree[A], f: Tree[A] => Unit): Unit = {
   def bfs(ts: List[Tree[A]]): Unit = ts match {
     case Nil => // ignore
     case _ =>
       val children = for{tree <- ts           Some(child) <- List(tree.left, tree.right)}           yield child       ts map f       bfs(children)     }      bfs(List(t))   }    /**    * Sum up the elements of a numeric tree    */   def sumTree[A <: Int](t: Option[Tree[A]]) : Int = t match {      case None => 0
   case Some(x) =>
     sumTree(x.left) + sumTree(x.right) + x.value
 }

 /**
  * Fold up a tree into a single value, using provided map and join functions
  */
 def treeFold[A, B](t: Option[Tree[A]],
                    f: Option[Tree[A]] => Option[B],
                    j: (Option[B], Option[B]) => Option[B]) : Option[B] = t match {

   case None => None
   case Some(x) => j(j(f(t), treeFold(x.left, f, j)), treeFold(x.right, f, j))
 }

 /**
  * Perform an inorder tree traversal using the provided Tree[A] => Unit function
  */
 def inOrder[A](t: Option[Tree[A]], f: Tree[A] => Unit) : Unit = t match {

   case None =>
   case Some(x) =>
     if (x.left != None) inOrder(x.left, f)
     f(x)
     if (x.right != None) inOrder(x.right, f)
 }

 /**
  * Perform a preorder tree traversal using the provided Tree[A] => Unit functio
  */
 def preOrder[A](t: Option[Tree[A]], f: Tree[A] => Unit) : Unit = t match {

   case None =>
   case Some(x) =>
     f(x)
     if (x.left != None) inOrder(x.left, f)
     if (x.right != None) inOrder(x.right, f)
 }

 /**
  * Perform a postorder tree traversal using the provided Tree[A] => Unit functio
  */
 def postOrder[A](t: Option[Tree[A]], f: Tree[A] => Unit) : Unit = t match {

   case None =>
   case Some(x) =>
     if (x.left != None) inOrder(x.left, f)
     if (x.right != None) inOrder(x.right, f)
     f(x)
 }

 /**
  * build tree and run tree functions on it
  */
 def main(args : Array[String]) {

   /* Test Tree structure

               1
              / \
             2   3
            / \ / \
           4  x 5  6
         
   */

   // build a tree
   val myTree = Tree(1,
     Some(Tree(2,
       Some(Tree(4, None, None)),
         None
       )
     ),
     Some(Tree(3,
       Some(Tree(5, None, None)),
         Some(Tree(6, None, None))
       )
     )
   )

   printBfsTree(myTree)

   println("Size = " + size(Some(myTree)))

   println("Depth = " + depth(Some(myTree)))

   println("Sum = " + sumTree(Some(myTree)))
  
   var sum = treeFold[Int, Int](
               Some(myTree),
               (t: Option[Tree[Int]]) => t match { case None => Some(0); case Some(x) => Some(x.value) },
               (x: Option[Int], y: Option[Int]) =>
                 Some(zeroIfNone[Int](x, (x:Int) => x) + zeroIfNone[Int](y, y => y))
             )

   var mult = treeFold[Int, Int](
               Some(myTree),
               (t: Option[Tree[Int]]) => t match { case None => Some(0); case Some(x) => Some(x.value) },
               (x: Option[Int], y: Option[Int]) =>
                 Some(defaultIfNone[Int](x, (x:Int) => x, 1) * defaultIfNone[Int](y, y => y, 1))
              )

   println("Sum Result = " + sum)
   println("Mult Result = " + mult)

   println("InOrder = ")
   inOrder(Some(myTree), (t: Tree[Any]) => println(t.value))

   println("PreOrder = ")
   preOrder(Some(myTree), (t: Tree[Any]) => println(t.value))

   println("PostOrder = ")
   postOrder(Some(myTree), (t: Tree[Any]) => println(t.value))
 }

 /**
  * Print a tree using BFS, passing in print unit function
  */
 def printBfsTree[A](tree: Tree[A]) {

   breadthFirstSearch(tree, (t: Tree[A]) => println(t.value))
 }
}

.

Notes on Adobe LiveCycle, Flash, Flex and Air

Having recently attended Adobe LiveCycle training at Adobe Uxbridge, here are a few notes and links from it.

Adobe LiveCycle is an integrated Java based SOA and document management server framework. LiveCycle can be hosted on a JEE application server, including JBoss, WebSphere and WebLogic. LiveCycle requires a Database, mySql, Oracle and MS SQL are supported.

LiveCycle is offers best performance on Microsoft/MS SQLServer platforms - currently.

LiveCycle is compatible with Windows, Solaris, AIX and Linux

LiveCycle is designed to integrate with RIA technologies, such as Flash, Flex and Air.


Key LiveCycle features include:

• Forms builder - a PDF based form generation engine for PDF/HTML and Flash presentation
• Form Guides - based on PDF but with wizard style Flash presentation
• Reader/Reader extensions - Acrobat/Reader document management including digital signatures, revocation, permissions etc
• Process Management
• Data Services - Web Services, support for RESTful webservices in the next version
• Output - print/production services

• Flash is the original rich embedded content for multimedia, video, graphics and sound - flash runs as a plugin in the browser (although stand alone players are available too).
• Flex builds on Flash and adds a rich component model.
• Air is Flex technology that can be run in the browser or as desktop applications transparently.

LiveCycle and Flex based technologies can use ActionScript, a form of ECMA (JavaScript), Flex itself uses an XML format called mxml to define applications and component layout.


Key Tools:

• FlexBuilder - IDE for Flex/Air development
• LiveCycle Workbench - for LiveCycle development including forms and process management

Main Development WebSite: http://www.adobe.com/devnet/
Main Download home: http://www.adobe.com/downloads/
Flex Downloads: http://www.adobe.com/products/flex/flexdownloads/

Flex Development center: http://www.adobe.com/devnet/flex/?view=home
TourDeFlex: http://www.adobe.com/devnet/flex/tourdeflex/
TourDeLiveLycle: http://www.adobe.com/devnet/livecycle/tourdelivecycle/
LiveCycle Cafe: http://www.adobe.com/devnet/livecycle/cafe/

LiveDocs (online documentation): http://livedocs.adobe.com/
ActionScript 3: http://livedocs.adobe.com/flash/9.0/ActionScriptLangRefV3/
Flex 3 LiveDocs: http://livedocs.adobe.com/flex/3/

Adobe Partners: https://www.adobe.com/cfusion/partnerportal/index.cfm

FlashDevelop: Getting started http://nuigroup.com/forums/viewthread/1689/


.

Scala, the Google App Engine and an iPhone client...

In this Blog I wanted to explore Scala on the Google App Engine. The Google App Engine has supported Java (as well as Python) for a little while now. There have been a few blogs about running Scala on the App engine and I wanted to further demonstrate this by taking a simple Java Servlet and converting it to a Scala based web application suitable for the App Engine.

The Google App Engine home is here http://code.google.com/appengine/ and contains excellent documentation on how to get stated. I don't want to repeat the documentation, so I'll just point out the essentials relevant to this blog.

The Getting Started guide can be found here: http://code.google.com/appengine/docs/java/gettingstarted/ for Java, and a Python equivalent is available too.

This example is based on the previous blog, the Sieve of Eratosthenes as a simple prime number generator. The request accepts one parameter n whose integer value is the upper limit to generate all the primes until (from 2). The response output is JSON encoded to create a simple web service.


Starting with the very basics, the recommended project directory structure is of the form:

|-src
|---META-INF
|---primes
|-war
|---WEB-INF
|-----classes
|-------META-INF
|-------primes
|-----lib

For any Web App for the Google App Engine, one additional GAE specific file is required alongside the standard web.xml deployment descriptor. This file is called appengine-web.xml and contains the name of the Application, for example:

<appengine-web-app xmlns="http://appengine.google.com/ns/1.0">
  <application>primes-chillipower-com</application>
  <version>1</version>
</appengine-web-app>

In this simple GAE deployment descriptor the main thing is that the name of the application is specified, in this example the application was called 'primes-chillipower-com'.

Applications must be created on the App Engine, this can be done here: http://appengine.google.com/

Note that there are some limitations currently, you are allowed up to a maximum of 10 applications and applications can not be deleted once created!


The simple Java version:

In the simple Java version we can place a simple Servlet in the src directory and build using ant.


Example Java servlet:

package primes;

import java.io.IOException;
import javax.servlet.http.*;

public class PrimesServletJ extends HttpServlet {
public void doGet(HttpServletRequest req, HttpServletResponse resp)
       throws IOException {
    resp.setContentType("text/plain");

int n = 100;

String nStr = req.getParameter("n");

try {

   n = Integer.parseInt(nStr);
}
catch (Exception e) {}

int[] primes = primes(n);

resp.getWriter().println("{ \"n\" : \"" + n + "\",");
resp.getWriter().println("  \"primes\" : [ ");

for (int i = 0; i < primes.length; i++) {
   String sep = (i < primes.length - 1) ? ", " : "";
       resp.getWriter().println(" { \"" + i + "\" : \"" + primes[i] + "\" }" + sep);
   }

resp.getWriter().println(" ] }");
}

public static int[] primes(int n) {

   // initially assume all integers are prime
   boolean[] isPrime = new boolean[n + 1];

   for (int i = 2; i <= n; i++) {
       isPrime[i] = true;
   }

   // mark non-primes <= N using Sieve of Eratosthenes
   for (int i = 2; i*i <= n; i++) {

       // if i is prime, then mark multiples of i as nonprime
       // suffices to consider mutiples i, i+1, ..., N/i
       if (isPrime[i]) {
           for (int j = i; i * j <= n; j++) {
               isPrime[i * j] = false;
           }
       }
   }

   // count primes
   int primeCount = 0;
   for (int i = 2; i <= n; i++) {
       if (isPrime[i]) primeCount++;
   }

   System.out.println("The number of primes <= " + n + " is " + primeCount);

   int[] primes = new int[primeCount];
   int idx = 0;
   for (int i = 0; i <= n; i++) {
       if (isPrime[i] == true) {

           primes[idx] = i;
           idx++;
       }
   }

   return primes;
}

public static void main(String[] args) {

   int n = 100;

   if (args.length > 0 && args[0] != null) {
       n = Integer.parseInt(args[0]);
   }

   int[] primes = primes(n);

   for (int p : primes) {
       System.out.println("Prime: " + p);
   }
}
}

The ant build script goes in the root of the project, to start with I based mine on the example on the Google App Engine documentation here http://code.google.com/appengine/docs/java/tools/ant.html#Uploading_and_Other_AppCfg_Tasks

Using the standard ant script the project can be compiled and even run locally using the SDK.

ant compile

ant runserver


If you start the dev app server locally, it will be accessibly using a URL of the form:

http://localhost:8080/yourappcontextpath


Where the port 8080 is the default and can be changed in the script.

The App Engine SDK comes with appcfg.sh script in the bin directory, which can be used to perform operations such as uploading your app to the App Engine.


../../../../tools/appengine-java-sdk-1.2.1/bin/appcfg.sh update war


The Scala version:

The main tasks in converting this conventional Java Servlet based web app to a Scala based one is to:

• Rewrite the Java Servlet in Scala.
• Reconfigure the ant build.xml to modify the classpath to include the Scala libraries and to run the Scala scalac compiler to create the Java .class files from the .scala source files.

Since the Servlet API is a Java based API, there will of course be some reference to Java based classes in the Scala Servlet.


Example Scala based Servlet:

package primes

import javax.servlet.http._


class PrimesServlet extends HttpServlet {
override def doGet(request: HttpServletRequest, response: HttpServletResponse) = {

  var n = 100

  try {
    val nStr = request.getParameter("n"); 
    n = Integer.parseInt(nStr);
  } catch {
    case e : Exception => {
      println("Exception e " + e.getMessage())
    }
  }

  val ps = primes take n
  val out = response.getWriter()

  out.println("{ \"n\" : \"" + n + "\", \"primes\" : [")

  var i = 0
  for (p <- ps) {
    val sep = if (i < ps.length - 1) ", " else ""
    out.println(" { \"" + i + "\" : \"" + p + "\" }" + sep)
    i = i + 1
  }

  out.println(" ] } ")
}

def primes = {
 def sieve(is: Stream[Int]): Stream[Int] = {
   val h = is.head
   Stream.cons(h, sieve(is filter (_ % h > 0)))
 }

 sieve(Stream.from(2))
}
}

Example modified and build.xml file:

<project>
<property name="scala.home" location="/Users/chillipower_uk/dev/tools/scala/scala-2.7.5.final/" />
<property name="sdk.dir" location="/Users/chillipower_uk/dev/tools/appengine-java-sdk-1.2.1/" />

<import file="${sdk.dir}/config/user/ant-macros.xml" />

<path id="project.classpath">
<pathelement path="war/WEB-INF/classes" />
<fileset dir="war/WEB-INF/lib">
 <include name="**/*.jar" />
</fileset>
<fileset dir="${sdk.dir}/lib">
 <include name="shared/**/*.jar" />
</fileset>
</path>

<!-- Copy over Scala jars -->
<target name="init">
<property
 name="scala-library.jar"
 value="${scala.home}/lib/scala-library.jar"
  />
<path id="build.classpath">
 <pathelement location="${scala-library.jar}"   />

 <pathelement location="${build.dir}"   />
</path>
<taskdef resource="scala/tools/ant/antlib.xml">
 <classpath>
   <pathelement location="${scala.home}/lib/scala-compiler.jar"   />
   <pathelement location="${scala-library.jar}"   />
 </classpath>
</taskdef>
</target>

<!-- Copy Scala JARs -->
<target name="copyscala"
 description="Copies the Scala JARs to the WAR.">
<copy
   todir="war/WEB-INF/lib"
   flatten="true">
 <fileset dir="${scala.home}/lib">
   <include name="**/scala-library.jar" />
 </fileset>
</copy>
</target>

<!-- Copy App engine jars -->
<target name="copyjars"
 description="Copies the App Engine JARs to the WAR.">
<copy
   todir="war/WEB-INF/lib"
   flatten="true">
 <fileset dir="${sdk.dir}/lib/user">
   <include name="**/*.jar" />
 </fileset>
</copy>
</target>

<target name="compile" depends="copyscala, copyjars, init"
 description="Compiles Java source and copies other source files to the WAR.">
<mkdir dir="war/WEB-INF/classes" />
<copy todir="war/WEB-INF/classes">
 <fileset dir="src">
   <exclude name="**/*.scala" />
<exclude name="**/*.java" />
 </fileset>
</copy>
<scalac
   srcdir="src"
   destdir="war/WEB-INF/classes"
   classpathref="project.classpath"
    />

<!--
<copy todir="war/WEB-INF/classes">
  <fileset dir="src">
    <exclude name="**/*.scala" />
    <exclude name="**/*.java" />
  </fileset>
</copy> -->
<javac
   srcdir="src"
   destdir="war/WEB-INF/classes"
   classpathref="project.classpath"
   debug="on" />

</target>

<target name="datanucleusenhance" depends="compile"
 description="Performs JDO enhancement on compiled data classes.">
<enhance_war war="war" />
</target>

<target name="runserver" depends="datanucleusenhance"
 description="Starts the development server.">
<dev_appserver war="war" />
</target>

<target name="update" depends="datanucleusenhance"
 description="Uploads the application to App Engine.">
<appcfg action="update" war="war" />
</target>

<target name="update_indexes" depends="datanucleusenhance"
 description="Uploads just the datastore index configuration to App Engine.">
<appcfg action="update_indexes" war="war" />
</target>

<target name="rollback" depends="datanucleusenhance"
 description="Rolls back an interrupted application update.">
<appcfg action="rollback" war="war" />
</target>

<target name="request_logs"
 description="Downloads log data from App Engine for the application.">
<appcfg action="request_logs" war="war">
 <options>
   <arg value="--num_days=5"/>
 </options>
 <args>
   <arg value="logs.txt"/>
 </args>
</appcfg>
</target>

</project>

Example request and output:

Request: http://primes-chillipower-com.appspot.com/primes?n=50

{ "n" : "50", "primes" : [ { "0" : "2" }, { "1" : "3" }, { "2" : "5" }, { "3" : "7" }, { "4" : "11" }, { "5" : "13" }, { "6" : "17" }, { "7" : "19" }, { "8" : "23" }, { "9" : "29" }, { "10" : "31" }, { "11" : "37" }, { "12" : "41" }, { "13" : "43" }, { "14" : "47" }, { "15" : "53" }, { "16" : "59" }, { "17" : "61" }, { "18" : "67" }, { "19" : "71" }, { "20" : "73" }, { "21" : "79" }, { "22" : "83" }, { "23" : "89" }, { "24" : "97" }, { "25" : "101" }, { "26" : "103" }, { "27" : "107" }, { "28" : "109" }, { "29" : "113" }, { "30" : "127" }, { "31" : "131" }, { "32" : "137" }, { "33" : "139" }, { "34" : "149" }, { "35" : "151" }, { "36" : "157" }, { "37" : "163" }, { "38" : "167" }, { "39" : "173" }, { "40" : "179" }, { "41" : "181" }, { "42" : "191" }, { "43" : "193" }, { "44" : "197" }, { "45" : "199" }, { "46" : "211" }, { "47" : "223" }, { "48" : "227" }, { "49" : "229" } ] }

The iPhone client:

I'm currently developing using the iPhone 3.1 beta SDK. I'm not going to post all the source code the the simple client, but rather give some essential snippets relevant to the invocation of the simple JSON web service once deployed on the Google App Engine.

To Consume this JSON in an iPhone app, we can use the JSON Objective-C library, which is available on Google code here http://code.google.com/p/json-framework/wiki/FAQ

- (void)loadData {
[super viewDidLoad];

NSString *urlString = [NSString stringWithFormat:@"http://primes-chillipower-com.appspot.com/primes?n=1000"];
NSURL *url = [NSURL URLWithString:urlString];

NSDictionary *primesResponse = (NSDictionary *)[JsonClientHelper fetchJSONValueForURL:url];

if (primesResponse != nil) {

NSArray *primeEntries = [primesResponse objectForKey:@"primes"];

NSMutableArray *primesTemp = [[NSMutableArray alloc] init];
[primesTemp retain];

for (int i = 0; i < [primeEntries count]; i++) {

 NSDictionary *primeEntry = (NSDictionary*)[primeEntries objectAtIndex:i];

 NSString *key = [NSString stringWithFormat:@"%d", i];

 NSString *p = [primeEntry objectForKey:key];

 NSString *msg = [NSString stringWithFormat:@"Prime %d = %@", i, p];

 NSLog(msg);

 [primesTemp addObject:p];
}

primes = [primesTemp copy];

[primesTemp release];
}
}

The above code makes a request to the JSON web service on the App Engine and decodes the response, which once decoded using the JSON library is contained in Dictionaries (NSDictionary) and Arrays (NSArray).


Where JsonClientHelper contains a basic class helper method fetchJSONValueForURL to fetch and decode a JSON response from the supplied URL.

+ (id)fetchJSONValueForURL:(NSURL *)url
{
NSString *jsonString = [[NSString alloc] initWithContentsOfURL:url encoding:NSUTF8StringEncoding error:nil];

id jsonValue = [jsonString JSONValue];

[jsonString release];

return jsonValue;
}

I hope this Blog has helped give some insight into creating a Scala based Web Application for the Google App Engine, as well as the consumption of JSON in an iPhone Objective-C client.

(I appologise for the formatting of the code in this blog, finding it awkward to get the code into the blog without it being mangled in some way!).


Resources:

Handy JSON Lint tool: http://www.jsonlint.com/

Scala Servlet development: http://blogs.oracle.com/aseembajaj/2008/08/scala_servlet_development.html

Scala on the Google App Engine: http://froth-and-java.blogspot.com/2009/04/scala-on-google-appengine.html

The Google App Engine provides support for JPA and JDO based persistence - a comparison of the two can be found here: http://www.jpox.org/docs/persistence_technology.html Further details of the JDO specification can be found here: http://java.sun.com/jdo/index.jsp and the JDO specification here: http://java.sun.com/javaee/technologies/persistence.jsp

Support for the Google App Engine in Netbeans: http://kenai.com/projects/nbappengine/pages/Home


.

Scala, lazy evaluation and the Sieve of Eratosthenes

This blog posting is primarily concerned with looking at lazy evaluation in functional programing, what it means and how it can be put to use.

Lazy evaluation can be described as an expression that has a value, but that is not evaluated until it's actually needed. Conversely strict refers to the opposite property where all expressions are evaluated up front when declared.

Some functional languages are described as Pure Lazy (no, this is not a derogatory term!), to reflect the fact that all evaluation is performed on demand. Haskell is on such language. Scala has both aspects of strict evaluation and lazy evaluation, as such it couldn't be referred to as 'pure' in either sense.

By means of the simplest example I can think of to illustrate Lazy evaluation, consider the following interaction with the Scala CLI:

scala> lazy val a = b + 1; lazy val b = 1;
a: Int = <lazy>
b: Int = <lazy>

scala> a
res9: Int = 2

scala> b
res10: Int = 1

I think this illustrates lazy evaluation, without defining the 'vals' as lazy the statement lazy val a = b + 1; lazy val b = 1; as val a = b + 1; val b = 1; couldn't be evaluated because b would be undefined when evaluating a!

The examples are based on the Sieve of Eratosthenes. Eratosthenes was an ancient Greek Mathmetician from 276 BC – c. 195 BC. The Sieve of Eratosthenes is a ancient algorithm for finding prime numbers from 2 .. n. Stated simply, this algorithm can be expressed as:

• Create a list of all the numbers from 2 .. n.
• Starting at p = 2
• Strike out all multiples of p up until n from the list
• Let p now be the first (lowest) number that has not been struck-off the list
• Repeat the last two steps until p^2 > n
• All remaining numbers not struck from the list are prime

In Haskell this can be expressed very elegantly and succinctly, as follows:

primes = sieve [2..]
sieve (p : xs) = p : sieve [x | x <− xs, x `mod` p > 0]


Note that [2..] creates an infinite steam of all the integers from 2 to infinity. You might think this is impossible and would create an out of memory error on the machine it ran on, but this is perfectly valid in a pure lazy language because none of the numbers are actually generated until they are requested!

In Scala there's not really a way to represent this quite so succinctly, but it is possibly to create a Lazy stream of numbers using:

var is = Stream from 2

which is essentially equivalent to Haskell's:

[2..]

Syntax.


Another important thing to note and be aware of is that Scala's List class is not a lazy list. Therefore, trying to make the equivalent of the Haskell algorithm in Scala using a List is not going to work.

Scala's Stream class however is Lazy, and so it can form the basic of the equivalent algorithm in Scala. To be specific, Scala's Stream class is strict about head and lazy about tail - which is ok since head contains a finite set of 0|1 elements.


The following Scala code shows two ways to implement the Sieve using Scala Lazy streams.


Example 1:

package primes;

/* Haskell...

primes = sieve [2..]
sieve (p : xs) = p : sieve [x | x <− xs, x `mod` p > 0]
*/
object Primes1 {

def primes : Stream[Int] = {

 var is = Stream from 2

 def sieve(numbers: Stream[Int]): Stream[Int] = {
   Stream.cons(
     numbers.head,
     sieve(for (x <- numbers.tail if x % numbers.head > 0) yield x))
 }

 sieve(is)
}

def main(args : Array[String]) = {

 primes take 100 foreach println
}
}

object Primes2 {
def primes = {
 def sieve(is: Stream[Int]): Stream[Int] = {
   val h = is.head
   Stream.cons(h, sieve(is filter (_ % h > 0)))
 }

 sieve(Stream.from(2))
}

def main(args: Array[String]) {
 println(primes take 100 toList)
}
}

Note the use of the 'take' method to extract the first 100 primes from the stream (so the program terminates!).


This second example shows how we can define a Lazy list like trait and then use it to implement the same, equivalent behavior:


Example 2:

package primes


object PrimesLazyTrait {

sealed trait Lazy[+A] {
 def head: A = this match {
   case Nil => error("head called on empty")
   case Cons(h, _) => h()
 }

 def tail: Lazy[A] = this match {
   case Nil => error("tail on empty")
   case Cons(_, t) => t()
 }

 def filter(p: A => Boolean): Lazy[A] = this match {
   case Nil => Nil
   case Cons(h, t) => if(p(h())) Cons(h, () => t() filter p) else t() filter p
 }

 def foreach(f: A => Unit) {
   this match {
     case Nil =>
     case Cons(h, t) => {
       f(h())
       t() foreach f
     }
   }
 }

 def toList: List[A] = this match {
   case Nil => scala.Nil
   case Cons(h, t) => h() :: t().toList
 }
}

final case class Cons[+A](h: () => A, t: () => Lazy[A]) extends Lazy[A]
case object Nil extends Lazy[Nothing]

def from(n: Int): Lazy[Int] = Cons(() => n, () => from(n + 1))

def primes = {
 def sieve(is: => Lazy[Int]): Lazy[Int] = {
   lazy val h = is.head
   Cons(() => h, () => sieve(is filter (_ % h > 0)))
 }

 sieve(from(2))
}

def main(args: Array[String]) {
 primes foreach println
}
}

In this version we see the Lazy trait provides the necessary methods head, tail, filter, foreach and toList.


These little examples help demonstrate some of the power, elegance and conciseness of lazy functional programming - as well as the beauty of this Ancient Greek algorithm for finding primes.


The basic algorithms complexity is:

• O((nlogn)(loglogn))

And has a memory requirement of:

• O(n).

Without any optimization.

--

Additional example - e (Euler's number):

Calculating e, a list of converging numbers in the sequence of e

e can be defined as lim n->inf ( 1 + 1/n)^n and therefore expressed directly as a function e of n as follows:

def e(n : Int) = { Math.pow((1.0 + (1.0/n)), n) }

So, how can we turn this into a stream? If we create a stream of numbers from 1 that are mapped using the e function, which can be defined as an anon lambda argument to map:

val es = Stream.from(1).map((n => { Math.pow((1.0 + (1.0/n)), n) }))

Example usage of the e stream:

es take 5 toList


.

Scala actors, an introduction with some simple examples

The Scala programming language provides an Actor based framework for handling concurrency.

Scala's Actor model for concurrent programming was originally inspired by the Erlang programming language.

The actor model is a system of asynchronous message passing for concurrent programming, rather than the typical shared data and locks model. The shared data and locks model has some inherent difficulties that make programming in this way difficult and error prone. Major problems with shared data and locks include the well known dead-lock problem, as well as live locks and the general problem of locking shared mutable data without affecting program scalability and performance. Whilst Scala's actor messaging framework is build around asynchronous messaging, synchronous messaging is provided on top of this for convenience.

The Scala's actor model is based around an actor library and the Actor trait, along with some simple syntactical constructs for sending and receiving messages.

The actor library can be included into a project using:

import scala.actors.Actor._

The simplest way to start an actor is to declare an object/class that extends the class Actor and in the body of the actor declare an act() {} method to do the work. The actor x can then be started much like a thread, using x.start(). The act() method is much like the Java Thread's run() method.

A more succinct method is to declare a variable val x = actor {} and put the action definition directly between the braces (no act method required). What happens here is that actor is a helper method on Actor that creates and starts the actor - so there is no need to call x.start() explicitly when using this approach.

Actors can receive messages using the receive {} method. The receive message is passed a partial function to receive the messages. Typically the body of the receive method uses case pattern matching to determine what to do with the message.

A message can be sent to an actor using the ! operation. For example, an Int can be sent to actor x using: x ! 3

All actors get their own thread to call the receive function - this causes scalability problems when there are many actors with receive functions. The way to overcome this in Scala is to use the react() {} method instead. React is similar to receive except it doesn't not need a native thread to run and but must call itself when done to receive more messages - apart from this both are the same in that they both take a partial function.

Scala provides a convenience to avoid having to call act/react within a react method, this is the loop construct. This ends up looking as simple as:

loop {
 react {
   // message handling body goes here
 }
}

Note that react itself does not end end by returning up the call stack in the normal way, all calls to react result in an exception.

Within a receive or react method, an actor can reply to the sender of the received message by messaging the special identifier "sender", which represents the source of the message.


Example 1:

This simple example shows the most basic way to create an actor, by extending Actor, creating an instance and calling start on it.

package scalaactors1

import scala.actors._

class Actor1 extends Actor {

 def act {
   var x = 1
   while (true) {
     println("actor1! " + x)
     x = x + 1
     Thread.sleep(500)
   }
 }
}

object TestActors1 {

 /**
  * @param args the command line arguments
  */
 def main(args: Array[String]) = {

   println(">>main() - starting")

   val actor1 = new Actor1()

   actor1.start()

   println("<<main() - ending")
 }
}

Example 2:

This example creates a couple of actors using the val x = actor {} constructs. Each actor will automatically start and run concurrently, outputting a message and sleeping in an infinite loop. If you run this you can observe that the main thread starts and ends, the messages from the two actors are interleaved and run even after the main method has ended.

package scalaactors1

import scala.actors.Actor._

object TestActors2 {

 /**
  * @param args the command line arguments
  */
 def main(args: Array[String]) = {

   println(">>main() - starting")

  
   val actor1 = actor {

     var x = 1
     while (true) {
       println("actor1! " + x)
       x = x + 1
       Thread.sleep(500)
     }
   }

   val actor2 = actor {

     var x = 1
     while (true) {
       println("actor2! " + x)
       x = x + 1
       Thread.sleep(1000)
     }
   }

   println("<<main() - ending")
 }
}

Example 3:

This example is slightly more complex.

Actor kbReaderActor takes input from the keyboard (as Chars) and passes them one by one to the actor kbProcessorActor which prints out the received character and then uses a 3rd actor called sleep to sleep for the specified amount of time before then waking up the kbProcessorActor (to simulate some "work" that takes a finite amount of time to complete). Note that sleep signals the "sender" using a simple case class to represent the message type (with no arguments).

package scalaactors1

import scala.actors.Actor._

case class Wakeup // simple signalling case class


// simple actor example
object TestActors3 {

 def main(args: Array[String]) = {

   println(">>Starting")

   val sleep = actor {

     loop {
       react {
         case x : int => {
           println("sleeping for " + x)
          
           java.lang.Thread.sleep(x)

           println("waking up sender...")

           sender ! Wakeup
         }
       }
     }
   }

   val keyProcessorActor = actor {

     println(">>keyProcessorActor starting")

     var key : Option[Char] = null

     loop {

       react {
         case 'q' => exit() // 'q' signifies quit app!
         case x : Char => println("keyProcessorActor received '" + x + "'")

           sleep ! 1000  // ask the sleep actor to sleep, we will get a Wakeup call when done

           // now wait for our wakeup
           var r = false

           do {
             receive {
               case Wakeup => r = true
             }
           } while (!r)
       }
     }

     println("<<keyProcessorActor ending")
   }

   val kbReaderActor = actor {

     println(">>kbReaderActor starting")

     var key : Char = ' '

     do {

       println("kbReaderActor waiting for input")
       val i = System.in.read()
          
       key = i.asInstanceOf[Char]

       println("Received input " + key)

       // message actor1 with the key read from the console
       keyProcessorActor ! key
          
     } while (key != 'q')

     println("<<kbReaderActor ending")
   }
  
   println("<<Application Ending")
 }
}

.

Quantum Entanglement, entanglement with 2 electron singlet

(and now for something completely different... Quantum mechanics and quantum entanglement)

Quantum Entanglement: Entanglement with 2 element quantum singlet.

Having recently emailed Leonard Susskind (Stanford CA) with a question regarding entanglement of a 3rd element with a 2 element system in the quantum singlet state (an entangled pair).

Leonard Susskind is the Felix Bloch professor of theoretical physics at Stanford University in the field of string theory and quantum field theory http://en.wikipedia.org/wiki/Leonard_Susskind

Susskind is widely regarded as one of the fathers of String Theory.

So naturally, I was somewhat surprised when I actually got a detailed response, and the answer is very interesting and informative too! Like most things in Quantum mechanics, the result is not something that could be guest or anticipated, it's not something that could be expected using classical intuition or experience.


Here is the reply:

--

Let’s begin with the initial state consisting of two electrons in a singlet state |ud-du> .( I should include a factor of one-over-square-root-of-2 to normalize the state but it’s too hard to type in Word so I will leave it to you.) Now add another electron in the up state— |u). Also, in order to keep track of photons, lets indicate that there are no photons present with the notation |0}. The initial state is,

[ |ud-du> |u) ] |0}

Now let’s rearrange the symbols so as to group electrons 2 and 3 together. This is just a notational device. The initial state is

[ |u> |du) - |d>|uu) ] |0}

Now use the trivial identity

|du) = ½ |du-ud) + ½ |du+ud)

to rewrite it

=½ [ |u> |du-ud) ] |0} + ½ [ |u> |du+ud) ] |0}

-[ |d>|uu) ] |0}

Now think of electron 2 and 3 as close one another, while electron 1 is off in the distance. In the first term 2-3 are in a singlet state. Nothing happens to it. In the other two terms the 2-3 system is orthogonal to the singlet. The 2-3 system will interact to emit a photon, and decay to the singlet in those cases, although the photons will be in different states in the two terms. Denoting the presence of the photon by |γ} and |γ’}, the final state will be

=½ [ |u> |du-ud) ] |0} + ½ [ |u> |du-ud) ] |γ}

-[ |d>|du-ud)] |γ’} (note, there is missing sqrt2)

So what do we have in the end? A superposition of states in which the 2-3 system is in the singlet and

1. electron 1 is up with no photon

2. electron 1 is up with a photon in state |γ}

3. electron 1 is down with a photon in state |γ’}.

If there is no photon or a photon in state |γ} then we know that electron 1 is up. If there is a photon in state |γ’} then e-1 must be down.

--

Having such a brilliantly and concise response was fantastic!

I've gone on to calculate the trivial equations to determine the probability in each state, as follows:

Given the probabilities of the 3 possibilities must add up to 1, taking the coefficients as lambda, the probability is given by lambda.lambda* which for real numbers is just lambda^2, so:

=½ [ |u> |du-ud) ] |0} + ½ [ |u> |du-ud) ] |γ}
-[ |d>|du-ud)] |γ’} (note, there is missing sqrt2)

a. electron 1 is up with no photon

|      1      | 2
| ------------|      = 1/4 = p1 = 0.25
|  2 sqrt(2)  |

b. electron 1 is up with a photon in state |γ}

p2 = 0.25


c. electron 1 is down with a photon in state |γ’}.

|      1      | 2
| ------------|      = 1/2 = p3 = 0.5
|  sqrt(2)    |

Google document:

http://docs.google.com/View?id=df4zskcg_25d8xtc9hp


The Stanford course "Modern Theoretical Physics - Fall 2006" by Leonard Susskind is available on iTunes-U (highly recommended!).


.

Basic Crib sheet for Mercurial hg

Mercurial (hg) is a distributed version control system, with many similarities to Subversion (svn). Being distributed, means people can work offline and still keep their version history local, merging changes with each other by exporting and importing the repository changes periodically.

Generally speaking mercurial is very simple and easy to use, but here are a few commands for quick reference:


Basic crib for Mecurial HG

Clone a repository from a web URL:

hg clone http://www.selenic.com/repo/hello my-hello

Clone from another local repository:

hg clone existing-repos clone-repos

Make a new repository:

hg init

Add files:

hg add

Committing changes:

hg commit (hg ci)

Pull changes from one repository to another:

hg pull

Note: this doesn't update the working directory, to do this update the working directory:

hg update (hg up)

Exporting and import:

hg export -o filename tip

hg import -o filename

Other common commands:

hg log
hg status (hg st)
hg diff
hg revert
hg (-q) tip


HG Editor, the editor for HG comments is determined in the following order:

HGEDITOR environment variable

editor configuration option in [ui] section (in hgrc or passed with --config ui.editor command-line option).

VISUAL environment variable

EDITOR environment variable

vi, if none of the above is set


References:

Mercurial home:

http://www.selenic.com/mercurial/wiki/Mercurial

Mecurial tutorial:

http://www.selenic.com/mercurial/wiki/Tutorial

Quick reference and cheat sheets:

http://www.selenic.com/mercurial/wiki/QuickReferenceCardsAndCheatSheets


.

GlassFish v2.1 b60e crib sheet / installation notes

Recently, having been working on a project that's migrated from JBoss 4.2.2 to GlassFish v2.1, I needed to hand over a crib sheet / quick guide to people supporting the live system, so as it might be useful in general. Only really covering the basics, but here it is anyway:

GlassFish AS Basic Crib / notes:

Prerequisites:

• Java JDK 6.x latest
  

GlassFish AS version V2.1 b60e Final Release

Download jar here http://java.net/download/javaee5/v2.1_branch/promoted/Linux/glassfish-installer-v2.1-b60e-linux.jar

For RHEL derived CentOS, recommended installation would be something like /usr/local/projectname/glassfish

Installation:

java -Xmx256m -jar glassfish-installer-v2.1-b60e-linux.jar

cd glassfish

chmod -R +x lib/ant/bin

lib/ant/bin/ant -f setup.xml

Follow the installer instructions, accepting EULA and any defaults presented...

This will unpack and install the server, creating a default domain called "domain1"

A domain is an administrative "unit" - possibly related to, but not the same as an actual domain.

All domains live in: {glassfish_home}/domains/

We need just one for now, so all our stuff will be in:

{glassfish_home}/domains/domain1/

the installation process will create a default empty domain, domain1 with a default config file, the main configuration file is called domain.xml

e.g. {glassfish_home}/domains/domain1/config.xml

This file may contain some host /installation specific information, as well as stuff specific to our application.

Starting and stopping GlassFish AS:

{glassfish_home}/bin/asadmin start-domain domain1

{glassfish_home}/bin/asadmin stop-domain domain1

If all is good you will see confirmation on the command prompt when started, such as:

Domain domain1 started

Managing GlassFish AS:

By default, the web based management console is available on port :4848

The default admin account is username = admin, password = adminadmin

URL is: http://{hostname}:4848

Web-app deployment options:

There are a few options, the main two are:

Manually, using autodeploy directory

Simply copy .war file to: {glassfish_home}/domains/domain1/autodeploy

Deploying via the admin console:

On main menu on left, click on and expand the Web Applications menu entry

Click on the Deploy button, typically when deploying from a local file, use the "Packaged file to be uploaded to the server" browse button to locate the local war file. Browse for the war file, select it and click Ok

When completed, the web app will appear in the application list (if all is well)

The other settings can be left as defaults. Optionally we can chose to pre-compile JSPs here etc.

Server Logs:

The main server logs appear in the domain under logs, i.e.

{glassfish_home}/domains/domain1/logs/server.log

Logs can also be viewed (and configured, including log rotation) via the admin console, under the Application Server menu entry

Monitoring and management:

JConsole:

GlassFish is a JMX compliant app server (listening by default to port 8686)

Using jconsole, remote connect to: http://{hostname}:8686

Using the same default account: admin/adminadmin

Admin console:

Under the Application Server in the main menu - there are entries for server Monitoring.

This includes a built in chart and call flow logging - which is potentially very useful for diagnostics and monitoring…

HTTPS / SSL:

GlassFish AS will do HTTPS out of the box (using a default Sun Microsystems certificate).

HTTPS is served by default on port :8181

Hopefully in the near future I'll but together something to cover clustering and load balancing too.

.