2009-02-24 61 views
2

我剛剛有一個用例,我需要將列表拆分爲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) 

回答

4

您的代碼,你的謂詞單純的調用使問題是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改變操控使它成爲倍樣謂詞工作。

+0

謝謝......不像我打算的一般,但會爲我的用例做! – 2009-03-02 02:37:32

4

如何如下:

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的例子,但不記得在哪裏。