Создать функцию для группировки последовательности в точках останова

Question

Я пытаюсь создать функцию, которая берет две последовательности и группирует элементы сначала на основе «точек останова», включенных во вторую. Пример:

val ls = ('a' to 'z').map(_.toString)
// IndexedSeq[String] = Vector(a, b, c, d, e, f, g, h, i, j, k, l, m, ...)

val breakpoints = Seq("c", "f", "j")

grouper(ls, breakpoints)
// Seq(Seq("a", "b"), Seq("c", "d", "e"), Seq("f", "g", "h", "i"), Seq("j", ...))

Я пытался сделать это с помощью рекурсивных вызовов takeWhile и dropWhile (как я мог бы в языке, подобном Haskell), но поскольку моя текущая функция не используетХвостовая рекурсия, я получаю java.lang.StackOverflowError. Вот функция:

def grouper(strings: Seq[String], breaks: Seq[String]): Seq[Seq[String]] = strings match {
  case Nil => Seq()
  case s => s.takeWhile(breaks.contains(_)) +: grouper(s.dropWhile(breaks.contains(_)), breaks)
}

Есть ли лучший способ приблизиться к этому?

Answer 1

Для такого рода проблем я всегда предпочитаю написать собственную хвостовую рекурсивную функцию, работающую o Списки .

import Ordering.Implicits._

def group[A : Ordering](data: List[A], breakPoints: List[A]): List[List[A]] = {
  def takeUntil(list: List[A], breakPoint: A): (List[A], List[A]) = {
    @annotation.tailrec
    def loop(remaining: List[A], acc: List[A]): (List[A], List[A]) =
      remaining match {
        case x :: xs if (x < breakPoint) =>
          loop(remaining = xs, x :: acc)

        case _ =>
          (acc.reverse, remaining)
      }

    loop(remaining = list, acc = List.empty)
  }

  @annotation.tailrec
  def loop(remainingElements: List[A], remainingBreakPoints: List[A], acc: List[List[A]]): List[List[A]] =
    remainingBreakPoints match {
      case breakPoint :: remainingBreakPoints =>
        val (group, remaining) = takeUntil(remainingElements, breakPoint)
          loop(
            remainingElements = remaining,
            remainingBreakPoints,
            group :: acc
          )

      case Nil =>
        (remainingElements :: acc).reverse
    }

  loop(
    remainingElements = data.sorted,
    remainingBreakPoints = breakPoints.sorted,
    acc = List.empty
  )
}

Вы можете использовать еенапример:

group(data = ('a' to 'z').toList, breakPoints = List('c', 'f', 'j')) 
//res: List[List[Char]] = List(
//  List('a', 'b'),
//  List('c', 'd', 'e'),
//  List('f', 'g', 'h', 'i'),
//  List('j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z')
// )

Эта функция всегда генерирует список length = length(breakPoints) + 1.
Если элементов больше нет, генерируются пустые списки.
(вы можете редактироватькод для ваших конкретных требований)

Answer 2

Вы можете попробовать немного другой подход:

 def grouper(strings: Seq[String], breaks: Seq[String]): Seq[Seq[String]] =  {
    var i = 0
    (for(x <- strings) yield {if (breaks.contains(x)) {i=i+1}; (x,i)})
      .groupBy(_._2).map(_._2.map(_._1)).toList
  }

 grouper(ls,breakpoints).foreach(println(_))


Vector(f, g, h, i)
Vector(c, d, e)
Vector(j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z)
Vector(a, b)

Answer 3

Вы на правильном пути. takeWhile и dropWhile можно заменить на span.

def grouper(xs: Seq[String], breaks: Seq[String]): Seq[Seq[String]] = breaks match{
 case Nil => Seq(xs)
 case h::t => {
   val split = xs.span(x => x != h); 
   split._1 +: grouper(split._2, t);
 }
}

scala> grouper(ls, breakpoints)
res5: Seq[Seq[String]] = List(Vector(a, b), Vector(c, d, e), Vector(f, g, h, i),
  Vector(j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z))

Из API на span: Примечание: c span p эквивалентен (но, возможно, более эффективен, чем)(c takeWhile p, c dropWhile p), при условии, что оценка предиката p не вызывает никаких побочных эффектов.