The background of the question might be interesting. My students have just finished a course in Graph Theory where they implemented several graph algorithms in Python. Now some are taking Scala as an elective. For lecture #1, I’m trying to reuse some of the same algorithms that they have fresh in memory and show how to do it in Scala. I’d love it if some of the algorithms appear simpler in Scala.
The problem at hand is given a graph in the form of a collection of edges (where collection may be array, set, or list) generate the adjacency list which is not a List, but rather a mapping vertex vertex to collection of neighboring vertices. In the lecture I go through about 10 different ways to implement this function in Scala, using Array, Set, and Map, all using immutable data structures.
Here are the different approaches I show them, using pattern matching, recursion, foldLeft, pre-initialized Map/Array, uninitialized Map/Array, Array.tabulate, and several other techniques.
I personally think the examples are good because they give examples to the students of how to use the basic data structures on algorithms they already know.
As a “look this is a language and you can do the same as other languages” perspective yapp. But in that case these can be your “base” cases from where you can factor out the impurity as you introduce the new concepts in later lectures. (But still I would mention that these codes are “translations” from python, and not “the scala/FP way” in some cases. Maybe you can mention some problems along the way as “teasers” (like you draw the curve between the first and second function (personally I like Nil or List.empty[A] better than List())). Also in this case I would not really take much effort to ~any error or corner case handling, I would just give it as a “homework” to find where the code is not working properly )
Btw I would love a cats like “last” example with:
//build on top of makeAdj_12 with SemiGroups and cats
def makeAdj_14[V](edges: Seq[(V, V)]): Map[V, Set[V]] = {
import cats.implicits._
edges
.map{case (f, s) => Map(f -> Set(s), s -> Set(f))} //Seq[Map[V, Set(V)]]
.reduceOption(_ |+| _) //Option[Map[V, Set(V)]]
.getOrElse(Map.empty[V, Set[V]])
}
An interesting solution. Do I really need cats for that?
If I convert each edge (src -> dst) to a Map[V,Set[V]] can I then flatMap the Maps together in a way which unions the sets when the keys are the same?
I didn’t talk about map and flatMap in lecture #1, although that might be a good example for lecture #2 or #3 when I talk about flatMap.
A bit off from the original question, but you can’t just flatmap that as easily bcs Map will override by keys and not aggregate. The combine (|+|) is aggregating on maps second type if the second type can be combined (and the code will fail to compile if not).
The catsless method would something like:
edges
.flatMap{case (f, s) => Seq(f -> s, s -> f)} //"duplicate" to both dirs
.groupBy(_._1) //Map[V, Seq[V]]
.map{case (k, v) => k -> v.map(_._2).toSet}
But I hate the last line I think this is by far the cleanest with pure scala, but also I think this is the slowest (in general, no idea building an immutable map step-by-step is how resource hungry, but I hope the groupBy using a mutable map building which can be gamechanger in practice…). You can notice that this method works with empty lists without ever mentioning the empty result anywhere
)
I think this is by far the cleanest with pure scala, but also I think this is the slowest (in general, no idea building an immutable map step-by-step is how resource hungry, but I hope the groupBy using a mutable map building which can be gamechanger in practice…). You can notice that this method works with empty lists without ever mentioning the empty result anywhere 