# 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.

**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 -

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.