I'm coming from a Python-heavy background and trying to learn Scala through a basic "Design a Parking Lot" exercise. I have Scala code that looks something like:

class ParkingLot(spaces: Set[ParkingSpace]) {
    var openSpaces: Set[ParkingSpace] = spaces;
    var usedSpaces: Set[ParkingSpace] = Set()

    def assign(vehicle: Vehicle): Boolean = {
        var found = false;
        for (s <- openSpaces) {
            (s.isCompatibleWithVehicle(vehicle)) match {
                case true => {
                    if (!found) {
                        s.acceptVehicle(vehicle)
                        openSpaces -= s
                        usedSpaces  = s
                        found = true
                    }
                }

                case _ => {}
            }
        }

        found
    }
}

The logic is pretty simple - I have a ParkingLot with Sets of open and occupied ParkingSpaces. I want to define a function assign that takes in a Vehicle, loops through all the openSpaces and if it finds an available space, will update the open and used spaces. I'm having a hard time coming up with a good idiomatic way to do this. Any thoughts and suggestions about how to reframe questions into a Scala mindset?

CodePudding user response：

The main problem with this code is use of mutable state (var). Rather than changing an existing object, functional code creates new, modified objects. So the functional approach is to create a new ParkingLot each time with the appropriate allocation of spaces.

case class ParkingLot(open: Set[ParkingSpace], used: Set[ParkingSpace])
{
  def assignVehicle(vehicle: Vehicle): Option[ParkingLot] =
    open.find(_.isCompatibleWithVehicle(vehicle)).map { space =>
      ParkingLot(open - space, used   space.acceptVehicle(vehicle))
    }
}

assignVehicle can return a new parking lot with the spaces appropriately updated. It returns an Option because there might not be a compatible space, in which case it returns None. The caller can take whatever action is necessary in this case.

Note that ParkingSpace now as an acceptVehicle that returns a new ParkingSpace rather than modifying itself.

CodePudding user response：

As also the answer by @Tim mentioned, you need to avoid mutations, and try to handle this kind of state managements in functions. I'm not gonna dive into the details since Tim mentioned some, I'm just proposing a new approach to the implementation, which uses a map of spaces to weather they're used, and returns a new (not optional) instance every time you assign a new vehicle (if the vehicle fits in, updated instance is returned, and if not, the same instance):

class ParkingLot(spaces: Map[ParkingSpace, Boolean]) {

  def withVehicleAssigned(vehicle: Vehicle): ParkingLot = 
    spaces.collectFirst {
      case (space, used) if !used && space.isCompatibleWithVehicle(vehicle) => 
        new ParkingLot(spaces.updated(space, true))
    }.getOrElse(this) 

}

Almost the same process goes for removing vehicles, the usage would be something like this:

parkingLot
  .withVehicleAssigned(v1)
  .withVehicleAssigned(v2)
  .withVehicleRemoved(v1)

CodePudding user response：

Since most answers already explained the importance of immutability and creating new objects, I am just going to propose two alternative models and solutions.

1. Using a queue of empty spaces plus a set of used ones.

final case class ParkingLot(freeSpaces: List[ParkingSpace], occupiedSpaces: Set[ParkingSpace]) {
  // Returns the used space and the new parking lot.
  // An option is used since the parking lot may be full.
  def assign(vehicle: Vehicle): Option[(ParkingSpace, ParkingLot)] =
    freeSpaces match {
      case freeSpace :: remainingSpaces =>
        val usedSpace = freeSpace.withVehicle(vehicle)
        Some(copy(freeSpaces = remainingSpaces, usedSpaces = usedSpace   usedSpaces))

      case Nil =>
        None
    }
}

2. Using a List[(ParkingSpace, Boolean)] and a tail-recursive function.

final case class ParkingLot(parkingSpaces: List[(ParkingSpace, Boolean)]) {
  // Returns the used space and the new parking lot.
  // An option is used since the parking lot may be full.
  def assign(vehicle: Vehicle): Option[(ParkingSpace, ParkingLot)] = {
    @annotation.tailrec
    def loop(remaining: List[(ParkingSpace, Boolean)], acc: List[(ParkingSpace, Boolean)]): Option[(ParkingSpace, List[(ParkingSpace, Boolean)])] =
      remaining match {
        case (parkingSpace, occupied) :: tail =>
          if (occupied) loop(remaining = tail, (parkingSpace, occupied) :: acc)
          else {
            val usedSpace = parkingSpace.withVehicle(vehicle)
            val newSpaces = acc reverse_::: ((usedSpace -> true) :: tail)
            Some(usedSpace -> newSpaces)
         }

        case Nil =>
          None
      }

    loop(remaining = parkingSpaces, acc = List.empty).map {
      case (usedSpace, newSpaces) =>
        usedSpace -> copy(newSpaces)
    }
  }
}

