CODEWITHSUNDEEP
listscalaimmutability
mitchus
mitchus

Reputation: 4877

Chopping up a list into a list of lists

Suppose I have a list of elements myl and a function f. I would like to chop up myl into a list of lists, where each new "sublist" contains a contiguous stretch of myl on which the value of f is constant.

For example, if myl = List( (1,2), (3,2), (4,1), (6,2) ) and def f(x: (Int, Int)) = x._2. Then the result should be List( List((1,2), (3,2)), List((4, 1)), List((6,2)) ).

Is there an elegant way to write such a function without any vars?

Upvotes: 1

Views: 198

Answers (4)

Ben James
Ben James

Reputation: 125119

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)))

Edit: I also wrote this version, using 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
  }

This is essentially similar to ghik's solution, but using pattern matching instead of isEmpty and head.

(An explanation of the name groupBy: there is a function of the same name in the Haskell library, which has this exact same behaviour.)

Upvotes: 4

Nikita Volkov
Nikita Volkov

Reputation: 43309

Your problem is too specific for there to exist a general function solving it, so we'll have to write a function of our own.

The standard strategy to implementing functional algorithms is Divide and conquer, which basically means extracting the smallest part of the problem and then gradually building up the algorithm over it.

Implementation

Okay, the obviously smallest thing we'll need is to test two items for contiguity:

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

Then we'll need some function arranging the lists using the two-item comparison function. Would be nice if the standard library had it, but it doesn't, so we define our own:

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
    }

Okay, you can see that the above implementation relies on two other functions, let's define them too:

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

That's it!

Usage

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)))

You can now see that we've created a pretty flexible and general solution, working on lists of items of any type and allowing you to use any other testing function to arrange them. Also we've heavily utilized division of a complex algorithm to small easily understandable parts to solve this.

Upvotes: 1

ghik
ghik

Reputation: 10764

Little more general solution:

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

Example usage:

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)))

Upvotes: 2

Beryllium
Beryllium

Reputation: 12988

You could try 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
    }
}

Upvotes: 1

Related Questions