Help making lazy sequence

Question
1

I hope someone can help me refactor this code to make it work lazily.

I have a tail recursive function which is effectively two concentric flatMaps. The loop (recursion) proceeds, until such time as some generated element meets a certain condition, found. My implementation of the function works, but is not ideal. I’d really like to only generate elements until I find a match, and I fear that the flatMap of flatMap could in some cases generate very large lists.

Can someone help me refactor this so that it works lazily?

As I see it recure(routings flatMap extendRouting) iterates over the entire routings list, and only thereafter checks whether any of the items generated matches the found predicate. I can’t check the found predicate inside function extendRouting because I don’t know how to return from wishToBeLazy as soon as found returns true.

I feel like the call to find would like iterate across routings and routings be generated lazily. If find finds nothing, then test to see whether an empty list was generated, and if not make the recursive call again. But I don’t know how to do that.

I’d appreciate any clue or suggestion.

object LazyMetro {

  type Station = Int
  type Time = Int
  type Leg = (Station,Station,Time)
  case class Routing(path:List[Leg], stations:Set[Station]) {
    assert (path != Nil) // I never will consider empty paths
    val currentStation = path match {
      case leg :: _ => leg._2
    }
  }

  def wishToBeLazy(initial:List[Routing], legData:List[Leg], skip:Leg=>Boolean, found:Routing=>Boolean):Option[Routing] = {
    val metroAdj = legData groupBy (_._1)

    def extendRouting(routing: Routing): List[Routing] = {
      metroAdj(routing.currentStation) flatMap {
        leg: Leg => {
          leg match {
            case leg if skip(leg) => Nil
            case (_, dst, _) => List(Routing(leg::routing.path,routing.stations+dst))
          }
        }
      }
    }

    def recure(routings: List[Routing]): Option[Routing] = {
      if (routings == Nil)
        None
      else {
        val augmenting = routings find found

        augmenting match {
          case Some(_) => augmenting
          case None => recure(routings flatMap extendRouting)
        }
      }
    }

    recure(initial)
  }
}

P.S., I did consider changing extendRouting to test the found function on each element generated, return an Either type indicating the lucky element, or list list of objects, none of which match the predicate. I’m not sure whether that approach is more or less obscure than the lazy approach.

2

I’m not sure if it solves your problem, but you could try using a view of the list, which makes operations like flatMap on the list lazy.

import scala.collection.SeqView
def recure(routings: SeqView[Routing, Seq[_]]): Option[Routing] = {
    ...
}
recure(initial.view)
3

That’s an interesting clue. But what I can’t see is how to lazily generate items later in the sequence which are functions of items earlier in the sequence. E.g., if x is in the sequence then I always (but later) want some or all elements returned by extendRouting(x) to occur later in the sequence. I.e., any elements of extendRouting(x) up to when one of them satisfies the predicate found.

I could get the same effect, if there was a way for a local function to return from the parent function. This is done in Common Lisp with return-from, and as I recall it is done in CaML using Exception, but I have forgotten the details.

This would avoid the issue with laziness, and simply let me detect a sort-circuit element, and abort the iteration early.

  def outer(x):Option[A] = {
    def inner(y): List[A] = {
      y flatMap {
        z => {
          if (some-condition)
             return-from outer Some(a)
          else if (second-condition)
             List(a)
          else
             Nil
        }
      }
    }
    inner(start)
      ...
  }
4

The same sort of short-circuiting can be done by throwing an Exception and catching it in the outer scope. (I can’t say I like that answer, and there may well be a better one, but just FYI…)

5

I’ve refactored the code to use Either. I don’t find it as elegant, but it seems to do what I want. I had to remove the call to flatMap :disappointed:and rewrite using ++ and tail recursion.

    def extendPath(path:Path,predicate:Path=>Boolean):Either[Path,List[Path]] = {
      // Left(path) means we found a path of length n that matches the predicate
      // Right(paths) means we are expanding to the paths of length n+1
      val found = path.nonLoopingExtensions find predicate
      found match {
        case Some(path) => Left(path)
        case None => Right(path.nonLoopingExtensions)
      }
    }

    def extendPaths(paths:List[Path],extended:List[Path],predicate:Path=>Boolean):Option[Path] = {
      (paths,extended) match {
        case (Nil,Nil) => None
        case (Nil,_) => extendPaths(extended,Nil,predicate)
        case (path::tail,_) => {
          extendPath(path,predicate) match {
            case Left(path) => Some(path)
            case Right(paths) => extendPaths(tail,extended ++ paths,predicate)
          }
        }
      }
    }
    def findPath(vertex:A,predicate:Path=>Boolean):Option[Path] = {
      extendPaths(List(Path(List(vertex))),Nil,predicate)
    }