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
– vsnyc, Commented Sep 21, 2015 at 19:49
@Brian I have added the definition of Edge class, I had deliberately omitted the type parameter in the question — vsnyc
– vsnyc, Commented Sep 21, 2015 at 20:39

Aivean · Accepted Answer · 2015-09-21 21:21:34Z

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, 2015 at 21:21

Aivean

10.9k28 silver badges40 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

vsnyc Over a year ago

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)

Brian · Accepted Answer · 2015-09-21 19:50:05Z

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, 2015 at 19:50

answered Sep 21, 2015 at 19:08

Brian

20.3k6 gold badges36 silver badges55 bronze badges

7 Comments

al32 Over a year ago

and map and flatten becomes flatMap :) Or it is possible to use for comprehensive: for { r <- row if (r != -1) } yield ...

vsnyc Over a year ago

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 Over a year ago

@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 Over a year ago

@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

al32 Over a year ago

@vsync You can try to use zipWithIndex

|

Brian Kent · Accepted Answer · 2015-09-21 20:05:05Z

1

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

answered Sep 21, 2015 at 20:05

Brian Kent

3,8641 gold badge29 silver badges32 bronze badges

Comments

Community · Accepted Answer · 2017-05-23 12:16:18Z

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, 2017 at 12:16

CommunityBot

11 silver badge

answered Oct 2, 2015 at 20:36

vsnyc

2,25725 silver badges39 bronze badges

Collectives™ on Stack Overflow

Scala List vs ListBuffer

4 Answers 4

1 Comment

7 Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

1 Comment

7 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related