Как преобразовать императивный двойной цикл for в функциональный стиль без возврата в Scala?

У меня есть следующий код Scala, императивный стиль, и мне было интересно, есть ли эквивалент в функциональном стиле, избегающий использования return:

def function(c: Char, vector: Vector[Vector[Char]]): (x:Int , y:Int) = {
  for (x <- vector.indices)
    for (y <- vector(x).indices)
      if (vector(x)(y) == c)
        return (x, y)
  throw new NoSuchElementException
}

Мне интересно, есть ли альтернатива, столь же эффективная, как эта, без использования return.


for-loop scala functional-programming imperative-programming
person bquenin    schedule 02.11.2014    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Начнем со следующей наивной реализации:

def function(c: Char, levelVector: Vector[Vector[Char]]): Option[(Int, Int)] = (
  for {
    (row, x) <- levelVector.zipWithIndex
    (cell, y) <- row.zipWithIndex
    if cell == c
  } yield (x, y)
).headOption

(Обратите внимание, что я возвращаю значение в Option вместо того, чтобы генерировать исключение в случае отсутствия совпадения, но вы можете добавить .getOrElse(throw new NoSuchElementException), если хотите исходное поведение.)

Эта реализация, скорее всего, подойдет во многих сценариях, но она несколько расточительна, поскольку создает много промежуточных коллекций и проверяет каждый элемент даже после того, как находит совпадение. (Стоит отметить, что ваша императивная реализация также создает промежуточные коллекции, но это всего лишь диапазоны, и это не так плохо, как эта наивная функциональная реализация.)

Следующая версия, вероятно, будет более эффективной, но по-прежнему избегает return:

def function(c: Char, levelVector: Vector[Vector[Char]]): Option[(Int, Int)] =
  levelVector.view.zipWithIndex.map {
    case (row, x) => (x, row.indexOf(c))
  }.collectFirst {
    case (x, y) if y >= 0 => (x, y)
  }

Здесь мы используем view, чтобы избежать создания множества промежуточных коллекций, и collectFirst, чтобы прекратить проверку после того, как мы найдем совпадение.

Если вы знаете, что производительность этого метода действительно важна (вероятно, нет), вам все равно следует избегать return (что включает в себя создание исключения в реализации Scala) и вместо этого использовать var и while. Это довольно разумная вещь для чего-то такого простого — просто убедитесь, что вы обернули все изменяемое состояние внутри метода.

Следующим шагом в более функциональном направлении будет попытка вообще избежать использования индексов — очень часто можно переформулировать проблему таким образом, что они вам не нужны, и, сделав это, часто делает вашу программу более элегантной (если не более производительной).

person Travis Brown    schedule 02.11.2014
comment
Спасибо, я не знал о collectFirst и это то, что я искал - person bquenin; 03.11.2014