Scala - for : type mismatch

Question

Here is the structure : - Points - Segments - Paths

case class Point(name: String, x: Long, y: Long)

case class Segment(from: Point, to: Point)

case class Path(segments: Vector[Segment])

I'm trying to find all the possibles paths from a list of segments available to join two points (from and to). Here is my function :

def allPossiblePaths(segments: Vector[Segment], from: Point, to: Point) : Option[Vector[Path]] = {

    if (from == to) Option(Vector())

    for {
      segment <- segments.filter(segment => segment.from == from)
      nextSegment <- segments.filter(segmentSuivant => segmentSuivant.from == segment.to)
      if nextSegment.to != segment.from
    } yield allPossiblePaths(segments.filter(segment => segment.from == from) ,segment.to, nextSegment.to)


  }

If I try :

allPossiblePaths(topSegments, tl, tr)

with :

val tl = Point("tl", 0, -10)
  val t  = Point("t", 0, 0)
  val tr = Point("tr", 0, 10)


  // tl - t - tr
  //  |   |    |
  // bl - b --- br


  // Segments

  val tlt     = Segment(tl, t)
  val tlbl     = Segment(tl, bl)
  val tb     = Segment(t, b)
  val ttr     = Segment(t, tr)      

  val topSegments = Vector(tlt, ttr, bbr)

I have this error :

 Error:(63, 15) type mismatch;
 found   : scala.collection.immutable.Vector[Option[Vector[chemins.Path]]]
 required: Option[Vector[chemins.Path]]
      segment <- segments.filter(segment => segment.from == from)

But when I do

for {
          segment <- segments.filter(segment => segment.from == from)
}

I am using the for on a Vector[Segment] so I don't understand why the "scala.collection.immutable.Vector" appears

Thanks in advance !

Edit 1

Introduced a class "PathList" :

case class PathList(paths: Vector[Path])

Changed the code adding the "else" and "some"

  def allPossiblePaths(segments: Vector[Segment], from: Point, to: Point) : Option[PathList] = {

    if (from == to) Some(PathList(Vector()))

    else {

      for {
        segment <- segments.filter(segment => segment.from == from)
        nextSegment <- segments.filter(segmentSuivant => segmentSuivant.from == segment.to)
        if nextSegment.to != segment.from
      } yield allPossiblePaths(segments.filter(segment => segment.from == from), segment.to, nextSegment.to)

    }


  }

The error hasn't really changed :

Error:(65, 17) type mismatch;
 found   : scala.collection.immutable.Vector[chemins.PathList]
 required: chemins.PathList
        segment <- segments.filter(segment => segment.from == from)

Edit 2

Tried to not specify the type of return and it does compile

def allPossiblePaths( segments: Vector[Segment], from: Point, to: Point) {

    if (from == to) Path(Vector())

    else {

      for {
        segment <- segments.filter(segment => segment.from == from)
        nextSegment <- segments.filter(segmentSuivant => segmentSuivant.from == segment.to)
        if nextSegment.to != segment.from
      } yield allPossiblePaths(segments.filter(segment => segment.from == from), segment.to, nextSegment.to)
    }

  }

it returns :

Expected :Some(Path(Vector(Segment(Point(tl,0,-10),Point(t,0,0)), Segment(Point(t,0,0),Point(b,10,0)), Segment(Point(b,10,0),Point(br,10,20)))))
Actual   :<(), the Unit value>

Well the result it's not what what I'm expecting but it's something I guess

segments is a Vector, so after the filter you will still get a Vector. Also it seems you missed the else in if (and it might be better to express the intent to return Some(Vector()) in the then part of if without using Option#apply.) — Gábor Bakos
I was not expecting change (the second part was really just a comment), just tried to explain why you get a Vector and not an Option. Not sure why you want Option, what it should mean. — Gábor Bakos
I wanted an Option to handle the stop when the recursive function returns an EmptyPath or a None. But I could be poorly doing — François Bourrée

Adam Fraser Adam Fraser · Accepted Answer · 2018-11-05T19:06:46

I think sometimes it can be helpful to generalize a bit when solving these kinds of problems. Consider the function below:

def pathsFrom[S, A](z: S)(f: S => Stream[(S, A)]): Stream[(S, List[A])] = {

  def go(initial: Stream[(S, List[A], Set[S])]): Stream[(S, List[A])] =
    initial match {
      case (s, as, explored) #:: tail =>
        val neighbors = f(s)
        val newNeighbors = neighbors
          .filter { case (s, _) => !explored.contains(s) }
          .map { case (s, a) => (s, a :: as, explored + s) }
        ((s, as)) #:: go(tail #::: newNeighbors)
      case _ => Stream.empty
    }

  go(Stream((z, Nil, Set(z))))
}

This embodies a generalized algorithm that starts with some initial state S and a transition function f that given a state S returns a Stream[(S, A)] of all states S immediately reachable from that state along with the associated moves A. It then returns a Stream[(S, List[A])] of all paths from the initial state and the associated final states.

In your case, the initial state would be the starting point and you could write the transition function like so:

def next(point: Point)(segments: List[Segment]): Stream[(Point, Segment)] =
  segments.filter(_.from == point).map(segment => (segment.to, segment)).toStream

You could then just filter for states ending at your desired end point:

pathsFrom(tl)(next(_)(segments))
  .filter(_._1 == br)
  .map(_._2.reverse)
  .toList
  .foreach(println)

Assuming the six points as you described and segments going from top to bottom and left to right between adjacent points, this would return:

List(Segment(Point(tl,0,-10),Point(t,0,0)), Segment(Point(t,0,0),Point(tr,0,10)), Segment(Point(tr,0,10),Point(br,-10,10)))
List(Segment(Point(tl,0,-10),Point(t,0,0)), Segment(Point(t,0,0),Point(b,-10,0)), Segment(Point(b,-10,0),Point(br,-10,10)))
List(Segment(Point(tl,0,-10),Point(bl,-10,-10)), Segment(Point(bl,-10,-10),Point(b,-10,0)), Segment(Point(b,-10,0),Point(br,-10,10)))

In other words, to get from top left to bottom right we can go right / right / down, right / down / right, or down / right / right.

Scala - for : type mismatch

1 Answers