Define 2d array functionally

Question
1

What is the correct way to define a multi-dimensional (2d in my case) functionally?
I have a class with a class parameter T, and an object, which I’m calling adjacencyMatrix which is a mapping from pair of integer to integer. Isn’t there an easier, more functional, way to declare adjacencyMatrix than to construct loops and destructively append to the map N^2 times?

I basically want give a function (Int,Int)=>Int to the Map constructor. And have the values calculated lazily but only once.

Also, I have defined a class called UnorderedPair. I’ve defined a type named Edge to that class, but then I don’t get a constructor named Edge. I’d like to use

val edge = Edge(vertices(i),vertices(j))

but that doesn’t work. I have to use

val edge:Edge = UnorderedPair(vertices(i),vertices(j))

I’m happy to have advise about how to do this properly.

  case class UnorderedPair[A](a: A, b: A) {
    // https://gist.github.com/dmyersturnbull/2295d91ef503bb3eec6d
    override def equals(o: Any) = o match {
      case that: UnorderedPair[A] => that.a == a && that.b == b || that.a == b && that.b == a
      case _ => false
    }
    override def hashCode = a.hashCode * b.hashCode // commutative and unique
  }

  abstract class Graph[T]() {
    type Edge = UnorderedPair[T]
    def V:Set[T] // set of vertices
    def E:Set[Edge] // set of edges

    // the adjacencyMatrix construction needs a vertices vector because
    // although Graph.V is an ordered set of vertices, an adjacency matrix is
    // constructed given a fixed order for the vertices.
    def adjacencyMatrix (vertices:Vector[T]): Map[(Int,Int),Int] = {
      var arr = null /*new Map[(Int,Int),Int] */
      for ( i <- 0 until V.size){
        for ( j <- 0 until V.size){
          // I'd like to say
          //    val edge = Edge(vertices(i),vertices(j))
          // but that doesn't work
          val edge:Edge = UnorderedPair(vertices(i),vertices(j))
          arr += ((i,j) -> (if ( E.contains( edge )) 1 else 0))
        }
      }
      arr
    }
  }
2

At least for Scala 2.x I think that you are stuck with the UnorderedPair constructor unless you wrap another type. It is possible that the opaque types in Scala 3 will solve that. Hopefully someone who is more up on the changes will answer as well.

As for the more function approach, I can think of several. Here is one that follows your pattern.

(for (i <- 0 until V.size; j <- 0 until V.size) yield {
  (i, j) -> (if (E.contains(UnorderedPair(vertices(i), vertices(j))) 1 else 0)
}).toMap

Note that I haven’t tried compiling this, so there may be typos, but hopefully the idea is clear.

1 Like
3

That is because in the line type Edge = UnorderedPair[T], you declare the type Edge to be UnorderedPair[T]. However, in Edge(vertices(1), vertices(j)), you are not using the type Edge, but a function called Edge.

What UnorderedPair(...) effectively does is: UnorderedPair.apply(...). This is not the type, but the companion object of the case class, and on that you call the method apply.

You can resolve that without further changes by adding a method like this

def Edge(v1: T, v2: T): Edge

, but I’d suggest renaming it to something like createEdge or similar. Then you create Edges from inside Graph[T] only via this method.

4

if you also val Edge = UnorderedPair, then you can val edge = Edge(...)

1 Like