Scala implementation of Haskell's groupBy

Question

I'm looking for a Scala implementation of Haskell's groupBy.

The behavior should be like this:

isD :: Char -> Bool
isD c = elem c "123456789-_ "

groupBy (\a b -> isD a == isD b) "this is a line with 0123344334343434343434-343 3345"
["this"," ","is"," ","a"," ","line"," ","with"," 0123344334343434343434-343 3345"]

I tried the Scala groupBy function, however it only takes a function of one argument, instead of Haskell's 2. I also looked at partition, however it only returns a tuple.

The function I'm looking for should group each consecutive element matching a predicate.

This is nontrivial, but the answer already exists (for arbitrary types, including strings) as an example used to answer another question: http://stackoverflow.com/questions/5410846 (Note that the method is called `groupedWhile`.) — Rex Kerr, Nov 24 '11 at 20:21
thanks for pointing this out, obviously not the term I searched for ;) — Sander, Nov 24 '11 at 21:08
@hammar thanks for the pointer. Removed the answer and moved it to a separate one below. — Sander, Nov 25 '11 at 10:38
Several more implementations here too: http://stackoverflow.com/questions/4761386/scala-list-function-for-grouping-consecutive-identical-elements — Todd Owen, Dec 28 '14 at 07:02

Luigi Plinge · Accepted Answer · 2011-11-24T22:45:42.523

Questions like this seem to come up quite often, which is a good indication IMO that Rex Kerr's groupedWhile method should be included in the standard collections library. However if you don't want to copy / paste that into your project...

I like your recursive solution, but it doesn't actually output the right thing (i.e. Strings), so here's how I'd change it:

def groupBy(s: String)(f: (Char, Char) => Boolean): List[String] = s match {
  case "" => Nil
  case x => 
    val (same, rest) = x span (i => f(x.head, i))
    same :: groupBy(rest)(f)
}

Then, take your function and try it in the REPL:

val isD = (x: Char) => "123456789-_ " contains x
groupBy("this is a line with 0123344334343434343434-343 3345")(isD(_) == isD(_))

The result is a List[String], which is presumably what you really wanted.

score 2 · Answer 2 · answered Nov 25 '11 at 10:37

Used this for now, thanks to the answers:

def groupByS(eq: (Char,Char) => Boolean, list: List[Char]): List[List[Char]] = {
    list match {
    case head :: tail => {
      val newHead = head :: tail.takeWhile(eq(head,_))
      newHead :: groupByS(eq, tail.dropWhile(eq(head,_)))
    }
    case nil => List.empty
  }
}

this can probably be improved upon ;)

score 1 · Answer 3 · answered Nov 24 '11 at 19:34

1

It's surely can't be too difficult to translate the Haskell version into Scala. Here's the Haskell definition of groupBy. It uses span; I don't know offhand whether there's an equivalent to span in Scala or whether you'll need to translate the Haskell definition of span as well.

answered Nov 24 '11 at 19:34

dave4420

46,404
6
118
152

There is a Scala version of `span`, but it is hard to keep all the types straight in the general case, due to the differences between the Haskell and Scala type systems. – Rex Kerr Nov 24 '11 at 20:24
Thanks for the answers. I've hacked up something that's on its way to working for this specific case. – Sander Nov 24 '11 at 21:07

score 0 · Answer 4 · answered Dec 20 '15 at 17:11

def partitionBy[T, U](list: List[T])(f: T => U ): List[List[T]] = {

  def partitionList(acc: List[List[T]], list: List[T]): List[List[T]] = {
    list match {
      case Nil => acc
      case head :: tail if f(acc.last.head) == f(head) => partitionList(acc.updated(acc.length - 1, head :: acc.last), tail)
      case head :: tail => partitionList(acc ::: List(head) :: Nil, tail)
    }
  }

  if (list.isEmpty) List.empty
  else partitionList(List(List(list.head)), list.tail)
}

partitionBy("112211".toList)(identity)
//res: List[List[Char]] = List(List(1, 1), List(2, 2), List(1, 1))


val l = List("mario", "adam", "greg", "ala", "ola")

partitionBy(l)(_.length)
//res: List[List[String]] = List(List(mario), List(greg, adam), List(ola, ala))

score 0 · Answer 5 · answered Nov 24 '11 at 21:59

My version, just messing around -- not too sure about it. I know Haskell better than Scala but trying to learn Scala:

object GroupByTest extends App {    
  val ds = Set('0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '-', '_', ' ')

  def isD(d: Char) = ds contains d

  def hgroupBy[A](op: A => (A => Boolean), a: List[A]): List[List[A]] = 
    a match {
      case Nil => List.empty
      case x :: xs =>
        val t = xs span op(x)         
        (x :: t._1) :: hgroupBy(op, t._2)        
    }

  val lambda: Char => Char => Boolean = x => y => isD(x) == isD(y)

  println(hgroupBy(lambda, "this is a line with 0123344334343434343434-343 3345".toList))
}

Scala implementation of Haskell's groupBy

5 Answers5