Scala：使用子列表的谓词拆分列表

我刚刚有一个用例，我需要将列表拆分为n个子列表，以便元素按原始列表的顺序进行分组，而谓词对于子列表（当它为假时，启动一个新的子列表）。我没有在标准库中找到这个功能，我认为这是一个很好的练习，试图以功能性的风格来解决它（因为我远离功能大师）。Scala：使用子列表的谓词拆分列表

下面是我想出的代码。但我怀疑它可以提高很多。你能帮我找到更好的方法来编码吗？

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

结果的样品是：

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

来源

2009-02-24 Germán

您的代码，你的谓词单纯的调用使问题是O（N^2）。另外，我认为面向对象的东西太复杂了。

我想出了：

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

这并不让你指定任意断言，但可以通过与一对foldLeft的第一elent改变操控使它成为倍样谓词工作。

来源

2009-03-01 21:42:04 jpalecek

谢谢......不像我打算的一般，但会为我的用例做！ – 2009-03-02 02:37:32

如何如下：

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

在http://ideone.com/HBrOv

通过我，我看到在scalaz功能类似的感觉方式Runnable的例子，但不记得在哪里。

来源

2012-05-22 09:37:13 ron

Scala：使用子列表的谓词拆分列表

回答

相关问题