Note, the boolean may be redundant since the ParkingSpace should be able to tell us if it is empty or not.

CodePudding user response：

Ideally, to go fully functional, what you should always strive for is immutability. To achieve it, always keep in mind 2 main ideas:

1. Avoid mutable (var) variables in your object - this gives your object mutable state - which is exactly the opposite of what immutability means.
2. Avoid impure methods (methods with side-effects) - these alter the behavior of your object and can possibly make it nondeterministic.

Based on these, there are 2 design issues in your program that must be eliminated: the 2 mutable Set variables, and the impure method assign which has the side effect of changing the contents of your mutable variables while returning a different result.

You should return a new object when you want to change it's state. Here's an idea: convert your mutable variables into immutable fields - they can be private so as to not be available outside, and whenever you want to assign an open space to a car, simply return a new object with the new state:

  class ParkingLot(
      private val openSpaces: Set[ParkingSpace],
      private val usedSpaces: Set[ParkingSpace]
  ) {

    def findFirstAvailableSpace(v: Vehicle): Option[ParkingSpace] =
      openSpaces.find(s => s.isCompatibleWithVehicle(v))

    def assign(v: Vehicle): ParkingLot =
      findFirstAvailableSpace(v)
        .map(s => s.acceptVehicle(v))
        .map(s => new ParkingLot(openSpaces.excl(s), usedSpaces.incl(s)))
        .getOrElse(this)
  }

Note that s.acceptVehicle(v) has to result in the same parking space or this instance, or the newly used space will not be excluded from openspaces when assigning a new vehicle to the parking lot. This hints that if you want your whole design immutable (including ParkingSpace), then ParkingSpace will have to be changed to create a new object when it accepts a vehicle, and ParkingLot's space fields will have to rely on checking some other property of the ParkingSpace object to know if a parking space is available or not.

You will say ok but - how do I know if I assigned an open space to that car or not ? There are multiple ways to find out. Either check the usedSpaces field, either include that field in your toString and print it, or, just don't use assign before checking isSpaceAvailable:

  def isSpaceAvailable(v: Vehicle): Boolean = 
    openSpaces.exists(s => s.isCompatibleWithVehicle(v))

    override def toString: String =
      s"openSpaces: ${openSpaces.size} usedSpaces: ${usedSpaces.size}"

If isSpaceAvailable is true, definitely assign will succeed. But the interesting part is you don't even have to know if the space was used or not, because if it was not used, you returned back this, as if nothing happened, and your object becomes chainable, and can take as many cars as you want. For example, I can give it 3 cars, even if it has only 2 open spaces:

  val pl = new ParkingLot(
    Set(new ParkingSpace(), new ParkingSpace()),
    Set.empty[ParkingSpace]
  )
  val newpl = pl.assign(new Vehicle).assign(new Vehicle).assign(new Vehicle)
  println(pl)             // openSpaces: 2 usedSpaces: 0
  println(newpl)          // openSpaces: 0 usedSpaces: 2

Nothing happened with the third car, because there was no space left for it. So isSpaceAvailable becomes just an utility method, since you don't really need it. Your requirements matter here a lot: maybe you don't want your clients to try assigning cars without checking if there is space inside the parking lot. In that case, you should force them to check isSpaceAvailable first, otherwise face the consequences of throwing an exception on the getOrElse part of the assign method, when they call assign while the park lot is full.

In the end, worth mentioning is that the important aspect functional programming must have to work properly is referential transparency (have deterministic behavior), which is mainly achieved when your objects are immutable. But they don't have to obey the immutability rules from top to bottom, as long as they are referentially transparent.

Here's a counterexample: an object that stores a mutable cache to avoid recalculating some computationally intensive values - is still considered immutable because it still has referential transparency: given the same value to recalculate, it will always return the same result (only faster starting from the second time). So even though, it has a mutable variable (the cache) and side effects (the cache will be updated if a value that was not previously in the cache is calculated and inserted into the cache before being returned) it is still considered an immutable object.