Thursday, May 7, 2015

Java with Try, Failure, and Success based computations


In this post I will try to borrow one of the Scala nice related computation models into the Java language.

It is about the Try/Success/Failure computation model implemented by the Scala libraries.

In Scala the Try type represents a computation that may either result in an exception, or return a successfully computed value.

More details could be found here:
http://www.scala-lang.org/files/archive/nightly/docs/library/index.html#scala.util.Try


In the following chunks of code I will not use any functional capabilities of the JDK 1.8.

The whole point is to be able to chain more computations which result could be either a success or a failure. At the first apparition of the failure in any of the computations the remained computations will not be applied anymore and the  failure will be propagated to the caller.

Please look at the following code snippet :

ComputationlResult<String> res = ComputationalTry.initComputation("1").bind(t0).bind(t1).getResult();

Here we pass an argument in our case the string "1" that will be processed one by one by the transformer "t0" and "t1".

We get the result of the chained computations stored in the "res" variable.

We can check if the chained computations were all successfully executed or if one of them failed. We can also extract the computed value or the cause of failure from the result.

Note also the "ITransformer" interface which presence here is needed when we do not use a functional approach.
Its only method "transform" is passed in the argument of generic type T and its function would be to apply a transformation on this argument and return the result.

Some would say that this is a monad based computation type. I wont go that far, so please regard this like a different way of chaining computations.

If you want a nice description of a monad which by the way is a simple structure and it should not be that hard to be comprehended  please watch the first lectures given by Martin Odersky on Coursera.

