Список фильтров в стиле функционального программирования

Question

У нас есть список строк с метками BEGIN и END как части этого списка.Можем ли мы отфильтровать элементы между BEGIN-END в стиле функционального программирования?Я вышел только с этим обычным (flag) подходом в scala.

val list1 =
  """992
  1010
  1005
  1112
  BEGIN
  1086
  1244
  1107
  1121
  END
  1223
  1312
  1319
  1306
  1469""".lines.toList

var flag = false
val filteredList = list1.filter{
  def f(x: String): Boolean = {
    if (x.contains("BEGIN")) {
      flag = true;
      return false
    } else if (x.contains("END")) {
      flag = false
    }
    flag
  }
  f
}

Можно ли избежать определения переменной flag?Как они решают это на чисто функциональных языках?

Answer 1

Вы можете использовать функции drop / tail, dropWhile, takeWhile:

val filteredList = list1.map(_.trim).dropWhile("BEGIN" !=).tail.takeWhile("END" !=)

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

Как уже упоминалось в комментариях tail вызовет исключение, еслисписок пуст, поэтому, если вы предпочитаете оставаться в безопасности, используйте drop(1) вместо tail:

val filteredList = list1.map(_.trim).dropWhile("BEGIN" !=).drop(1).takeWhile("END" !=)

А вот моя версия алгоритма, которая обрабатывает несколько BEGIN и END разделы (некоторые сумасшедшие вещи от меня - маленький конечный автомат :)

var filteredList1 = list1.map(_.trim).foldLeft(List(None): List[Option[List[String]]]) {
  case (None :: rest, "BEGIN") => Some(Nil) :: rest
  case (Some(list) :: rest, "END") => None :: Some(list) :: rest
  case (Some(current) :: rest, num) => Some(num :: current) :: rest
  case (result, _) => result
}.flatten.reverse map (_.reverse)

возвращает List[List[String]]

Answer 2

Для начала каждая строка в вашем списке содержит пробелы от начала строки.

Это самая большая проблема в вашем коде, и есть два способа ее исправить.

Либо обрезать линии ...

val list1 =
  """992
  1010
  ...
  1306
  1469""".lines.map(_.trim).toList

... или перед каждой строкой можно указать | и использовать stripMargin.

Тогда это всего лишь маленький вопрос применения takeWhile / dropWhile

list1.takeWhile("BEGIN" !=) ++ list1.dropWhile("END"!=).tail

или более эффективно:

val (begin,middle) = list1.span("BEGIN" !=)
val end = middle.dropWhile("END" !=).tail
begin ++ end

EDIT

У меня было решение задом наперед, которое отбросило бы (отфильтровало) значения между BEGIN и END. Чтобы сохранить их:

list1.dropWhile("BEGIN" !=).tail.takeWhile("END"!=)

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

Принимая вызов здесь ... Я учту несколько блоков BEGIN / END, но также учту, что входные данные могут быть неправильно искажены. Что если бы было НАЧАЛО без соответствующего КОНЦА? Возможно, в строке два BEGIN, или список заканчивается до того, как закончится END.

Определение некоторых правил:

• КОНЕЦ без соответствующего НАЧАЛА игнорируется
• блоки BEGIN / END не вкладываются
• НАЧАЛО, обнаруженное, когда уже в блоке начинается новый блок
• Если список заканчивается в блоке, подразумевается неявный END

Без лишних слов сначала создайте итератор, который идентифицирует каждый "BEGIN" во входных данных:

val blocksStarts =
  Iterator.iterate(list1)(_.dropWhile("BEGIN" !=).drop(1)).drop(1).takeWhile(Nil !=)

//This iterator tries to continue forever,
//returning Nils once the sequences are exhausted
//For this reason, we must use drop(1) instead of tail

Предоставление итератора списков, каждый из которых начинается с "BEGIN"

Чтобы затем брать элементы из каждого из этих списков, пока не будет достигнут соответствующий "END", или другой "BEGIN", или список не будет исчерпан:

val blocks = blockStarts map {
  _.takeWhile(x => x != "BEGIN" && x != "END")
} toList

Финал toList - потому что на тот момент он все еще равен Iterator. Теперь у вас есть список списков, каждый из которых соответствует партии элементов в блоке, как определено в предыдущих правилах.

Answer 3

Я немного расширяю ответы других, чтобы представить случай, когда в списке два блока BEGIN ... END.

val list1 =
  """992
  1010
  1005
  1112
  BEGIN
  1086
  1244
  1107
  1121
  END
  1223
  1312
  BEGIN
  773
  990
  224
  END
  1319
  1306
  1469""".lines.map(_.trim).toList

Мы собираемся использовать foldRight передать аккумулятор состояния между итерациями.Обратите внимание, что мы используем foldRight, чтобы сделать построение списка результатов эффективным, поэтому мы встретимся с END, прежде чем встретим BEGIN.

case class StripStatus(list:List[String], retaincurrent:Boolean)

list1.foldRight(StripStatus(Nil,false)){ (curElem:String, curStatus:StripStatus) =>
   if (curElem == "END")
      StripStatus(curStatus.list,true)
   else if (curElem == "BEGIN")
      StripStatus(curStatus.list,false)
   else if (curStatus.retaincurrent)
      StripStatus(curElem::curStatus.list, true)
   else
      curStatus
}.list

Мы могли бы так же легко использовать foldLeft и reverse список результатов в конце:

list1.foldLeft(StripStatus(Nil,false)){ (curStatus:StripStatus, curElem:String) =>
   if (curElem == "BEGIN")
      StripStatus(curStatus.list,true)
   else if (curElem == "END")
      StripStatus(curStatus.list,false)
   else if (curStatus.retaincurrent)
      StripStatus(curElem::curStatus.list, true)
   else
      curStatus
}.list.reverse

Answer 4

мммм.Вот мой дубль:

def getInside(l: List[String]) = {
    def concat(in: List[String], out: List[String]): List[String] = in ::: off(out)

    def off(l: List[String]): List[String] = 
        if (l.isEmpty) Nil 
        else on(l dropWhile ("BEGIN" !=) drop 1)

    def on(l: List[String]): List[String] = 
        if (l.isEmpty) Nil
        else (concat _).tupled(l span ("END" !=))

    off(l)
}

Answer 5

Опять же, с той же целью иметь дело с несколькими BEGIN ... END диапазонами в списке.

def getBetweenBeginEnd(l:List[String]) = {
   def internal(l:List[String],accum:List[String]):List[String]={
      val (keep, keepChecking) = l.dropWhile("BEGIN" !=).drop(1).span("END" !=)
      if (keepChecking == Nil)
         accum:::keep
      else
         internal(keepChecking.tail,accum:::keep)
   }
   internal(l,Nil)
}

Answer 6

Я не знаю Scala, но вы можете определить функцию, которая возвращает индекс в списке следующего элемента, который соответствует подстроке, и возвращает индекс, где была найдена подстрока, а также список элементов, встречавшихся до тех пор. подстрока была найдена. Заголовок псевдокода: findSubstr(list, startIndex). Затем создайте выражение (более псевдокод):

beginIndex, preBeginElems = findSubstr(list, 0)
endIndex, inBetweenElems = findSubstr(list, beginIndex)
restElems = list[endIndex until the end]

Если полезно, я мог бы написать это на Хаскеле ...:)

РЕДАКТИРОВАТЬ: Возможно, есть и другие способы сделать это тоже