Scala: scinder une liste en utilisant un prédicat pour les sous-listes

Question

Je viens d'avoir un cas d'utilisation où je devais diviser une liste en n sous-listes, de sorte que les éléments sont pris dans l'ordre de la liste originale et groupés alors que le prédicat est vrai sous-liste (lorsqu'elle est fausse, une nouvelle sous-liste est lancée). Je n'ai pas trouvé cette fonctionnalité dans la bibliothèque standard, et j'ai pensé que c'était un bon exercice pour essayer de le résoudre dans un style fonctionnel (car je suis loin d'un gourou fonctionnel).

Voici le code que j'ai trouvé. Mais je pense que cela peut être amélioré beaucoup. Pouvez-vous m'aider à trouver une meilleure façon de coder cela?

class ListWithSplitter[A](val theList:List[A]) 
{ 
    private def sublistWhile(list:List[A], pred:(List[A] => Boolean)):(List[A],List[A]) = 
    { 
    def combine(okList:List[A], remaining:List[A], pred:(List[A] => Boolean)):(List[A],List[A]) = 
    { 
     if(pred(okList ::: remaining.head :: Nil)) 
     combine(okList ::: remaining.head :: Nil, remaining.tail, pred) 
     else 
     (okList, remaining) 
    } 

    list match { 
     case Nil => (Nil, Nil) 
     case x :: Nil => (list, Nil) 
     case x :: xs => combine(List(x), xs, pred) 
    } 
    } 

    private def combinedSplit(list:List[A], pred:(List[A] => Boolean)):List[List[A]] = 
    { 
    val r = sublistWhile(list, pred) 
    r match { 
     case (Nil, Nil) => List(Nil) 
     case (x, Nil) => List(x) 
     case (x, y) => x :: combinedSplit(y, pred) 
    } 
    } 

    def combinedSplit(pred:(List[A] => Boolean)):List[List[A]] = 
    { 
    combinedSplit(theList, pred) 
    } 
} 

trait ListCombinedSplit 
{ 
    implicit def list2combSplitter[A](x:List[A]) : ListWithSplitter[A] = new ListWithSplitter(x) 
} 

object ListSplitter extends ListCombinedSplit { 

    def main(args:Array[String]) 
    { 
    // sample usage: sum of each sublist is less than 100 
    val a = List(4, 59, 10, 24, 42, 9, 2, 44, 44, 44, 44) 
    val b = a combinedSplit { list:List[Int] => ((0 /: list)(_ + _)) < 100 } 

    b foreach println 
    } 
} 

Résultat d'échantillon est:

List(4, 59, 10, 24) 
List(42, 9, 2, 44) 
List(44, 44) 
List(44) 

Answer 1

Votre code a le problème que de simples invocations de votre prédicat font O (N^2). En outre, je pense que la substance orientée objet est trop compliquée.

je suis venu avec:

scala> def lsplit(x : List[Int], limit : Int) = 
    (x foldLeft (0, Nil.asInstanceOf[List[List[Int]]])) ((x, y) => x match { 
    case (v, l::xs) if v+y < limit => (v+y, (y::l)::xs) 
    case (_, xs) => (y, (y::Nil)::xs) 
    })._2.reverse.map(x => x.reverse) 

lsplit: (List[Int],Int)List[List[Int]] 

scala> lsplit(List.range(1,50), 100) 
res9: List[List[Int]] = List(List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13), List(14, 15, 16, 17, 18, 19), List(20, 21, 22, 23), List(24, 25, 26), List(27, 28, 29), List(30, 31, 32), List(33, 34), List(35, 36), List(37, 38), List(39, 40), List(41, 42), List(43, 44), List(45, 46), List(47, 48), List(49)) 

scala> lsplit(List.range(1,50), 122) 
res10: List[List[Int]] = List(List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15), List(16, 17, 18, 19, 20, 21), List(22, 23, 24, 25, 26), List(27, 28, 29, 30), List(31, 32, 33), List(34, 35, 36), List(37, 38, 39), List(40, 41), List(42, 43), List(44, 45), List(46, 47), List(48, 49)) 

Cela ne vous permet pas de spécifier prédicat arbitraire, mais vous pouvez le faire fonctionner pour les prédicats comme pli en changeant la manipulation avec la première elent de la paire en foldLeft .

Answer 2

Que diriez-vous les éléments suivants:

def toggledPartition[A](xs: List[A])(p: A => Boolean): List[List[A]] = 
    if (xs.isEmpty) Nil 
    else xs span p match { case (a,b) => a :: toggledPartition(b)(x => !p(x)) } 

exemple Runnable à http://ideone.com/HBrOv

Par la façon dont j'ai le sentiment que j'ai vu quelque chose de semblable dans la fonctionnalité dans scalaz, mais ne peut pas se rappeler où.