[It might be just a coincidence, but for some reason after Martin's lecture on monads it seems that some light was shed on this topic]

Here is the link:  Principles of Reactive Programming


And here is the whole code:

       

public class ComputationalTry<T> { 

  final private ComputationlResult<T> result;
 
 static public <P> ComputationalTry<P> initComputation(P argument)
 {
  return new ComputationalTry<P>(argument);
 }
 
 private ComputationalTry(T param)
 {
  this.result = new ComputationalSuccess<T>(param);
 }
 
 private ComputationalTry(ComputationlResult<T> result)
 {
  this.result= result;
 } 
 
 private ComputationlResult<T> applyTransformer(T t, ITransformer<T> transformer) {
  try
  {
   return new ComputationalSuccess<T>(transformer.transform(t));
  }
  catch (Exception throwable)
  {
   return new ComputationalFailure<T, Exception>(throwable);
  }
 }
 
 public ComputationalTry<T> bind(ITransformer<T> transformer)
 {  
  if (result.isSuccess())
  {
   ComputationlResult<T> resultAfterTransf = this.applyTransformer(result.getResult(), transformer);   
   return new ComputationalTry<T>(resultAfterTransf);
  }
  else
  {   
   return new ComputationalTry<T>(result);
  }
 } 
 
 public ComputationlResult<T> getResult()
 {
  return this.result;
 }
}


public class ComputationalFailure<T, E extends Throwable> implements ComputationlResult<T> {
 
 public ComputationalFailure(E exception)
 {
  this.exception = exception;
 }

  final private E exception;
 
 @Override
 public T getResult() {
  return null;
 }

  @Override
 public E getError() {
  return exception;
 }

  @Override
 public boolean isSuccess() {
  return false;
 }
 
}


public class ComputationalSuccess<T> implements ComputationlResult<T> {
 
 public ComputationalSuccess(T result)
 {
  this.result = result;
 }
 
 final private T result;

  @Override
 public T getResult() {
  return result;
 }

  @Override
 public Throwable getError() {
  return null;
 }
 
 @Override
 public boolean isSuccess() {
  return true;
 }
}


public interface ComputationlResult<T> {
 
 T getResult();
 
 <E extends Throwable> E getError();
 
 boolean isSuccess();
 
}


public interface ITransformer<T> {
 
 public T transform(T t);
 
}


public class Test {

 public static void main(String[] args) {
  
  ITransformer<String> t0 = new ITransformer<String>() {
   @Override
   public String transform(String t) {
    //return t + t;
    throw new RuntimeException("some exception 1");    
   }
  };

  ITransformer<String> t1 = new ITransformer<String>() {
   @Override
   public String transform(String t) {
    return "<" + t + ">";
    //throw new RuntimeException("some exception 2");
   }
  };
  
  ComputationlResult<String> res = ComputationalTry.initComputation("1").bind(t0).bind(t1).getResult();
  
  System.out.println(res);
  
  if (res.isSuccess())
  {
   System.out.println(res.getResult());
  }
  else
  {
   System.out.println(res.getError());
  }
 }
}
       
 
Thank you for bearing with me. Any suggestions are much appreciated.

Tuesday, November 5, 2013

Scala Actors. Handling messages using Try, Success, Failure

In this short post I will try to show a general method that could be used to handle actor messages. I want to also mention that this is not specifically related to actor supervision or other Akka actor advanced topics.

Let's say that we have an actor that is supposed to receive some events.

We want that this actor to be able to handle the received events in a generic way, so it should catch the exceptions occurring inside the actual handlers and it should also know to handle them accordingly.

I will provide you with a possible implementation that is using the Try Scala type.
More information about it can be found here:
http://www.scala-lang.org/api/current/index.html#scala.util.Try

First, we should introduce a class hierarchy for the types of events our actor is going to receive, send back to its senders, or forward to other actors:

  1. Msg any event received by our actor should extend this class
  2. ResponseMsg - any response sent by the actor back or forwarded to another actor should also extend this event
  3. SuccessMsg, FailureMsg - these are the messages used to wrap the results in case of a successful or a failed execution that might happen inside our actor event handlers

abstract class Msg
abstract class ResponseMsg
abstract class SuccessMsg extends ResponseMsg
abstract class FailureMsg extends ResponseMsg

Now, I will define the actual GenericActorHandler trait:

import akka.actor.{ Actor, ActorRef, ActorSystem, Props }
import scala.util.{ Try, Success, Failure }
trait GenericActorHandler extends Actor {
  def handleTryWithReply[S <: SuccessMsg, F <: FailureMsg](fun: => Try[S], createFailureMsg: Throwable => F): Unit = {
    fun match {
      case Success(successResp) =>
        sender ! successResp
      case Failure(e) =>
        sender ! createFailureMsg(e)
    }
  }
  def handleTryWithForward[M <: Msg, F <: FailureMsg](fun: => Try[(ActorRef, M)], createFailureMsg: Throwable => F): Unit = {
    fun match {
      case Success(actorMsgTuple) =>
        actorMsgTuple._1 forward actorMsgTuple._2
      case Failure(e) =>
        
actorMsgTuple._1 forward createFailureMsg(e)
    }
  }
}


Here is an example of an actor that mixes in the GenericActorHandler actor:

import akka.actor.{ActorRef, Props }
import scala.util.{ Try, Success, Failure }

class CalculatorActor extends GenericHandlerActor {
  def receive = {
    case evt: AddEvt =>
      handleTryWithReply(handleAddEvt(evt), ex => FailureAddEvt(ex.getMessage))
    case evt: DivideEvt =>
      handleTryWithReply(handleDivideEvt(evt), ex => FailureDivideEvt(ex.getMessage))
  }

  private def handleAddEvt(evt: AddEvt ): Try[SuccessAddEvt] =
    Try {
      SuccessAddEvt( evt.a + evt.b)
    }

  private def handleDivideEvt(evt: DivideEvt ): Try[SuccessDivideEvt] =
    Try {
     SuccessDivideEvt(evt.a / evt.b)
    }

and here are the events or messages our calculator actor is handling:

case class AddEvt (a: Int, b: Int) extends Msg
case class SuccessAddEvt(result: Int) extends SuccessMsg
case class FailureAddEvt(reason: String) extends FailureMsg 

case class DivideEvt (a: Int, b: Int) extends Msg
case class SuccessDivideEvt(result: Int) extends SuccessMsg
case class FailureDivideEvt(reason: String) extends FailureMsg
Assuming, that we send DivideEvt(10, 0) to our actor. This event  will be handled by handleDivideEvt. In this case its computation will fail when trying to divide by 0.
The actor will still be able to send back to its sender the exception wrapped inside the FailureDivideEvt response.

Monday, April 1, 2013

Scala DSL for parsing and evaluating of arithmetic expressions

In this post I want to show you a simple way to parse and evaluate arithmetic expressions by using Scala Parser Combinators.

So, I will try to do the followings:
  1. create a parser able to recognize complex arithmetic expressions
  2. parse arithmetic expression and generate the parse result as a list of strings that corresponds to the postfix notation of the initial expression
  3. evaluate the above postfix notation list to generate the value of the arithmetic expression
To better understand the code I would also recommend you to read the following links if you are not that familiar with Scala parser combinators and the postfix notation:

Chapter 31 of Programming in Scala, First Edition Combinator Parsing by Martin Odersky, Lex Spoon, and Bill Venners December 10, 2008

Reverse Polish notation

And here is the code:


import scala.util.parsing.combinator._
/**
* @author Nicolae Caralicea
* @version 1.0, 04/01/2013
*/
class Arithm extends JavaTokenParsers {
  def expr: Parser[List[String]] = term ~ rep(addTerm | minusTerm) ^^
    { case termValue ~ repValue => termValue ::: repValue.flatten }

  def addTerm: Parser[List[String]] = "+" ~ term ^^
    { case "+" ~ termValue => termValue ::: List("+") }

  def minusTerm: Parser[List[String]] = "-" ~ term ^^
    { case "-" ~ termValue => termValue ::: List("-") }

  def term: Parser[List[String]] = factor ~ rep(multiplyFactor | divideFactor) ^^
    {
      case factorValue1 ~ repfactor => factorValue1 ::: repfactor.flatten
    }

  def multiplyFactor: Parser[List[String]] = "*" ~ factor ^^
    { case "*" ~ factorValue => factorValue ::: List("*") }

  def divideFactor: Parser[List[String]] = "/" ~ factor ^^
    { case "/" ~ factorValue => factorValue ::: List("/") }

  def factor: Parser[List[String]] = floatingPointConstant | parantExpr

  def floatingPointConstant: Parser[List[String]] = floatingPointNumber ^^
    {
      case value => List[String](value)
    }

  def parantExpr: Parser[List[String]] = "(" ~ expr ~ ")" ^^
    {
      case "(" ~ exprValue ~ ")" => exprValue
    }

  def evaluateExpr(expression: String): Double = {
    val parseRes = parseAll(expr, expression)
    if (parseRes.successful) evaluatePostfix(parseRes.get)
    else throw new RuntimeException(parseRes.toString())
  }
  private def evaluatePostfix(postfixExpressionList: List[String]): Double = {
    import scala.collection.immutable.Stack

    def multiply(a: Double, b: Double) = a * b
    def divide(a: Double, b: Double) = a / b
    def add(a: Double, b: Double) = a + b
    def subtract(a: Double, b: Double) = a - b

    def executeOpOnStack(stack: Stack[Any], operation: (Double, Double) => Double): (Stack[Any], Double) = {
      val el1 = stack.top
      val updatedStack1 = stack.pop
      val el2 = updatedStack1.top
      val updatedStack2 = updatedStack1.pop
      val value = operation(el2.toString.toDouble, el1.toString.toDouble)
      (updatedStack2.push(operation(el2.toString.toDouble, el1.toString.toDouble)), value)
    }
    if (postfixExpressionList.length == 1) toDouble(postfixExpressionList.head)
    else {
      val initial: (Stack[Any], Double) = (Stack(), null.asInstanceOf[Double])
      val res = postfixExpressionList.foldLeft(initial)((computed, item) =>
        item match {
          case "*" => executeOpOnStack(computed._1, multiply)
          case "/" => executeOpOnStack(computed._1, divide)
          case "+" => executeOpOnStack(computed._1, add)
          case "-" => executeOpOnStack(computed._1, subtract)
          case other => (computed._1.push(other), computed._2)
        })
      res._2
    }
}

object TestArithmDSL {
  def main(args: Array[String]): Unit = {
    val arithm = new Arithm
    val actual = arithm.evaluateExpr("(12 + 4 * 6) * ((2 + 3 * ( 4 + 2 ) ) * ( 5 + 12 ))")
    val expected: Double = (12 + 4 * 6) * ((2 + 3 * ( 4 + 2 ) ) * ( 5 + 12 ))
    assert(actual == expected)
  }
}


Saturday, January 26, 2013

Graphs - Finding the Minimum Spanning Tree - A Generic Scala implementation of Prim's algorithm



In this post I am trying to provide you a basic implementation of Prim's algorithm in Scala.

I also tried to make it more generic.

So, here is how I defined the Node, Edge, and UndirectedGraph (just a part of it) classes.

case class Node(name: String)
case class Edge[T <% Ordered[T]](xNodeName: String, yNodeName: String, cost: T)
case class UndirectedGraph[T <% Ordered[T]](nodes: List[Node], edgetList: List[Edge[T]])

Here is the declaration of the  function that provides the sought result:


def computeMinimumSpanningTreeUsingPrim(): UndirectedGraph[T]

 I am also using this opportunity to introduce you to "Views and view bounds".
This is another great Scala feature. I'm not going to dive into more details about it.

So, as long as there is a "view" from T to Ordered[T], this algorithm is supposed to work properly.

Note that, "T <% Ordered[T]" is one of the most used views in Scala.


On Wikipedia you can also find a good explanation if the Prim's algorithm, so I wont go into more details.

Here is the link:

http://en.wikipedia.org/wiki/Prim%27s_algorithm



And here is the code:


package org.madeforall.graph.mst.prim
/**
 * @author Nicolae Caralicea
 * @version 1.0, 26/01/2013
 */

case class Node(name: String)
case class Edge[T <% Ordered[T]](xNodeName: String, yNodeName: String, cost: T)

case class UndirectedGraph[T <% Ordered[T]](nodes: List[Node], edgetList: List[Edge[T]]) {
  case class NodesEdge[T <% Ordered[T]](xNode: Node, yNode: Node, cost: T)

  def computeMinimumSpanningTreeUsingPrim(): UndirectedGraph[T] =
    computeMinimumSpanningTree(nodes.tail, UndirectedGraph(List(nodes.head), Nil))

    private def computeMinimumSpanningTree(leftNodes: List[Node], mst: UndirectedGraph[T]): UndirectedGraph[T] = {
    leftNodes match {
      case Nil => mst
      case _ =>
        val minCostEdge = minCost(cost(leftNodes, mst)) // xNode belongs to leftNodes, and yNode belongs to mst
        if (minCostEdge == None) throw new Error("disconnected graph")
        val updatedLeftNodes = leftNodes diff List(minCostEdge.get.xNode)
        val updatedMst = UndirectedGraph(
              minCostEdge.get.xNode :: mst.nodes,
              toEdge(minCostEdge.get) :: mst.edgetList)
        computeMinimumSpanningTree(updatedLeftNodes, updatedMst)
    }
  }

  private def toEdge[T <% Ordered[T]](nodesEdge: NodesEdge[T]): Edge[T] =
    Edge(nodesEdge.xNode.name, nodesEdge.yNode.name, nodesEdge.cost)

  private def cost(outsideNodes: List[Node], graph: UndirectedGraph[T]): List[NodesEdge[T]] =
    for {
      node <- outsideNodes
      minCostEdgeNodeToGraph <- minCostEdgeOfNodeToGraph(node, graph.nodes)
    } yield minCostEdgeNodeToGraph

  private def minCost[T <% Ordered[T]](nodesEdgeList: List[NodesEdge[T]]): Option[NodesEdge[T]] = {
    val min: Option[NodesEdge[T]] = None
    nodesEdgeList.foldLeft(min)((comp, itm) =>
      if (comp != None) {
        if (comp.get.cost > itm.cost) Some(itm) else comp
      } else {
        Some(itm)
      })
  }

  private def cost(nodeA: Node, nodeB: Node): Option[T] = {
    val costItem = edgetList.filter(item => {
      (item.xNodeName == nodeA.name && item.yNodeName == nodeB.name) ||
        (item.yNodeName == nodeA.name && item.xNodeName == nodeB.name)
    })
    if (costItem != Nil) Some(costItem.head.cost) else None
  }

  private def minCostEdgeOfNodeToGraph(node: Node, graph: List[Node]): Option[NodesEdge[T]] = {
    val edges = for {
      n <- graph
      cost <- cost(n, node)
    } yield NodesEdge(node, n, cost)
    minCost(edges)
  }
}

To test it you can use something like this:

package org.madeforall.extractor.test
import org.scalatest._
import org.scalatest.matchers._
import org.madeforall.graph.mst.prim._
/**
 * @author Nicolae Caralicea
 * @version 1.0, 26/01/2013
 */
class TestMst extends FlatSpec with ShouldMatchers {
    
  "The minimal spanning resulted whn using the Prim's alghorith" should "be like" in {
    val graph: UndirectedGraph[Double] = UndirectedGraph(
      List(
        Node("A"), Node("B"), Node("C"), Node("D"),
        Node("E"), Node("F"), Node("G"), Node("H"),
        Node("M"), Node("N")),
      List(
        Edge("A", "B", 9.0),
        Edge("A", "F", 6),
        Edge("A", "G", 3),
        Edge("B", "G", 9),
        Edge("B", "M", 8),
        Edge("B", "C", 18),
        Edge("C", "M", 10),
        Edge("C", "N", 3),
        Edge("C", "D", 4),
        Edge("D", "N", 1),
        Edge("D", "E", 4),
        Edge("E", "F", 9),
        Edge("E", "H", 9),
        Edge("E", "M", 7),
        Edge("F", "G", 4),
        Edge("F", "H", 2),
        Edge("H", "G", 2),
        Edge("H", "M", 8),
        Edge("M", "N", 9),
        Edge("M", "G", 9),
        Edge("N", "E", 5)))
    assert(graph.computeMinimumSpanningTreeUsingPrim === UndirectedGraph(
        List(Node("B"), Node("C"), Node("N"), Node("D"), Node("E"), Node("M"), Node("F"), Node("H"), Node("G"), Node("A")),
        List(Edge("B","M",8), Edge("C","N",3), Edge("N","D",1), Edge("D","E",4), Edge("E","M",7), Edge("M","H",8), Edge("F","H",2),
            Edge("H","G",2), Edge("G","A",3))))
  }
    
}

If you want to use and contribute in any way to this project/code here is the link to its Github repository:

https://github.com/ncaralicea/madeforall



Thursday, January 17, 2013

Simple Scala Text Recognition Patterns

So many times I wanted to be able to extract email addresses, links, specific html tags, simple chunks of code, you name it from simple text, html content, code, etc.

But, every time I ended up looking for the right REGEX expressions, tweaking them, throwing them into my code and forget everything the day after. Next time I would start over again and again.

I think that this library could preserve all these efforts, so bear with me to see how Scala with its nice features like Extractors, REGEX, and Manifest classes can make your life much easier.


Let's assume that we have some text based content (txt, html, etc) and that our goals are the followings:

  • We want to be able to easily extract email addresses, links, images, etc from the above content
  • We want to have a decent and common data format of what we extract
  • We want to easily add new patterns to the existent text recognition patterns, so we would be able to recognize more patterns in our text based contents

The madeforall's extractor library is a Scala based library that is meant to help us reach the above goals.

Here is a simple description of how to use and extend this library:

We create a RecognizableItemsExtractor object, to which we pass as a parameter an RecognitionPattern object

Any RecognitionPattern object should:
- implement the unapply extraction method (Scala based extractor)
- mix in the RecognitionPattern trait
 
For instance, to support email recognition, we could do the followings:

case class Email(user: String, domain: String) extends Recognizable {
  override def toString() = {
    user + "@" + domain
  }
}
object EmailRecognitionPattern extends RecognitionPattern {
  // The extraction method
  def unapply(str: String): Option[(String, String)] = {
    val parts = str split "@"
    if (parts.length == 2) Some(parts(0), parts(1)) else None
  }
  // email regex
  val regexPattern = """(?i)\b[A-Z0-9._%+-]+@[A-Z0-9.-]+\.[A-Z]{2,4}\b""".r

  def recognize(value: String): Option[Recognizable] = {
    value match {
      case EmailRecognitionPattern(user, domain) =>
        Some(Email(user, domain))
      case _ =>
        None
    }
  }
}

Then, to extract all the emails from our text we could do the followings:

val textToAnalyze: String = "<<some content>>"
val recog = RecognizableItemsExtractor(List(EmailRecognitionPattern))
val emailList: List[Recognizable] = recog.analyzeText(textToAnalyze)

If we want to extract emails and links we can also add more recognition patterns to the above RecognizableItemsExtractor.

RecognizableItemsExtractor(List(EmailRecognitionPattern, LinkRecognitionPattern))
val emailAndLinkList: List[Recognizable] = recog.analyzeText(textToAnalyze)

The above emailAndLinkList list contains both emails and links.
To filter out emails we could use the following filterByType function.

val onlyEmailList = recog.filterByType[Email](emailAndLinkList)

Here is the definition of the RecognizableItemsExtractor's filterByType function:

  def filterByType[T <: Recognizable](t: List[Recognizable])(implicit mf: Manifest[T]) =
    t.filter(e => mf.erasure.isInstance(e))

It is based on Scala class manifest feature, that is helping the runtime
with the type information provided as hint by the Scala compiler.
Type erasure is still present in Scala like in Java.
The creators of Scala gave us this helpful manifest class support to overcome
the JVM's type erasure limitations.

If you want to use and contribute in any way to this project here is the link to its Github repository:

https://github.com/ncaralicea/madeforall





      

Saturday, November 12, 2011

MadeForAll (Alfa) - Social collaboration & Knowledge Sharing platform



MadeForAll is a platform where people can easily create, search, and share information. 


They can share this information privately with their own groups or they can also make the information available to anyone.


It is people's choice to define their own data structures that represent the best their knowledge. 


Either programmers or just web addicts in searching for new ways of doing collaboration with their peers, MadeForAll could be the answer.


You might also get a better idea of what you can do on MadeForAll from some of its screenshots,


The website is just in its Alpha stage and any suggestions are more than welcomed.


Feel free to contact us or post comments on MadeForAll.


I will soon expose its API, so MadeForAll could be easily integrated into your own applications.


I might also opensource the whole MadeForAll platform so other developers could join and give a hand too.
It is too overwhelming to work alone on it and I feel like it would take me forever to finish it, so I am really optimistic that I would open source MadeeForAll eventually.


So, if you are a developer that really loves Scala, Erlang, NoSQL, Spring, and other great technologies, and you also want to contribute to MadeForAll, there are many exiting things waiting ahead for you.
  
For now, just have a look and give me some suggestions if you feel it.

Sunday, July 31, 2011

Scala – Get a taste of implicit parameters through Quicksort

Why is Scala great?

I'm tempted simply to state that Scala is great. However, I know that many developers have not yet heard of it, so I'll try to explain why that's true.

Why? Because it offers a number of goodies that other programming languages don't.

For those who don't know this yet, I would ask them to imagine shopping for the best 10-year-long package tour. 

I wouldn't say that everything inside Scala's Dream Package is unique or without peer, but the price you'll pay and the goodies you'll get make it by far your best overall choice for those years to come.

What are the features that make Scala so great? Among other things, it's concise, elegant, type-safe, object-oriented, functional, extremely fast, compatible/inter-operable with Java, has great pattern matching, and uses a powerful actor model borrowed form Erlang.

Wouldn't that be a delightful 10-year tour on the Scala boat?

So, give it a shot and get onboard -- there's plenty of space, and everyone's friendly too!

In other words, Scala is versatile enough to be used everywhere, and it has a large community with excellent support.

I realize that a newcomer can hardly avoid initial sea-sickness, but there are at least 10 years ahead of real joy. A few months of hardship will more than repay, trust me.

I would like to try to convince you by showing you one of Scala's unique features  -- Implicit Parameters.

What are they? Some parameters used to define a method can be marked with the keyword 'implicit'. Where are such parameters used?

Under certain circumstances if the developer has not provided some parameters in a function call, the compiler will try to implicitly insert the values for all those missing parameters, so the code will be properly compiled and the function call will be properly executed.

In the coming examples I will try to gradually show you when and why is good to have implicit parameters.

I will try to use Scala to implement  the Quicksort algorithm.
Far from being the fastest Scala implementation of Quicksort the implementation shown here is just good enough for our purpose.

Here at the http://en.wikipedia.org/wiki/Quicksort link you can find more about Quicksort.

A naive scala implementation - it only addresses the Int type

object NaiveQuickSort {
  def qsort(list : List[Int]) : List[Int] = {
    list match {
      case List() => List()
      case h :: tail => qsort(tail.filter(_ <= h)) ::: List(h) 
                         ::: qsort(tail.filter(_ > h))
    }
  }
  def main(args: Array[String]): Unit = {
    println(qsort(List(2, 4, 1, 6, 5)))
  }
}

the displayed result is: List(1, 2, 4, 5, 6)

A parametrized implementation - it is a parameteriezed implementation, so it could be used for any types as long as a comparison function for that types has been explicitly provided. You can see the explicitly provided parameter when calling the qsort function. This might be avoided though, but this is a another great topic related to the currying concept.

object ParameterizedQuickSort {
  def qsort[T](less : (T, T) => Boolean)(list : List[T]) : 
    List[T] = {
    list match {
      case List() => List()
      case h :: tail =>
        (qsort(less)(tail.filter(less(_, h)))) ::: List(h) :::       
        (qsort(less)(tail.filter(! less(_, h))))
    }
  }
  def main(args: Array[String]): Unit = {
    println(qsort((x: Int, y: Int) => x < y)(List(2, 4, 1, 6, 
         5)))
    println(qsort((x: String, y: String) => x < y)(List("violin", 
     "piano","whistle", "guitar","saxophone")))
   }
}

A parametrized implementation with implicit parameters
As you can see there are 2 lines that defines the comparison functions for the Int and String types. These lines basically let the compiler know what values it can implicitly supply when necessary.


  implicit val lessIntOp = (x: Int, y: Int) => x < y
  implicit val lessStringOp = (x: String, y: String) => x < y


Having the implicit marker for the 'less' parameter of the following line lets the compiler know which parameters of the qsort function might be missing in a function call, so the compiler could insert them when needed.



def qsort[T](list : List[T])(implicit less : (T, T) => Boolean)
  : List[T]


In the following lines the 'less' parameter is not provided and the code still compiles and is properly executed.


println(qsort(List(2, 4, 1, 6, 5)))
println(qsort(List("violin", "piano","whistle", 
  "guitar","saxophone")))


And, here is the whole code you can use to test this.

object ImplicitParameterizedQuickSort {
  implicit val lessIntOp = (x: Int, y: Int) => x < y
  implicit val lessStringOp = (x: String, y: String) => x < y

  def qsort[T](list : List[T])(implicit less : (T, T) => Boolean)
  : List[T] = {
     list match {
      case List() => List()
      case h :: tail =>
        qsort(tail.filter(less(_, h))) ::: List(h) :::  
        qsort(tail.filter(! less(_, h)))
     }
  }
  def main(args: Array[String]): Unit = {
    println(qsort(List(2, 4, 1, 6, 5)))
    println(qsort(List("violin", "piano","whistle",  
      "guitar","saxophone")))
   }
}


This is it. Just a sec.
Please look at the next chunk of Erlang code (the code was taken from Erlang Programming - Francesco's book):


qsort([]) -> [];
qsort([X | Xs] ->
  qsort([Y || Y <- Xs, Y =< X]) ++ [X] ++ qsort([Y || Y <-Xs, Y > X]).


and compare it with this:



def qsort[T](list : List[T])(implicit less : (T, T) => Boolean)
  : List[T] = {
     list match {
      case List() => List()
      case h :: tail =>
        qsort(tail.filter(less(_, h))) ::: List(h) :::  
        qsort(tail.filter(! less(_, h)))
  }
}



They look pretty similar don't they?


This is another reason Scala is just great. It resembles Erlang in so many ways.