2011-01-21 1 views

Odpowiedz

15

Jest to trik, który normalnie używać:

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) 
} 

Właściwie ... Nie, ja zwykle streszczenie nad rodzaju zbiórki i optymalizację rekursji ogonowej z tak dobrze, ale chciał zachować prostą odpowiedź.

+2

Nice. Ale czy nie byłoby to na tyle powszechne, by gwarantować własną funkcję biblioteczną? –

+0

Nie ma tam argumentu, na pewno pojawia się on w pytaniach więcej niż jeden raz ... –

+0

@KevinWright "optymalizuj z rekurencją ogona" -> Jak byś to zrobił? –

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

Oto inny sposób.

(List(xs.take(1)) /: xs.tail)((l,r) => 
    if (l.head.head==r) (r :: l.head) :: l.tail else List(r) :: l 
).reverseMap(_.reverse) 
6
list.foldRight(List[List[Int]]()){ 
    (e, l) => l match { 
    case (`e` :: xs) :: fs => (e :: e :: xs) :: fs 
    case _ => List(e) :: l 
    } 
} 

Albo

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 

[Edytuj]

//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) 
+0

Czy którekolwiek z podejść będzie działać z wartościami NaN? Próbuję ustalić, czy widzę n kolejnych wartości Double.NaN w wektorze.Patrząc na zamieszczone tutaj rozwiązania, wydaje się, że to nic, co sam wymyślę. – TomTom101

+0

NaN wartości wymagałyby oczywiście specjalnej obsługi. Może mógłbyś zawrzeć 'Int's w' Option [Int] 'i przekonwertować' NaN's na 'None's. Wtedy będą działać zwykłe rozwiązania oparte na równości. Możesz też napisać własną funkcję równości. – Landei

8

Cholera Rex Kerr, na piśmie odpowiedź pójdę do. Ponieważ istnieją drobne różnice stylistyczne, oto moje zdanie:

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

ponieważ elementy są identyczne, nie przeszkadza odwrócenie listy zagnieżdżone.

+0

Czy możesz wyjaśnić (lub wskaż mi jakiś link) przypadku (acc @ (lst @ hd :: _). Nigdy nie widziałem takiej składni wcześniej.Dzięki z góry. – gashu

+1

@ gashu W dopasowaniu wzorca, 'x @ y' oznacza, że ​​'x' zostanie przypisane cokolwiek, co jest _matched_ przez' y'. Tak więc na przykład 'x @ _ :: _' przydzieli xa niepustej liście (czyli liście z głową i ogonem , jak przystało na '_ :: _') Tak więc' acc', powyżej, jest całą listą, a 'lst' jest głową listy –

+0

@ daniel-c-sobral, więc takie wyrażenia są używane tylko we wzorcu pasujące, lub w innym kontekście, mają na myśli coś innego? – gashu

5

Mam te implementacje kłamstwa od pracy na metodach kolekcji. W końcu sprawdziłem prostsze implementacje inicjałów i ogonów oraz opuszczonego klastra. Każda nowa metoda, bez względu na to, jak prosta kończy się zebranie dużego podatku, który jest trudny do zauważenia z zewnątrz. Ale tutaj jest implementacja, której nie używałem.

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) 
} 

[Edytuj: Zapominam, że inni ludzie nie znają elementów wewnętrznych. Ten kod jest napisane od wewnątrz TraversableLike, więc nie zabraknie oknie]

0

to może być prostsze.

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

To zgrupuje wszystkie identyczne elementy, nie tylko sekwencyjne. –

2

Oto ogon rekurencyjnej rozwiązanie inspirowane @Kevin Wright i @ 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 
    } 
}