Scala

Question

结构如下： - 积分 - 细分 - 路径

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

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

case class Path(segments: Vector[Segment])

我正在尝试从可用于连接两点（从和到）的线段列表中找到所有可能的路径。这是我的功能：

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)


  }

如果我尝试：

allPossiblePaths(topSegments, tl, tr)

与：

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)

我有这个错误：

 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)

但是当我这样做时

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

我在 Vector[Segment] 上使用 for，所以我不明白为什么会出现 "scala.collection.immutable.Vector"

提前致谢！

编辑 1

介绍了一个 class "PathList" :

case class PathList(paths: Vector[Path])

更改了添加 "else" 和 "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)

    }


  }

错误并没有真正改变:

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

编辑 2

试图不指定 return 的类型，但确实编译了

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)
    }

  }

它 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>

嗯，结果不是我所期待的，但我猜是这样

Answer 1

我认为有时在解决这类问题时进行一些概括会很有帮助。考虑以下函数：

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))))
}

这体现了一个从一些初始状态 S 开始的广义算法和一个给定状态 S returns a Stream[(S, A)] 的转换函数 f在所有状态中 S 可以从该状态立即到达以及相关移动 A。然后 return 是从初始状态到相关最终状态的所有路径的 Stream[(S, List[A])]。

在您的情况下，初始状态将是起点，您可以像这样编写转换函数：

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

然后您可以只筛选以您想要的终点结束的州：

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

假设您描述的六个点和相邻点之间从上到下和从左到右的线段，这将 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)))

换句话说，要从左上角到右下角，我们可以向右/向右/向下，向右/向下/向右，或向下/向右/向右。

Scala - 对于：类型不匹配

Scala - for : type mismatch

for-loop

type-mismatch