CODEWITHSUNDEEP
arraysscalafunctional-programmingscala-collectionsiterable
Joyoyoyoyoyo
Joyoyoyoyoyo

Reputation: 165

No var or breakable: How to "break" when a predicate is met, in an array traversal?

How would I write this programming logic into a functional method signature? I am attempting to loop/traverse an array until a condition is met, then break upon that condition. I'm mostly trying my best to avoid var and breakable from scala.util.control.Breaks. It makes use of a closure, in this case, dictionary, to check if a condition/predicate is met. The idea is that I am looping through an array until the predicate is met. I'm also avoiding converting my array to list. Would use of an array not allow me to splice the array, for example, to do pattern matching? 

val dictionary = Array.fill(128)(false)

def isUnique(array: Array[Char]): Option[Char] = {

  // traverse each element of the array {
  //     if a character.toInt is in the dictionary, insert into dictionary 
  //        exit loop, with the character which broke the loop
  //     else
  //        set dictionary(character.toInt) to true and continue looping
  // }
}

Here's an example use case:

val word = "abcdefggghijklmnopqrstuvqxyz".toArray
val charThatBrokeIt = isUnique(word)

Edit: Feel free to suggest or propose other return types as well, such as a Boolean, Tuple, Case Class, or any others. Option[Char] might not be a good resultant value on my part. For example. I may have returned false in the case that loop broke out early (short-circuited) or not.

Upvotes: 2

Views: 205

Answers (2)

Karl Bielefeldt
Karl Bielefeldt

Reputation: 49128

First, a String already acts like a collection, so you should just use String instead of Array[Char]. Second, you can take advantage of laziness to allow short-circuiting while still splitting the algorithm into parts, using .view.

def breaksUnique(word: String): Option[Char] = {
  val cumulativeSets = word.view.scanLeft(Set.empty[Char]){_ + _}
  val zipped = cumulativeSets zip word
  val nonDupsDropped = zipped dropWhile {case (set, char) => !(set contains char)}
  nonDupsDropped.map{_._2}.headOption
}

The first two lines are written as if they process the entire word, but because they operate on a view, they are only calculated as needed.

cumulativeSets is a sequence of sets of every character that has been seen up to that point. If you ran it on "abb", you would get Set(), Set(a), Set(a,b), Set(a,b). That is combined with the original word using zip, giving (Set(),a), (Set(a),b), (Set(a,b),b). We then just have to drop all the pairs where the character doesn't appear in the set, then return the first element that wasn't dropped.

Upvotes: 1

jwvh
jwvh

Reputation: 51271

Early breakout always suggests recursion.

def isUnique(array: Array[Char]): Option[Char] = {
  def getDup(index: Int, acc: Set[Char]): Option[Char] =
    if (array.isDefinedAt(index))
      if (acc(array(index))) Some(array(index))
      else getDup(index+1, acc + array(index))
    else None
  getDup(0, Set.empty[Char])
}

Usage:

val word = "abcdefggghijklmnopqrstuvqxyz".toArray
val charThatBrokeIt = isUnique(word)
//charThatBrokeIt: Option[Char] = Some(g)

Upvotes: 1

Related Questions