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

Answer 1

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.