Algorithms in Functional Style -Scala

Data Structures and algorithms play a pivotal role in day-to-day development of applications/solutions.When we intend to address a problem, the discussion starts with -

  • what data structures/in-memory collections to use ?
  • How to instantiate the values ?
  • Whats the flow of the approach ?

Functional style of writing code takes a different approach. We never intend to discuss on what collections / variable instantiation. It starts with -

  • Whats the input ?
  • What construct could be applied to arrive at the output
  • How best we could avoid variable creation ?

Here are some of the algorithms I have coded in functional style.

  1. Depth First Search:

When implementing DFS, we talk about constructing binary search tree and using stack to get the DFS output. Functional way of implementations differs from this as -

Let’s say we have graph of connected nodes as -

graph of connected nodes

We receive the input of connection between nodes as list -

List((0, 1), (0, 2), (1, 2), (2,0), (2, 3))

The DFS algorithm could be implemented as -

object DFS {

def main(args:Array[String]): Unit =
{
val connectedNodes = List((0, 1), (0, 2), (1, 2), (2,0), (2, 3))

val resultList = scala.collection.mutable.ArrayBuffer[Int]()

val distinctVertices = connectedNodes.map{tuple => List(tuple._1, tuple._2)}.flatten.distinct

val connectedNodesGrouped = connectedNodes
.groupBy(tuple => tuple._1).map{case(key:Int, list:List[(Int,Int)]) => (key, list.map{t => t._2} )}

val vertices = distinctVertices.length

val visited = Array.ofDim[Boolean](vertices).toBuffer

DFSUtil(2, visited, connectedNodesGrouped, resultList)

resultList.foreach(println)

}

def DFSUtil(vertex:Int, visited:mutable.Buffer[Boolean], connectedNodesGrouped:Map[Int, List[Int]], resultList:ArrayBuffer[Int]): ArrayBuffer[Int] =
{
visited.update(vertex, true)
resultList += vertex
val optionalValueList = connectedNodesGrouped.get(vertex)
if(optionalValueList != None)
{
val valueList = optionalValueList.get

valueList.foreach{ele =>
if(!visited(ele))
DFSUtil(ele, visited, connectedNodesGrouped, resultList)

}
resultList
}

else resultList
}

}

2. Evaluating Expression:

For evaluating expression, the common notion is to use stack, push the operands and when an operator arrives the pop the stack twice, perform the operation and push the result into stack

The implementation in functional style looks as -

object ExpressionEval {

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

val arr = Array("18", "4", "2", "*", "+")

val finalres = arr.reduce { (a, b) =>

if ( ( Try(a.toInt).isSuccess && Try(b.toInt).isSuccess ) || (a.contains(":") && Try(b.toInt).isSuccess )) a + ":" + b

else {
val parts = a.split(":")
val len = parts.length
val (x, y) = (parts(len - 1).toInt, parts(len - 2).toInt)
val res = b match {
case "*" => x * y
case "-" => x - y
case "+" => x + y
case "/" => x / y
}
parts.dropRight(2).:+(res).mkString(":")
}
}

println("Final Result:" + finalres)
}

}

Functional style of programming is not a paradigm. It’s your thought process.

I am an author, speaker, explorer and foodie. Anything in technology or psychology interests me. Profile to know about stuff: www.linkedin.com/in/padmachitturi