CODEWITHSUNDEEP
scalascala-collections
Michael
Michael

Reputation: 42050

List of every n-th item in a given list

This is a simple exercise I am solving in Scala: given a list l return a new list, which contains every n-th element of l. If n > l.size return an empty list.

def skip(l: List[Int], n: Int) = 
  Range(1, l.size/n + 1).map(i => l.take(i * n).last).toList

My solution (see above) seem to work but I am looking for smth. simpler. How would you simplify it?

Upvotes: 14

Views: 9843

Answers (6)

elm
elm

Reputation: 20405

Two approaches based in filter on indexes, as follows,

implicit class RichList[A](val list: List[A]) extends AnyVal {

  def nthA(n: Int) = n match {
    case 0 => List()
    case _ => (1 to a.size).filter( _ % n == 0).map { i => list(i-1)}
  }

  def nthB(n: Int) = n match {
    case 0 => List()
    case _ => list.zip(Stream.from(1)).filter(_._2 % n == 0).unzip._1
  }
}

and so for a given list

val a = ('a' to 'z').toList

we have that

a.nthA(5)
res: List(e, j, o, t, y)

a.nthA(123)
res: List()

a.nthA(0)
res: List()

Update

Using List.tabulate as follows,

implicit class RichList[A](val list: List[A]) extends AnyVal {
  def nthC(n: Int) = n match {
    case 0 => List()
    case n => List.tabulate(list.size) {i => 
                if ((i+1) % n == 0) Some(list(i)) 
                else None }.flatten
  }
}

Upvotes: 1

Mark Lister
Mark Lister

Reputation: 1143

You could omit toList if you don't mind an iterator:

 scala> def skip[A](l:List[A], n:Int) =
      l.grouped(n).filter(_.length==n).map(_.last).toList
 skip: [A](l: List[A], n: Int)List[A]

 scala> skip (l,3)
 res6: List[Int] = List(3, 6, 9)

Upvotes: 1

The Archetypal Paul
The Archetypal Paul

Reputation: 41749

Somewhat simpler:

scala> val l = (1 to 10).toList
l: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

// n == 3

scala> l.drop(2).grouped(3).map(_.head).toList
res0: List[Int] = List(3, 6, 9)

// n > l.length

scala> l.drop(11).grouped(12).map(_.head).toList
res1: List[Int] = List()

(the toList just to force the iteratot to be evaluated)

Works with infinite lists:

Stream.from(1).drop(2).grouped(3).map(_.head).take(4).toList
res2: List[Int] = List(3, 6, 9, 12)

Upvotes: 21

Przemek Piotrowski
Przemek Piotrowski

Reputation: 7456

Fold left approach O(n) 

def skip(xs: List[Int], n: Int) = {
  xs.foldLeft((List[Int](), n)){ case ((acc, counter), x) =>
      if(counter==1)
        (x+:acc,n)
      else
        (acc, counter-1)
  }
  ._1
  .reverse
}

scala > skip(List(1,2,3,4,5,6,7,8,9,10), 3)

Tailrec less readable approach O(n)

import scala.annotation.tailrec

def skipTR(xs: List[Int], n: Int) = {
  @tailrec
  def go(ys: List[Int], acc: List[Int], counter: Int): List[Int] = ys match {
    case k::ks=>
      if(counter==1)
        go(ks, k+:acc , n)
      else
        go(ks, acc, counter-1)
    case Nil => acc
  }
  go(xs, List(), n).reverse

}
skipTR(List(1,2,3,4,5,6,7,8,9,10), 3)

Upvotes: 1

bjfletcher
bjfletcher

Reputation: 11498

A bit more readable and the loop size is O(l.length/n):

def skip(l: List[Int], n: Int) = {
  require(n > 0)
  for (step <- Range(start = n - 1, end = l.length, step = n))
    yield l(step)
}

Upvotes: 4

Marth
Marth

Reputation: 24802

scala> def skip[A](l:List[A], n:Int) = 
         l.zipWithIndex.collect {case (e,i) if ((i+1) % n) == 0 => e} // (i+1) because zipWithIndex is 0-based
skip: [A](l: List[A], n: Int)List[A]

scala> val l = (1 to 10).toList
l: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

scala> skip(l,3)
res2: List[Int] = List(3, 6, 9)

scala> skip(l,11)
res3: List[Int] = List()

Upvotes: 9

Related Questions