CODEWITHSUNDEEP
listscalapattern-matching
Tom
Tom

Reputation: 45104

Finding next element in List using pattern matching

I'm playing with Scala pattern matching, trying to make a findNext function:

findNext(1,List(1,2,3)) == 2
findNext(2,List(1,2,3)) == 3
findNext(3,List(1,2,3)) == 1

def findNext(needle : Int, haystack : List[Int]): Int = {
    haystack match {
       case Nil => /* handle it */
       case needle::Nil => needle
       case front::needle::back => back.head
       case needle::back::Nil => back.head
    }
}

I can make it work for only for the trivial case.

Can this be done using pattern matching? I know I can make it work using methods in list, but this is just a toy program.

Upvotes: 0

Views: 652

Answers (3)

senia
senia

Reputation: 38045

def findNext(needle : Int, haystack : List[Int]): Option[Int] = {
  @annotation.tailrec def loop(needle : Int, haystack : List[Int], trueHead: Int): Option[Int] =
    haystack match {
      case Nil => None
      case `needle` :: next :: _ => Some(next)
      case `needle` :: Nil => Some(trueHead)
      case _ :: tail => loop(needle, tail, trueHead)
    }
  haystack match {
    case Nil | _ :: Nil => None
    case _ => loop(needle, haystack, haystack.head)
  }
}

See this answer for back ticks in pattern matching.

Usage:

scala> findNext(1,List(1,2,3))
res0: Option[Int] = Some(2)

scala> findNext(2,List(1,2,3))
res1: Option[Int] = Some(3)

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

scala> findNext(4,List(1,2,3))
res3: Option[Int] = None

scala> findNext(1,List(1,1))
res4: Option[Int] = Some(1)

scala> findNext(1,List(1))
res5: Option[Int] = None

scala> findNext(1,List())
res6: Option[Int] = None

Upvotes: 3

Alex Yarmula
Alex Yarmula

Reputation: 10667

Since the needle may not be found, it's best to return an Option[Int] here. Using just the pattern matching, you can solve it with:

@tailrec def findNext(needle: Int, haystack: List[Int]): Option[Int] = {
    haystack match {
      case Nil => None
      case front::next::back if front == needle => Some(next)
      case head::tail => findNext(needle, tail)
    }
  }

Or even simpler:

  @tailrec def findNext(needle: Int, haystack : List[Int]): Option[Int] = {
    haystack match {
      case Nil => None
      case head::tail if head == needle => tail.headOption
      case head::tail => findNext(needle, tail)
    }
  }

Note that this returns None if no matches were found in the haystack, unlike your example above. The result of the function could then be combined with the default answer, like so:

val haystack = List(1,2,3,4)
findNext(4, haystack) getOrElse haystack.head

Upvotes: 2

Brian
Brian

Reputation: 20285

This circles back to the head of the original haystack if the last element is the needle with the help of if conditionals. The findNextR holds the saved value for the case where the last element is the needle. 

def findNext(needle: Int, haystack: List[Int]): Option[Int]  =  {
  @annotation.tailrec def findNextR(needle: Int, haystack: List[Int], savedHead: Int): Option[Int]  =  {
    haystack match{
      case Nil => None
      case head :: tail => if (head == needle && tail.isEmpty) Some(savedHead)
                                   else if (head == needle) Some(tail.head)
                                   else findNextR(needle, tail, savedHead)
    }
  }
 findNextR(needle, haystack, haystack.head)
}

scala> :load findNext.scala
Loading findNext.scala...
findNext: (needle: Int, haystack: List[Int])Option[Int]

scala> findNext(1, List(1,2,3))
res0: Option[Int] = Some(2)

scala> findNext(2, List(1,2,3))
res1: Option[Int] = Some(3)

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

Upvotes: 1

Related Questions