Find nth element in list

[Harit Himanshu]

Hello All

I am learning Scala and as recommended working on S99 problem set. I wanted to get a quick code review done for problem

P03 (*) Find the Kth element of a list.

By convention, the first element in the list is element 0.

Example:

scala> nth(2, List(1, 1, 2, 3, 5, 8))
res0: Int = 2

My approach has been following, I am also writing test using ScalaTest so that I assert I do things right and learn TDD/BDD driven approach. Please let me know if this code could be improved further (I am sure it does)

object P03 {

  def nth(n: Int, l: List[Any]): Any = {

    require(n >= 0, "n must be greater than or equal to zero")

    l match {

      case List() => None

      case head :: tail if n == 0 => head

      case head :: tail if n > 0 => nth(n - 1, tail)

    }

  }

}

Tests

import com.learner.s99.P03._

import org.scalatest.{MustMatchers, FlatSpec}

class P03Spec extends FlatSpec

with MustMatchers {

  behavior of "A List"

  it must "return 0 in List(0,1,2,3) as 0th element" in {

    nth(0, List(0, 1, 2, 3)) mustBe 0

  }

  it must "return 3 in List(0,1,2,3) as 3rd element" in {

    nth(3, List(0, 1, 2, 3)) mustBe 3

  }

  it must "return None in List(0,1,2,3) as 10th element" in {

    nth(10, List(0, 1, 2, 3)) mustBe None

  }

  it must "throw an IllegalArgumentException for negative index in list" in {

    an [IllegalArgumentException] must be thrownBy nth(-10, List(0, 1, 2, 3))

  }

}

Thank you

[Vlad Patryshev]

This is all pretty cool, I would just remove some fluff:

  def nth[T](n: Int, list: List[T]): Option[T] = {

    list match {

      case Nil => None

      case head :: tail => if (n < 0) None else if (n== 0) head else nth(n - 1, tail)

    }

  }

Thanks,
-Vlad

--
You received this message because you are subscribed to the Google Groups "scala-user" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scala-user+...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Jason Zaugg]

On Sun, Jun 7, 2015 at 8:10 AM, Vlad Patryshev <vpatr...@gmail.com> wrote:

This is all pretty cool, I would just remove some fluff:

  def nth[T](n: Int, list: List[T]): Option[T] = {

    list match {

      case Nil => None

      case head :: tail => if (n < 0) None else if (n== 0) head else nth(n - 1, tail)

    }

  }

Here's what Vlad meant:

scala>   def nth[T](n: Int, list: List[T]): Option[T] = {

     |     list match {
     |       case Nil => None

     |       case head :: tail => if (n < 0) None else if (n== 0) Some(head) else nth(n - 1, tail)
     |     }
     |   }
nth: [T](n: Int, list: List[T])Option[T]

scala> nth(42, Nil)
res1: Option[Nothing] = None

scala> nth(0, List(1, 2))
res2: Option[Int] = Some(1)

scala> nth(1, List(1, 2))
res3: Option[Int] = Some(2)

scala> nth(2, List(1, 2))
res4: Option[Int] = None

​

Observations:

• We've introduced a type parameter to the method, so we can tie the element type of the list that we accept together with the result type.
• Rather than declaring the return type Any, we can be more precise with Option[T].

-jason

[Haoyi Li]

Maybe I'm missing something, but what's wrong with

def nth[T](n: Int, list: List[T]): Option[T] =  list.lift(n)

--

[Som Snytt]

List doesn't seem to have an efficient applyOrElse, so lifted it will walk twice for isDefinedAt and the apply.

[Pablo Díaz]

What about this:

def nth(n:Int, l:List[_]) = l.toStream.take(n+1).last

This should only traverse the list once, isn't it?

[Kevin Wright]

Shorter still:

def nth[T](n: Int, xs: List[T]) = xs.drop(n-1).headOption

Can't get much more efficient than this using a List.  But, frankly, if you're doing a lot of random access then List really isn't your best choice of collection.

Kevin Wright
mail: kevin....@scalatechnology.com
gtalk / msn : kev.lee...@gmail.com

quora: http://www.quora.com/Kevin-Wright

google+: http://gplus.to/thecoda

twitter: @thecoda

vibe / skype: kev.lee.wright

steam: kev_lee_wright

"My point today is that, if we wish to count lines of code, we should not regard them as "lines produced" but as "lines spent": the current conventional wisdom is so foolish as to book that count on the wrong side of the ledger" ~ Dijkstra

[Pablo Díaz]

I like your solution, much cleaner than my, as an alternative to the recursive one.

Yes, using a Scala List for random access is a very bad choice, but this problem is just one of the S99 problems which are just an adaptations from Prolog. It helps to learn to use the language but some of the exercices aren't probably a good idea to implement in terms of algorithm cost.

[Jaret Flores]

I’ve worked through some of the S99 problems myself (and problems in other texts). What I don’t understand is what functions are you “allowed” to use when solving the problem. It seems that non-[tail]recursive answers are avoiding use of the “index operator” () in exchange for other seemingly more advanced methods methods like drop, take.

def nth[A](n: Int, l: List[A]): Option[A] = if(n < 0 || n >= l.length) None else Some(l(n))

I understand that using () defeats the purpose of the exercise, but it seems like drop, take etc., do the same thing? What do you guys think? (At the same time, if you never use other List methods, almost every exercise would be some kind of tail recursion)

​

[Harit Himanshu]

Thank you all for your thoughts, this is really helpful.

@Jaret, I am following the advice from the S99 webpage

Some of the (easy) problems can be trivially solved using built-in functions. However, in these cases, you learn more if you try to find your own solution.

So, while learning how to do that using built-in functions is great (because that is what we do when using production code), using them while learning a new language may not help much (just my 2 cents)

I would however, like to read more from experienced developers who have gone through this path.

Thank you all again