CODEWITHSUNDEEP
scalatail-recursion
seas
seas

Reputation: 23

scala: make a function tail recursive

I have the following function in scala:

def is_in[T](e: T, as: List[T]) : Boolean = as match
{
  case Nil => false;
  case x::xs => e == x || is_in(e, xs);
}

Now I want to make this function tail recursive. My idea is the following:

// tail recursive:

def is_in[T](e: T, as:List[T]) : Boolean =
{
  @tailrec
  def is_in_tailrec[T](e: T, as:List[T], acc: Boolean) : Boolean =
  {
    as match
    {
      case Nil => acc;
      case x::xs => is_in_tailrec(... here I got stuck ...);
    }
  }
  is_in_tailrec(e, as, 1);
}

Could someone please give me an advice how I can make this function tail recursive?

Upvotes: 1

Views: 258

Answers (4)

Dmytro Mitin
Dmytro Mitin

Reputation: 51703

I wonder why the one who posted the answer with the helper method which was similar to my version deleted his post. I just wanted to analyse that and see what my mistakes are ...

I guess you meant

def is_in[T](e: T, as: List[T]) : Boolean = {
  @tailrec
  def is_in_tailrec[T](e: T, as: List[T], acc: Boolean): Boolean = as match {
    case Nil     => acc
    case x :: xs => is_in_tailrec(e, xs, e == x || acc)
  }

  is_in_tailrec(e, as, false)
}

Since T and e in is_in_tailrec are always the same as T and e in is_in, this can be rewritten as

def is_in[T](e: T, as: List[T]) : Boolean = {
  @tailrec
  def is_in_tailrec(as: List[T], acc: Boolean): Boolean = as match {
    case Nil     => acc;
    case x :: xs => is_in_tailrec(xs, e == x || acc)
  }

  is_in_tailrec(as, false)
}

Upvotes: 0

Tim
Tim

Reputation: 27421

Your function is already tail recursive. If you mark it as @annotation.tailrec it compiles just fine.

Upvotes: 2

Dmitry Reutov
Dmitry Reutov

Reputation: 3032

my suggestion is

{
    case Nil => acc
    case _ if acc => acc
    case x :: xs => is_in_tailrec(e, xs, x == e)
}

or may be even

{
    case x :: xs if !acc => is_in_tailrec(e, xs, x == e)
    case _ => acc
}

Upvotes: 0

Duelist
Duelist

Reputation: 1572

Actually you don't need the helper method with accumulator here. Just check if e == x returns false, then call the method with the rest of the list, otherwise return true:

  def is_in[T](e: T, as: List[T]): Boolean = as match {
    case Nil => false
    case x :: _ if e == x => true
    case _ :: xs => is_in(e, xs)
  }

Upvotes: 5

Related Questions