代码之家  ›  专栏  ›  技术社区  ›  Germán

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

  •  2
  • Germán  · 技术社区  · 17 年前

    我刚刚有一个用例,我需要将一个列表拆分为n个子列表,这样元素就可以从原始列表中按顺序提取并分组,同时子列表的谓词为真(当它为假时,会启动一个新的子列表)。我在标准库中没有找到这个功能,我认为尝试以函数式风格解决它是一个很好的练习(因为我远非函数大师)。

    下面是我想出的代码。但我怀疑它可以改进很多。你能帮我找到一个更好的编码方法吗?

    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)
    
    2 回复  |  直到 17 年前
        1
  •  5
  •   ron    13 年前

    以下情况如何:

    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

        2
  •  4
  •   jpalecek    17 年前

    我想到了:

    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中更改对的第一个元素的操作,使其适用于折叠式谓词。

    推荐文章