I wrote the following function to convert List[Int] => List[List[Int]].

Its intended purpose is to extract 1, followed by its non 1 followers, into a group.

input: List(1,2,2,1,3,3)

output: List( List(1,2,2), List(1,3,3) )


def leadingOnesGroup(xs: List[Int]): List[List[Int]] = 
        xs match {
          case Nil    => Nil 
          case _ :: _ => 
           val (first, rest)          = xs.span(_ == 1)
           val (followers, remainder) = rest.span(_ != 1)
           (first ++ followers) :: leadingOnesGroup(remainder)


scala> leadingOnesGroup(List(1,2,2))
res19: List[List[Int]] = List(List(1, 2, 2))

scala> leadingOnesGroup(List(1,2,2,1,3,3))
res20: List[List[Int]] = List(List(1, 2, 2), List(1, 3, 3))

scala> leadingOnesGroup(List(1,2,2,1,3,3,1,5,5))
res21: List[List[Int]] = List(List(1, 2, 2), List(1, 3, 3), List(1, 5, 5))
  • \$\begingroup\$ If the first element in the input is not one, your first list will not start with a one. Is that desired behaviour? One alternative would be to discard elements until the first 1 is encountered. Another would be to return a tuple where the first value is the not-starting-with-one prefix. Otherwise, you're checking the head of the first element again, having already evaluated it (and discared the information). \$\endgroup\$ – itsbruce Sep 7 '16 at 19:38

The current version of the function does not take into account the cases:

  • (as @itsbruce mentioned) if the list starts with a value other than '1'

  • if there are consecutive '1's

The second case is using wildcards, but instead it'd better directly match a list starting with '1':

case 1 :: tail => {
  // we take only the following elements different from 1
  val followers = tail.takeWhile(_ != 1)
  // we drop the 'followers' prefix for the recursive call
  val remainder = tail.drop(followers.size)
  (1 :: followers) :: leadingOnesGroup(remainder)

Of course, this block can be shortened to two lines only, but it will be less readable.

Since it is not clear how to process lists that do not start with '1', a generic matcher with an explicit exception can be added:

case _ => throw new IllegalArgumentException("Unexpected start of list: " + xs)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.