Scala: разделение списка с использованием предиката для подсписков

Question

У меня только что был случай, когда мне нужно было разбить список на n подсписков, чтобы элементы были взяты по порядку из исходного списка и сгруппированы, в то время как предикат имеет значение true для подсписка (когда он равен false, новый подсписок запущен). Я не нашел эту функциональность в стандартной библиотеке, и я подумал, что это было хорошее упражнение, чтобы попытаться решить ее в функциональном стиле (поскольку я далек от функционального гуру).

Ниже приведен код, который я придумал. Но я подозреваю, что это можно значительно улучшить. Можете ли вы помочь мне найти лучший способ закодировать это?

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)

Answer 1

Как насчет следующего:

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, но не могу вспомнить, где.

Answer 2

В вашем коде проблема в том, что простые вызовы вашего предиката делают его 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.