Функция Scala List для группировки последовательных идентичных элементов

Question

Учитывая, например:

List(5, 2, 3, 3, 3, 5, 5, 3, 3, 2, 2, 2)

Я хотел бы получить:

List(List(5), List(2), List(3, 3, 3), List(5, 5), List(3, 3), List(2, 2, 2))

Я бы предположил, что есть простая функция List, которая делает это, но не может найтиэто.

Answer 1

Это трюк, который я обычно использую:

def split[T](list: List[T]) : List[List[T]] = list match {
  case Nil => Nil
  case h::t => val segment = list takeWhile {h ==}
    segment :: split(list drop segment.length)
}

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

Answer 2

Черт, Рекс Керр, за написание ответа, на который я бы пошел.Поскольку есть небольшие стилистические различия, вот мое мнение:

list.tail.foldLeft(List(list take 1)) { 
    case (acc @ (lst @ hd :: _) :: tl, el) => 
        if (el == hd) (el :: lst) :: tl 
        else (el :: Nil) :: acc 
}

Так как элементы идентичны, я не стал переворачивать подсписки.

Answer 3

val xs = List(5, 2, 3, 3, 3, 5, 5, 3, 3, 2, 2, 2)

Вот другой способ.

(List(xs.take(1)) /: xs.tail)((l,r) =>
  if (l.head.head==r) (r :: l.head) :: l.tail else List(r) :: l
).reverseMap(_.reverse)

Answer 4

list.foldRight(List[List[Int]]()){
  (e, l) => l match {
    case (`e` :: xs) :: fs => (e :: e :: xs) :: fs
    case _ => List(e) :: l
  }
}

Или

list.zip(false :: list.sliding(2).collect{case List(a,b) => a == b}.toList)
 .foldLeft(List[List[Int]]())((l,e) => if(e._2) (e._1 :: l.head) :: l.tail 
                                       else List(e._1) :: l ).reverse

[Редактировать]

//find the hidden way 
//the beauty must be somewhere
//when we talk scala

def split(l: List[Int]): List[List[Int]] = 
  l.headOption.map{x => val (h,t)=l.span{x==}; h::split(t)}.getOrElse(Nil)

Answer 5

У меня есть эти реализации без работы над методами коллекций. В конце я проверил более простые реализации inits и tails и оставил кластер. Каждый новый метод, каким бы простым он ни был, в конечном итоге собирает большой налог, который трудно увидеть со стороны. Но вот реализация, которую я не использовал.

import generic._
import scala.reflect.ClassManifest
import mutable.ListBuffer
import annotation.tailrec
import annotation.unchecked.{ uncheckedVariance => uV }

def inits: List[Repr] = repSequence(x => (x, x.init), Nil)
def tails: List[Repr] = repSequence(x => (x, x.tail), Nil)
def cluster[A1 >: A : Equiv]: List[Repr] =
  repSequence(x => x.span(y => implicitly[Equiv[A1]].equiv(y, x.head)))

private def repSequence(
  f: Traversable[A @uV] => (Traversable[A @uV], Traversable[A @uV]),
  extras: Traversable[A @uV]*): List[Repr] = {

  def mkRepr(xs: Traversable[A @uV]): Repr = newBuilder ++= xs result
  val bb = new ListBuffer[Repr]

  @tailrec def loop(xs: Repr): List[Repr] = {
    val seq = toCollection(xs)
    if (seq.isEmpty)
      return (bb ++= (extras map mkRepr)).result

    val (hd, tl) = f(seq)
    bb += mkRepr(hd)
    loop(mkRepr(tl))
  }

  loop(self.repr)
}

[Редактировать: я забыл, что другие люди не будут знать внутренностей. Этот код написан изнутри TraversableLike, поэтому он не будет работать из коробки.]

Answer 6

Вот хвосто-рекурсивное решение, вдохновленное @Kevin Wright и @Landei:

@tailrec
def sliceEqual[A](s: Seq[A], acc: Seq[Seq[A]] = Seq()): Seq[Seq[A]] = {
  s match {
    case fst :: rest =>
      val (l, r) = s.span(fst==)
      sliceEqual(r, acc :+ l)
    case Nil => acc
  }
}

Answer 7

Вот немного чище:

def groupConsequtive[A](list: List[A]): List[List[A]] = list match {
  case head :: tail =>
    val (t1, t2) = tail.span(_ == head)
    (head :: t1) :: groupConsequtive(t2)
  case _ => Nil  
}

хвостовая рекурсивная версия

@tailrec
def groupConsequtive[A](list: List[A], acc: List[List[A]] = Nil): List[List[A]] = list match {
  case head :: tail =>
    val (t1, t2) = tail.span(_ == head)
    groupConsequtive(t2, acc :+ (head :: t1))
  case _ => acc
}

Answer 8

это может быть проще:

val input = List(5, 2, 3, 3, 3, 5, 5, 3, 3, 2, 2, 2)
input groupBy identity values