Tuesday, July 10, 2012

Find the common basename (prefix) in a collection of String

Not tail recursive implementation

  def basename(names:Iterable[String]):Option[String] = {
    if (names.exists(_.size==0) || names.size<=1) None
    else {
      val firsts = names.map(_.head)
      if (firsts.toSet.size>1) None
      else {
        Some(firsts.head.toString+basename(names.map(_.tail)).getOrElse(""))
      }
    }
  }

Tail recursive implementation

  @annotation.tailrec
  def basename(names:Iterable[String], accu:Option[String]=None):Option[String] = {
    if (names.exists(_.size==0) || names.size<=1) accu
    else {
      val firsts = names.map(_.head)
      if (firsts.toSet.size>1) accu
      else basename(names.map(_.tail), Some(accu.getOrElse("")+firsts.head))
    }
  }

Usage example

$ scala
Welcome to Scala version 2.9.2 (Java HotSpot(TM) 64-Bit Server VM, Java 1.6.0_33).
Type in expressions to have them evaluated.
Type :help for more information.

scala> :paste
// Entering paste mode (ctrl-D to finish)

  @annotation.tailrec
  def basename(names:Iterable[String], accu:Option[String]=None):Option[String] = {
    if (names.exists(_.size==0) || names.size<=1) accu
    else {
      val firsts = names.map(_.head)
      if (firsts.toSet.size>1) accu
      else basename(names.map(_.tail), Some(accu.getOrElse("")+firsts.head))
    }
  }

// Exiting paste mode, now interpreting.

basename: (names: Iterable[String], accu: Option[String])Option[String]

scala> basename(List("trucmuche", "trucmoche", "trucduq"))
res0: Option[String] = Some(truc)

scala> basename(List("was1", "was2"))
res1: Option[String] = Some(was)

scala> basename(List("was1"))
res2: Option[String] = None

Of course if we annotate with @tailrec the not tail recursive implementation we got the following error :
scala> :paste
// Entering paste mode (ctrl-D to finish)

@annotation.tailrec
def basename(names:Iterable[String]):Option[String] = {
    if (names.exists(_.size==0) || names.size<=1) None
    else {
      val firsts = names.map(_.head)
      if (firsts.toSet.size>1) None
      else {
        Some(firsts.head.toString+basename(names.map(_.tail)).getOrElse(""))
      }
    }
  }

// Exiting paste mode, now interpreting.

:15: error: could not optimize @tailrec annotated method basename: it contains a recursive call not in tail position
               Some(firsts.head.toString+basename(names.map(_.tail)).getOrElse(""))

No comments:

Post a Comment