Issues with maps and their entries in Scala

Question

I have a recursive function that takes a Map as single parameter. It then adds new entries to that Map and calls itself with this larger Map. Please ignore the return values for now. The function isn't finished yet. Here's the code:

def breadthFirstHelper( found: Map[AIS_State,(Option[AIS_State], Int)] ): List[AIS_State] = {
  val extension =
   for( 
     (s, v) <- found; 
     next <- this.expand(s) if (! (found contains next) )
   ) yield (next -> (Some(s), 0))

  if ( extension.exists( (s -> (p,c)) => this.isGoal( s ) ) )
    List(this.getStart)
  else
    breadthFirstHelper( found ++ extension )
}

In extension are the new entries that shall get added to the map. Note that the for-statement generates an iterable, not a map. But those entries shall later get added to the original map for the recursive call. In the break condition, I need to test whether a certain value has been generated inside extension. I try to do this by using the exists method on extension. But the syntax for extracting values from the map entries (the stuff following the yield) doesn't work.

Questions:

1. How do I get my break condition (the boolean statement to the if) to work?

2. Is it a good idea to do recursive work on a immutable Map like this? Is this good functional style?

Answer 1

When using a pattern-match (e.g. against a Tuple2) in a function, you need to use braces {} and the case statement.

if (extension.exists { case (s,_) => isGoal(s) } )

The above also uses the fact that it is more clear when matching to use the wildcard _ for any allowable value (which you subsequently do not care about). The case xyz gets compiled into a PartialFunction which in turn extends from Function1 and hence can be used as an argument to the exists method.

As for the style, I am not functional programming expert but this seems like it will be compiled into a iterative form (i.e. it's tail-recursive) by scalac. There's nothing which says "recursion with Maps is bad" so why not?

Note that -> is a method on Any (via implicit conversion) which creates a Tuple2 - it is not a case class like :: or ! and hence cannot be used in a case pattern match statement. This is because:

val l: List[String] = Nil
l match {
  case x :: xs =>
}

Is really shorthand/sugar for

case ::(x, xs) =>

Similarly a ! b is equivalent to !(a, b). Of course, you may have written your own case class ->...

Note2: as Daniel says below, you cannot in any case use a pattern-match in a function definition; so while the above partial function is valid, the following function is not:

(x :: xs) =>

Answer 2

This is a bit convoluted for me to follow, whatever Oxbow Lakes might think.

I'd like first to clarify one point: there is no break condition in for-comprehensions. They are not loops like C's (or Java's) for.

What an if in a for-comprehension means is a guard. For instance, let's say I do this:

for {i <- 1 to 10
     j <- 1 to 10
     if i != j
} yield (i, j)

The loop isn't "stopped" when the condition is false. It simply skips the iterations for which that condition is false, and proceed with the true ones. Here is another example:

for {i <- 1 to 10
     j <- 1 to 10
     if i % 2 != 0
} yield (i, j)

You said you don't have side-effects, so I can skip a whole chapter about side effects and guards on for-comprehensions. On the other hand, reading a blog post I made recently on Strict Ranges is not a bad idea.

So... give up on break conditions. They can be made to work, but they are not functional. Try to rephrase the problem in a more functional way, and the need for a break condition will be replaced by something else.

Next, Oxbow is correct in that (s -> (p,c) => isn't allowed because there is no extractor defined on an object called ->, but, alas, even (a :: b) => would not be allowed, because there is no pattern matching going on in functional literal parameter declaration. You must simply state the parameters on the left side of =>, without doing any kind of decomposition. You may, however, do this:

if ( extension.exists( t => val (s, (p,c)) = t; this.isGoal( s ) ) )

Note that I replaced -> with ,. This works because a -> b is a syntactic sugar for (a, b), which is, itself, a syntactic sugar for Tuple2(a, b). As you don't use neither p nor c, this works too:

if ( extension.exists( t => val (s, _) = t; this.isGoal( s ) ) )

Finally, your recursive code is perfectly fine, though probably not optimized for tail-recursion. For that, you either make your method final, or you make the recursive function private to the method. Like this:

final def breadthFirstHelper

or

def breadthFirstHelper(...) {
  def myRecursiveBreadthFirstHelper(...) { ... }
  myRecursiveBreadthFirstHelper(...)
}

On Scala 2.8 there is an annotation called @TailRec which will tell you if the function can be made tail recursive or not. And, in fact, it seems there will be a flag to display warnings about functions that could be made tail-recursive if slightly changed, such as above.

EDIT

Regarding Oxbow's solution using case, that's a function or partial function literal. It's type will depend on what the inference requires. In that case, because that's that exists takes, a function. However, one must be careful to ensure that there will always be a match, otherwise you get an exception. For example:

scala> List(1, 'c') exists { case _: Int => true }
res0: Boolean = true

scala> List(1, 'c') exists { case _: String => true }
scala.MatchError: 1
        at $anonfun$1.apply(<console>:5)
        ... (stack trace elided)    

scala> List(1, 'c') exists { case _: String => true; case _ => false }
res3: Boolean = false

scala> ({ case _: Int => true } : PartialFunction[AnyRef,Boolean])
res5: PartialFunction[AnyRef,Boolean] = <function1>

scala> ({ case _: Int => true } : Function1[Int, Boolean])
res6: (Int) => Boolean = <function1>

EDIT 2

The solution Oxbow proposes does use pattern matching, because it is based on function literals using case statements, which do use pattern matching. When I said it was not possible, I was speaking of the syntax x => s.