CODEWITHSUNDEEP
scala
vsnyc
vsnyc

Reputation: 2257

Scala List vs ListBuffer

I am modeling a DFA in Scala. I have a transition matrix which is a directed acyclic graph represented as 2-D matrix (more accurately, array or arrays). I have implemented a method getNextTransitions which will give me the possible next states based on the current state I am in. Consider the two implementations below which give correct output but differ in data structure used.

Using ListBuffer:

def getNextTransitions(currState: Int): List[Edge] = {
  val ret: ListBuffer[Edge] = ListBuffer[Edge]()
  val row: Array[Int] = transitionDAG(currState) //row is a 1-d array
  row.indices.foreach(j => {
    if (row(j) != -1) {
      ret += Edge(STATES(currState), STATES(j), row(j))
    }
  })
  ret.toList
}

Using List:

def getNextTransitions1(currState: Int): List[Edge] = {
  var ret: List[Edge] = List[Edge]()
  val row: Array[Int] = transitionDAG(currState) //row is a 1-d array
  row.indices.foreach(j => {
    if (row(j) != -1) {
      ret = Edge(STATES(currState), STATES(j), row(j)) :: ret
    }
  })
  ret
}

Scala encourages using immutable data structures, but I can't find a way of replacing var ret: List[Edge] with val ret: List[Edge] in getTransitions1 method above. Any suggestions?

Also, should I even try to force myself thinking in an alternative way when the getTransitions method using ListBuffer already does its job?

Adding definition of State and Edge classes. For the sake of simplicity, type parameters are removed in the question. So Edge class can be assumed to be case class Edge (start: State, end: State, edgeVal:Any)

State class: 

case class State[+T](stateVal: T) {
  override def toString: String = {
    stateVal.toString
  }
}

Edge class:

case class Edge[E](start: State[Any], end: State[Any], edgeVal: E) {
  override def toString: String = {
    start + " --" + edgeVal + "--> " + end
  }
}

Upvotes: 1

Views: 1233

Answers (4)

vsnyc
vsnyc

Reputation: 2257

I came up with yet another variant similar to Aivean's answer which uses the collect method on Scala collections

transitionDAG(currState).zip(STATES) collect {
  case (row, endState) if (endState != -1) => Edge(STATES(currState), endState, row)
}

Upvotes: 1

Aivean
Aivean

Reputation: 10882

I'm not sure that you need indices (and hence zipWithIndex) at all:

transitionDAG(currState).zip(STATES).filter(_._1 != -1).map {
  case (row, endState) => Edge(STATES(currState), endState, row)
}

Just zip rows with states and filter them.

Same thing using for-comprehension:

for ((row, endState) <-  transitionDAG(currState).zip(STATES) if row != -1)
  yield Edge(STATES(currState), endState, row)

Upvotes: 2

Brian Kent
Brian Kent

Reputation: 3854

You might try using a fold:

def getNextTransitions1(currState: Int): List[Edge] = {
  transitionDAG(currState).zipWithIndex.foldLeft(List[Edge]())({
    case (ret, (row, j)) =>
      if (row != -1) {
        Edge(STATES(currState), STATES(j), row) :: ret
      } else {
        ret
      }
  })
}

Upvotes: 1

Brian
Brian

Reputation: 20285

The foreach in this is filtering for indices where row(j) != -1 and returning a new Edge class if so. To mimic this filter and then map behavior here is an approach to filter using the same condition and wrap the result in a Some class. If the condition is not met, the result is None. Using this we get a List[Option[Edge]]. flatten is then used to get results for those cases that have a value.

row.indices.foreach...

becomes

row.indices.map(j => if(row(j) != -1) Some(Edge(STATES(currState), STATES(j), row(j))) else None).flatten

This returns a new collection and the last value of the method is returned in Scala. No need to even declare var ret: List[Edge] = List[Edge]()

Upvotes: 1

Related Questions