Scala List vs ListBuffer

Question

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

@BrianKent Could you give an example comment or answer of doing this using `fold`? Thanks! — vsnyc, Sep 21 '15 at 19:49
@Brian I have added the definition of `Edge` class, I had deliberately omitted the type parameter in the question — vsnyc, Sep 21 '15 at 20:39

score 2 · Accepted Answer · answered Sep 21 '15 at 21:21

2

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)

answered Sep 21 '15 at 21:21

Aivean

10,692
25
39

Thanks! I think the for-comprehension version is very clear on it's intent (although it might be just syntactic sugar defined over higher order functions) – vsnyc Sep 21 '15 at 21:40

Brian · Answer 2 · 2015-09-21T19:50:05.740

1

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]()

edited Sep 21 '15 at 19:50

answered Sep 21 '15 at 19:08

Brian

20,195
6
34
55

and map and flatten becomes flatMap :) Or it is possible to use for comprehensive: for { r <- row if (r != -1) } yield ... – al32 Sep 21 '15 at 19:21
Awesome, this works. I converted it to flatMap: `val ret = row.indices.flatMap(j => if (row(j) != -1) Some(Edge(STATES(currState), STATES(j), row(j))) else None)` – vsnyc Sep 21 '15 at 19:23
@al32 How can we use for-comprehension, I need the index of current column `r` in your example. That is a reason why I do a `foreach` on `row.indices`, else I could have iterated directly over `row` – vsnyc Sep 21 '15 at 19:31
@Brian there is a typo in your answer, could you change it so I can accept the answer `j => if(row(j) != 1` should be `j => if(row(j) != -1` – vsnyc Sep 21 '15 at 19:47
@vsync You can try to use zipWithIndex – al32 Sep 21 '15 at 19:50
How will using `zipWithIndex` enable using `for-comprehension`? Using `zipWithIndex` and `indices` is almost equivalent. See [this answer](http://stackoverflow.com/questions/6821194/get-index-of-current-element-in-a-foreach-method-of-traversable). `indices` is a bit more concise as I do not need the tuple – vsnyc Sep 21 '15 at 19:58
case class SomeY(someVal: Int) case class SomeX(someVal: Int, someY: SomeY) def zipWithIndexInFor: List[SomeX] = { val row = Array(1,2,3,4,5,6,7).toList.zipWithIndex for { (r, i) <- row if (r != -1) } yield SomeX(r, SomeY(i)) } – al32 Sep 21 '15 at 20:08

score 1 · Answer 3 · answered Sep 21 '15 at 20:05

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
      }
  })
}

score 1 · Answer 4 · edited May 23 '17 at 12:16

1

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)
}

edited May 23 '17 at 12:16

Community

1
1

answered Oct 02 '15 at 20:36

vsnyc

2,117
22
35

Scala List vs ListBuffer

4 Answers4