Проблемы с картами и их записями в Scala

Question

У меня есть рекурсивная функция, которая принимает Map в качестве единственного параметра. Затем он добавляет новые записи в эту карту и вызывает себя с этой большей картой. Пожалуйста, игнорируйте возвращаемые значения на данный момент. Функция еще не закончена. Вот код:

def breadthFirstHelper( found: Map[AIS_State,(Option[AIS_State], Int)] ): List[AIS_State] = {
  val extension =
   for( 
     (s, v) <- found; 
     next <- this.expand(s) if (! (found contains next) )
   ) yield (next -> (Some(s), 0))

  if ( extension.exists( (s -> (p,c)) => this.isGoal( s ) ) )
    List(this.getStart)
  else
    breadthFirstHelper( found ++ extension )
}

В расширение - новые записи, которые должны быть добавлены на карту. Обратите внимание, что оператор for генерирует итерацию, а не карту. Но эти записи позже будут добавлены к исходной карте для рекурсивного вызова. В состоянии разрыва мне нужно проверить, было ли определенное значение сгенерировано внутри extension . Я пытаюсь сделать это, используя метод существующие на расширение . Но синтаксис для извлечения значений из записей карты (материал, следующий за выходом) не работает.

Вопросы:

1. Как заставить работать мое условие разрыва (логическое выражение для if)?

2. Является ли хорошей идеей сделать рекурсивную работу на неизменяемой карте, подобной этой? Это хороший функциональный стиль?

Answer 1

При использовании сопоставления с образцом (например, против Tuple2) в функции необходимо использовать фигурные скобки {} и оператор case.

if (extension.exists { case (s,_) => isGoal(s) } )

Выше также используется тот факт, что при сопоставлении более понятно использовать подстановочный знак _ для любого допустимого значения (которое впоследствии вас не интересует). case xyz компилируется в PartialFunction, который, в свою очередь, простирается от Function1 и, следовательно, может использоваться в качестве аргумента для метода exists.

Что касается стиля, я не являюсь экспертом по функциональному программированию, но похоже, что он будет скомпилирован в итеративную форму (т. Е. С хвостовой рекурсией) с помощью scalac . Нет ничего, что говорит "рекурсия с Картами плоха" так почему бы и нет?

Обратите внимание , что -> - это метод для Any (посредством неявного преобразования), который создает Tuple2 - это , а не класс падежа , такой как :: или ! и, следовательно, не может использоваться в операторе сопоставления с шаблоном case. Это потому что:

val l: List[String] = Nil
l match {
  case x :: xs =>
}

Это действительно сокращение / сахар для

case ::(x, xs) =>

Аналогично a ! b эквивалентно !(a, b). Конечно, вы, возможно, написали свой собственный класс дела -> ...

Примечание2 : как говорит Даниэль ниже, вы ни в коем случае не можете использовать сопоставление с образцом в определении функции; таким образом, хотя вышеуказанная частичная функция действительна, следующая функция не является:

(x :: xs) =>

Answer 2

Это немного запутанно для меня, чтобы следовать, что бы ни думали Oxbow Lakes.

Прежде всего, я бы хотел уточнить один момент: нет условий перерывов в понимании. Они не являются циклами, такими как C (или Java) for.

Что означает if для понимания, это охранник. Например, скажем, я делаю это:

for {i <- 1 to 10
     j <- 1 to 10
     if i != j
} yield (i, j)

Цикл не "останавливается", когда условие ложно. Он просто пропускает итераций, для которых это условие ложно, и переходит к истинным. Вот еще один пример:

for {i <- 1 to 10
     j <- 1 to 10
     if i % 2 != 0
} yield (i, j)

Вы сказали, что у вас нет побочных эффектов, поэтому я могу пропустить целую главу о побочных эффектах и ​​мерах предосторожности для понимания. С другой стороны, чтение сообщения в блоге, которое я недавно написал на Strict Ranges - неплохая идея.

Так что ... сдавайся на перерывах. Их можно заставить работать, но они не работают. Попробуйте перефразировать проблему более функциональным способом, и необходимость условия прерывания будет заменена чем-то другим.

Далее, Oxbow верен в том, что (s -> (p,c) => не разрешен, потому что не определен экстрактор для объекта с именем ->, но, увы, даже (a :: b) => не будет разрешен, потому что нет сопоставления с образцом происходит в функциональном объявлении литерального параметра. Вы должны просто указать параметры в левой части =>, не выполняя разложения. Вы можете, однако, сделать это:

if ( extension.exists( t => val (s, (p,c)) = t; this.isGoal( s ) ) )

Обратите внимание, что я заменил -> на ,. Это работает, потому что a -> b является синтаксическим сахаром для (a, b), который сам по себе является синтаксическим сахаром для Tuple2(a, b). Поскольку вы не используете ни p, ни c, это тоже работает:

if ( extension.exists( t => val (s, _) = t; this.isGoal( s ) ) )

Наконец, ваш рекурсивный код в порядке, хотя, вероятно, не оптимизирован для хвостовой рекурсии. Для этого вы либо делаете свой метод final, либо делаете рекурсивную функцию приватной для метода. Как это:

final def breadthFirstHelper

или

def breadthFirstHelper(...) {
  def myRecursiveBreadthFirstHelper(...) { ... }
  myRecursiveBreadthFirstHelper(...)
}

В Scala 2.8 есть аннотация под названием @TailRec, которая сообщит вам, можно ли сделать функцию хвостовой рекурсивной или нет. И, на самом деле, кажется, будет флаг для отображения предупреждений о функциях, которые могут сделать хвосто-рекурсивными, если их немного изменить, например, как указано выше.

EDIT

Относительно решения Oxbow, использующего case, это литерал функции или частичной функции. Его тип будет зависеть от того, что требует логический вывод. В этом случае, потому что это то, что exists принимает, функцию. Однако нужно быть внимательным, чтобы всегда было совпадение, иначе вы получите исключение. Например:

scala> List(1, 'c') exists { case _: Int => true }
res0: Boolean = true

scala> List(1, 'c') exists { case _: String => true }
scala.MatchError: 1
        at $anonfun$1.apply(<console>:5)
        ... (stack trace elided)    

scala> List(1, 'c') exists { case _: String => true; case _ => false }
res3: Boolean = false

scala> ({ case _: Int => true } : PartialFunction[AnyRef,Boolean])
res5: PartialFunction[AnyRef,Boolean] = <function1>

scala> ({ case _: Int => true } : Function1[Int, Boolean])
res6: (Int) => Boolean = <function1>

РЕДАКТИРОВАТЬ 2

Решение, предлагаемое Oxbow, использует сопоставление с образцом, потому что оно основано на функциональных литералах, использующих операторы case, которые используют сопоставление с образцом. Когда я сказал, что это невозможно, я говорил о синтаксисе x => s.