1

假设我有一个元素列表myl和一个函数f。我想分割myl成一个列表列表，其中每个新的“子列表”都包含一个连续的片段，myl其中的值f是恒定的。

例如，如果myl = List( (1,2), (3,2), (4,1), (6,2) )和def f(x: (Int, Int)) = x._2。那么结果应该是List( List((1,2), (3,2)), List((4, 1)), List((6,2)) )。

有没有一种优雅的方式来编写这样一个没有任何vars 的函数？

4

4 回答 4

4 
def groupBy[A](as: List[A])(p: (A, A) => Boolean): List[List[A]] =
  as.foldRight(List.empty[List[A]]) {
    case (x, (ys @ y :: _) :: zs) if p(x, y) => (x :: ys) :: zs
    case (x, ys) => List(x) :: ys
  }

scala> groupBy(myl)(_._2 == _._2)
res0: List[List[(Int, Int)]] = List(List((1,2), (3,2)), List((4,1)), List((6,2)))

编辑：我也写了这个版本，使用span：

def groupBy[A](as: List[A])(p: (A, A) => Boolean): List[List[A]] =
  as match {
    case x :: xs =>
      val (ys, zs) = xs.span(p(x, _))
      (x :: ys) :: groupBy(zs)(p)
    case _ => Nil
  }

这本质上类似于 ghik 的解决方案，但使用模式匹配而不是isEmptyand head。

（名称的解释groupBy：Haskell 库中有一个同名的函数，它具有完全相同的行为。）

于 2013-06-01T10:47:17.760 回答
2

更通用的解决方案：

def partitionBy[A](list: List[A])(groupingFunc: A => Any): List[List[A]] =
  if (list.nonEmpty) {
    val firstGroupingValue = groupingFunc(list.head)
    val (group, rest) = list.span(groupingFunc(_) == firstGroupingValue)
    group :: partitionBy(rest)(groupingFunc)
  } else Nil

示例用法：

scala> partitionBy(List((1,2),(3,2),(5,2),(1,1),(2,1),(3,2),(5,2)))(_._2)
res14: List[List[(Int, Int)]] = List(List((1,2), (3,2), (5,2)), List((1,1), (2,1)), List((3,2), (5,2)))
于 2013-06-01T09:52:20.747 回答
1

你可以试试foldRight

val result2 = l.foldRight(List[List[(Int, Int)]]()) {
  (x, acc) =>
    if (acc.isEmpty) {
      List(x) :: Nil
    } else if (acc.head.head._2 == x._2) {
      (x :: acc.head) :: acc.tail
    } else {
      List(x) :: acc
    }
}
于 2013-06-01T09:16:50.640 回答
1

你的问题太具体了，没有一个通用的函数来解决它，所以我们必须自己编写一个函数。

实现函数式算法的标准策略是分而治之，这基本上意味着提取问题的最小部分，然后在其上逐步构建算法。

执行

好的，显然我们需要做的最小的事情是测试两个项目的连续性：

def testContiguity( a : (Int, Int), b : (Int, Int) ) : Boolean 
  = a._2 == b._2

然后我们需要一些函数来使用两项比较函数来排列列表。如果标准库有它会很好，但它没有，所以我们定义自己的：

def arrange
  [ A ]
  ( list : List[ A ] )
  ( f : (A, A) => Boolean ) 
  : List[ List[ A ] ]
  = list match {
      case a :: b :: tail => 
        if( f(a, b) ) putInFirstGroup( a, arrange( b :: tail )( f ) )
        else putInNewGroup( a, arrange( b :: tail )( f ) )
      case a :: Nil =>
        putInNewGroup( a, Nil )
      case Nil =>
        Nil
    }

好的，你可以看到上面的实现依赖于另外两个函数，我们也定义它们：

def putInFirstGroup
  [ A ]
  ( item : A, groups : List[ List[ A ] ] ) 
  : List[ List[ A ] ]
  = groups match {
      case group :: tail =>
        (item :: group) :: tail
      case Nil => 
        (item :: Nil) :: Nil
    }

def putInNewGroup
  [ A ]
  ( item : A, groups : List[ List[ A ] ] ) 
  : List[ List[ A ] ]
  = (item :: Nil) :: groups

就是这样！

用法

scala> arrange( List( (1,2), (3,2), (4, 1), (6,2) ) )( testContiguity )
res2: List[List[(Int, Int)]] = List(List((1,2), (3,2)), List((4,1)), List((6,2)))

您现在可以看到我们已经创建了一个非常灵活和通用的解决方案，处理任何类型的项目列表，并允许您使用任何其他测试功能来安排它们。此外，我们还大量利用将复杂算法划分为易于理解的小部分来解决此问题。

于 2013-06-01T10:12:50.557 回答