I have a list, and a binary relationship, and I want to group the list, joining the neighbors that satisfy the relationship. It being equivalence relationship is kind of nice to have, but not necessary. Can be an order actually, so we group monotone sequences. Etc.
(here's version 3, ugly)
def groupByRelationship[T](p: ((T,T) => Boolean)) = {
new (List[T] => List[List[T]]) { self =>
def apply(xs: List[T]): List[List[T]] =
xs match {
case List() => List()
case (x:T) :: _ =>
val pairs:Iterator[Seq[T]] = xs.sliding(2)
val (ps1, ps2) = pairs.span(_.toList match {
case a::b::Nil => a==b || p(a, b)
case _ => false
})
val chain:List[T] = x::(ps1 map (_(1))).toList
val tail = ps2.toList collect {case a::b::Nil => b}
chain :: self(tail)
}
}
}
This function groups a list into segments where values of a function are the same.
I've been using it for a while.
def groupListBy[T,U](xs: List[T])(f: T => U): List[List[T]] = groupListByRelationship[T](xs)((x,y) => f(x)==f(y))
A test:
val g1 = groupByRelationship[Int](_ < _)(List(1,2,4,2))
g1 must_== List(List(1,2,4), List(2))
val g2 = groupByRelationship[Int](_ > _)(List(1,2,4,2))
g2 must_== List(List(1),List(2), List(4,2))
Any questions?