This week, I’ll first implement the Dijkstra algorithm, then migrate the code to a more functional-friendly design.
This is the 4th post in the From Imperative to Functional Programming focus series.Other posts include:
- From Imperative to Functional Programming using Arrow
- From Imperative to Functional Programming, an approach
- From Imperative to Functional Programming: a grouping issue (and how to solve it)
- From Imperative to Functional Programming: the Dijkstra algorithm (this post)
The Dijkstra algorithm in a few words
A graph consists of both nodes and edges. An edge links two nodes.
There are different types of graphs: in weighted graphs, each edge has an associated weight.
In directed graphs, an edge can only be traveled in one direction; in undirected graphs, it can be traveled in any direction. Hence,
Dijkstra’s algorithm allows to find the shortest path in a graph. An unweighted graph can be considered a weighted graph where all weights are the same, and an edge in an undirected graph is the equivalent of two edges in each direction in a directed graph - with the same weight. Hence, any graph is a candidate structure for the algorithm, weighted or not, directed or not. The only requirement is that weights need to be positive.
The algorithm is as follows:
- Set the start node as the current node
- Repeat the following until the current node is the end node:
- Find all nodes accessible by edges from the current node
- Compute the overall weight to access unvisited nodes
- Mark the current node as visited
- Travel to the node with the less weight
A naive but working approach
Here is a straightforward implementation of the algorithm:
class Graph(private val weightedPaths: Map<String, Map<String, Int>>) {
private val evaluatedPaths = mutableMapOf<String, Int>()
fun findShortestPath(start: String, end: String): Int {
var current = start
while (current != end) {
current = updateShortestPath(current)
}
return evaluatedPaths.getValue(end)
}
private fun updateShortestPath(node: String): String {
val subGraph = weightedPaths[node]
for (entry in subGraph!!) {
val currentDistance = evaluatedPaths
.getOrDefault(entry.key, Integer.MAX_VALUE)
val newDistance = entry.value + evaluatedPaths.getOrDefault(node, 0)
if (newDistance < currentDistance)
evaluatedPaths[entry.key] = newDistance
}
evaluatedPaths.remove(node)
return evaluatedPaths.minBy { it.value }?.key!!
}
}This snippet is definitely not FP-friendly, as it contains both:
- mutable state e.g.
evaluatedPaths - and loops - one
whileloop and oneforloop
Migrating to Functional Programming
Migrating to FP means replacing:
- Loops with recursion
- Global mutable state with a passed around parameter
Additionally, Kotlin programmers might have noticed two usages of the !! operator:
though the type system infers the value can be nullable, we as a developer tell the compiler it cannot.
Removing the !! crutch
There are two occurrences of !!.
Both happen because when getting from a Map, nothing guarantees to the typesystem that there’s a corresponding key:
val map = mapOf("A" to 1)
val a = map.get("A") // 1
val b = map.get("B") // nullThe type returned from get() is nullable.
To make it non-nullable in a more idiomatic way, we can throw an exception if the returned value is null:
val map = mapOf("A" to 1)
val a = map.get("A") ?: throw RuntimeException("Cannot happen")
val b = map.get("B") ?: throw RuntimeException("Will happen")For the compiler, a and b are now of type String, even though at runtime, getting "B" will throw.
While exceptions make functions partial and partial functions do not conform to FP, it’s a good step.
For iteration, it’s even easier. The two following lines are equivalent, but the second is more idiomatic:
for (entry in subGraph!!) { }
subGraph?.forEach { }Replacing loops with recursion
There are two existing loops in the code:
one while loop and one for loop.
Let’s replace each of them with their Functional Programming equivalent - recursion.
A recursion is a function that calls itself.
The findShortestPath() implementation can be replaced with:
fun findShortestPath(start: String, end: String): Int {
recurseFindShortestPath(start, end)
return evaluatedPaths.getValue(end)
}The recurseFindShortestPath() function is recursive - as its name implies.
A recursive function offers different branches, the most important one being the stop branch.
In our case, the stop branch here is when the node has reached the end.
private fun recurseFindShortestPath(node: String, end: String): String {
return if (node == end) end
// else ...
}The other branch contains the same code as before, with one small change: we compute the next node by calling the same function with the updated node.
private fun recurseFindShortestPath(node: String, end: String): String {
return if (node == end) end
else {
// ... same code here
val nextNode = evaluatedPaths.minBy { it.value }?.key
?: throw RuntimeException("Map was empty")
recurseFindShortestPath(nextNode, end)
}
}The biggest issue with recursion is when calls pile upon one another on the stack.
Because it’s based on real-world hardware, the stack has a limit, however high it is.
When it’s reached, then the infamous StackOverflowError occurs.
To avoid that, the compiler can actually generate the equivalent non-recursive bytecode.
This requires:
- The function to be marked with
tailrec - The last instruction of the function should be the recursive call
Because our function conforms to the second condition, it’s a no-brainer to just add the tailrec keyword to it and optimize the generated bytecode.
Removing global state one step at a time
Replacing the state with parameters is a bit harder than replacing loops with recursion. Hence, we will do it step-by-step: the first step is to move the global state to local state, but keep it mutable for the time being.
This is the initial code:
class Graph(private val weightedPaths: Map<String, Map<String, Int>>) {
private val evaluatedPaths = mutableMapOf<String, Int>()
fun findShortestPath(start: String, end: String): Int {
recurseFindShortestPath(start, end)
return evaluatedPaths.getValue(end)
}
private tailrec fun recurseFindShortestPath(node: String, end: String): String {
// ...
recurseFindShortestPath(nextNode, end)
}
}After moving the state, the code becomes something like this:
class Graph(private val weightedPaths: Map<String, Map<String, Int>>) {
fun findShortestPath(start: String, end: String): Int {
val paths = mutableMapOf<String, Int>() (1)
recurseFindShortestPath(start, end, paths) (2)
return paths.getValue(end)
}
private tailrec fun recurseFindShortestPath(node: String, (2)
end: String,
paths: MutableMap<String, Int>): String {
// ...
recurseFindShortestPath(nextNode, end, paths) (2)
}
}| 1 | Move the mutable state inside the function |
| 2 | Change the function signature to accept the state and pass it at every call |
Add the state to the return value
Because we require immutable state, the next step is to also return the map along the existing return value.
class Graph(private val weightedPaths: Map<String, Map<String, Int>>) {
fun findShortestPath(start: String, end: String): Int {
val (_, paths) = recurseFindShortestPath(start, end, mutableMapOf()) (1)
return paths.getValue(end)
}
private tailrec fun recurseFindShortestPath(node: String,
end: String,
paths: MutableMap<String, Int>):
Pair<String, MutableMap<String, Int>> { (2)
return if (node == end) end to paths (3)
else {
// ...
recurseFindShortestPath(nextNode, end, paths) (4)
}
}
}| 1 | Assign the Map to a dedicated variable using Kotlin destructuring |
| 2 | Change the function signature to return the Map with the String, wrapping both into a Pair |
| 3 | Assemble the String with the Map to return both |
| 4 | Change the recursion call according to the new signature |
Restrict mutability
Before going further, we will extract a huge part of the recurseFindShortestPath() function into a dedicated function in order to keep mutability contained to a smaller scope:
class Graph(private val weightedPaths: Map<String, Map<String, Int>>) {
fun findShortestPath(start: String, end: String): Int { /* */ }
private tailrec fun recurseFindShortestPath(node: String,
end: String,
paths: MutableMap<String, Int>):
Pair<String, MutableMap<String, Int>> {
return if (node == end) end to paths
else {
val updatedPaths = updatePaths(node, paths)
val nextNode = updatedPaths.minBy { it.value }?.key
?: throw RuntimeException("Map was empty")
recurseFindShortestPath(nextNode, end, updatedPaths)
}
}
private fun updatePaths(node: String,
paths: MutableMap<String, Int>): MutableMap<String, Int> {
// ...
}
}At that point, we want to start migrating from mutable state to immutable state.
Let’s change the signature of the recurseFindShortestPath() function:
private tailrec fun recurseFindShortestPath(node: String,
end: String,
paths: Map<String, Int>):
Pair<String, Map<String, Int>> { (1)
return if (node == end) end to paths
else {
val updatedPaths = updatePaths(node, paths.toMutableMap()) (2)
val nextNode = updatedPaths.minBy { it.value }?.key
?: throw RuntimeException("Map was empty")
recurseFindShortestPath(nextNode, end, updatedPaths) (3)
}
}| 1 | Change the signature to use an immutable type instead of a mutable type i.e. from MutableMap to Map |
| 2 | Pass a mutable type because the called function requires it |
| 3 | No change in the function call |
The next step is to change the signature of the called function in the same way. To keep the change small, we will keep using mutable state inside the function itself:
private fun updatePaths(node: String,
paths: Map<String, Int>): Map<String, Int> { (1)
var updatedPaths = paths (2)
weightedPaths[node]?.forEach {
val currentDistance = paths.getOrDefault(it.key, Integer.MAX_VALUE)
val newDistance = it.value + paths.getOrDefault(node, 0)
if (newDistance < currentDistance)
updatedPaths = updatedPaths + (it.key to newDistance) (3)
}
return updatedPaths - node (4)
}| 1 | Only use immutable types in the function’s signature |
| 2 | Assign the Map to a var, so it can be reassigned |
| 3 | Create a new Map by adding a Pair instance to an existing Map, and reassign the var |
| 4 | Create a new Map by removing the entry whose key is node from the Map i.e. remove the current node from the paths so it’s not evaluated again |
At this point, it’s possible to extract the update of a single path into its own function. That will be help us to remove every trace of mutability:
private fun updatePaths(node: String, paths: Map<String, Int>): Map<String, Int> {
var updatedPaths = paths
weightedPaths[node]?.forEach {
updatedPaths = updatedPaths + updatePath(paths, it, node)
}
return updatedPaths - node
}The extracted function has no mutable state at all, and uses only immutable types:
private fun updatePath(paths: Map<String, Int>,
entry: Map.Entry<String, Int>,
node: String): Map<String, Int> { (1)
val currentDistance = paths.getOrDefault(entry.key, Integer.MAX_VALUE)
val newDistance = entry.value + paths.getOrDefault(node, 0)
return if (newDistance < currentDistance)
paths + (entry.key to newDistance) (2)
else
paths (2)
}| 1 | The function’s signature only uses immutable types |
| 2 | Because maps are immutable, they can be composed using the + operator.
This returns a new map instance, which entries are the entries of both composed maps |
The final step is to remove mutability from the implementation of updatePaths() now that it’s become easier to understand.
For that, the forEach() that works on mutable state can be migrated to a sequence of transformations:
private fun updatePaths(node: String, paths: Map<String, Int>) =
(weightedPaths[node]
?.map { updatePath(paths, it, node) } (1)
?.fold(emptyMap()) { acc, item -> acc + item } (2)
?: emptyMap<String, Int>()) (3)
- node| 1 | The first transform is to map the Map item to another Map item using the updatePath() function |
| 2 | Collect all Map entries into a single Map |
| 3 | Return an empty Map if weightedPaths[node] is null.
That makes the type of the evaluated expression a non-nullable Map, which can then be composed.
Otherwise, we wouldn’t be able to compile the next line as - cannot be called on a nullable type |
At that point, the source code has all features of Functional Programming: immutability and recursion.
Conclusion
Migrating from imperative to functional is mainly based on:
- replacing loops by recursion
- moving mutable state to accumulator parameters and return values
Baby steps help a lot when one is not used to Functional Programming.