How to split a List of elements into lists with at most N items?
ex: Given a list with 7 elements, create groups of 4, leaving the last group possibly with less elements.
split(List(1,2,3,4,5,6,"seven"),4)
=> List(List(1,2,3,4), List(5,6,"seven"))
Add a comment
|
5 Answers
I think you're looking for grouped. It returns an iterator, but you can convert the result to a list,
scala> List(1,2,3,4,5,6,"seven").grouped(4).toList
res0: List[List[Any]] = List(List(1, 2, 3, 4), List(5, 6, seven))
3 Comments
J Atkin
Scala lists have something for everything.
Rakshith
I have a weird question. For the same case if i convert the data to a sequence, I get a Stream Object. Why is that?
Ion Freeman
@Rakshith That sounds like a separate question. Scala has a mysterious gnome that chooses a data structure, and it chose a Stream for you. If you want a List, you should request a List, but you can also just trust the gnome's judgment.
There is much easier way to do the task using sliding method. It works this way:
val numbers = List(1, 2, 3, 4, 5, 6 ,7)
Lets say you want to break the list into smaller lists of size 3.
numbers.sliding(3, 3).toList
will give you
List(List(1, 2, 3), List(4, 5, 6), List(7))
Comments
Or if you want to make your own:
def split[A](xs: List[A], n: Int): List[List[A]] = {
if (xs.size <= n) xs :: Nil
else (xs take n) :: split(xs drop n, n)
}
Use:
scala> split(List(1,2,3,4,5,6,"seven"), 4)
res15: List[List[Any]] = List(List(1, 2, 3, 4), List(5, 6, seven))
edit: upon reviewing this 2 years later, I wouldn't recommend this implementation since size is O(n), and hence this method is O(n^2), which would explain why the built-in method becomes faster for large lists, as noted in comments below. You could implement efficiently as follows:
def split[A](xs: List[A], n: Int): List[List[A]] =
if (xs.isEmpty) Nil
else (xs take n) :: split(xs drop n, n)
or even (slightly) more efficiently using splitAt:
def split[A](xs: List[A], n: Int): List[List[A]] =
if (xs.isEmpty) Nil
else {
val (ys, zs) = xs.splitAt(n)
ys :: split(zs, n)
}
14 Comments
Kipton Barros
xs splitAt n is an alternative to the combination xs take n and xs drop n
Jed Wesley-Smith
this will explode the stack, consider a recursive implementation
Luigi Plinge
@Kipton, true, but you need to extract the results to temporary vals so it adds a couple of lines to a method. I did a quick benchmark and it seems using
splitAt instead of take/dropimproves performance on average around 4%; both are 700-1000% quicker than .grouped(n).toList!Kipton Barros
@Luigi, Wow. Any thoughts about why
grouped-toList is so slow? That sounds like a bug.Luigi Plinge
@Jed You're right in extreme cases, but your implementation depends on what you're using it for. For OP's use-case (if
grouped didn't exist :)), simplicity is the overriding factor. For the standard library, stability and performance should trump elegance. But there are plenty of examples both in Programming in Scala and the standard libraries of normal-recursive (rather than tail-recursive) calls; it's a standard and important weapon in the FP toolbox. |
I am adding a tail recursive version of the split method since there was some discussion of tail-recursion versus recursion. I have used the tailrec annotation to force the compiler to complain in case the implementation is not indeed tail-recusive. Tail-recursion I believe turns into a loop under the hood and thus will not cause problems even for a large list as the stack will not grow indefinitely.
import scala.annotation.tailrec
object ListSplitter {
def split[A](xs: List[A], n: Int): List[List[A]] = {
@tailrec
def splitInner[A](res: List[List[A]], lst: List[A], n: Int) : List[List[A]] = {
if(lst.isEmpty) res
else {
val headList: List[A] = lst.take(n)
val tailList : List[A]= lst.drop(n)
splitInner(headList :: res, tailList, n)
}
}
splitInner(Nil, xs, n).reverse
}
}
object ListSplitterTest extends App {
val res = ListSplitter.split(List(1,2,3,4,5,6,7), 2)
println(res)
}
1 Comment
Jeffrey Bosboom
This answer could be improved by adding some explanation. Given that the accepted answer seems to be the canonical, intended way to do this, you should explain why someone would prefer this answer.
I think this is the implementation using splitAt instead of take/drop
def split [X] (n:Int, xs:List[X]) : List[List[X]] =
if (xs.size <= n) xs :: Nil
else (xs.splitAt(n)._1) :: split(n,xs.splitAt(n)._2)
