实现DISTINCT以便理解

Question

在他的Coursera课程的倒数第二次讲座中,奥德斯基教授提供了以下for理解作为可爱案例研究的最后一步:

def solutions(target: Int): Stream[Path] =
  for {
    pathSet <- pathSets
    path <- pathSet
    if path.endState contains target
  } yield path

在之前的一次演讲中,他在for理解和SQL 之间进行了一些类比.

我正在寻找的yield只是那些path拥有一个DISTINCT endState.

有没有办法从相同理解的过滤条款中回溯到已经产生的项目？

另一种方法可能是转换pathSets到Map从endState到path了之前for的语句,然后将其转换回一个Stream返回之前.但是,这似乎失去了使用a的懒惰计算好处Stream.

同一个案例研究的早期方法实现了类似的目标,但它已经是一个递归函数,而这个函数(似乎)不需要递归.

看起来我可以使用mutable Set来跟踪endState得到的s,但是感觉不满意,因为到目前为止该课程已成功避免使用可变性.

Answer 1

有没有一种方法可以从具有相同理解的过滤子句中引用回已经生成的项目？

您的理解脱糖或多或少类似于

pathSets flatMap {
  pathSet => pathSet filter {
   path => path.endState contains target
  }
} map {path => path}

最后一个带有恒等函数的映射就是你的产量。我不记得规范是否允许在它是恒等函数时忽略该映射。

无论如何，我希望这能更清楚地表明为什么该结构没有“回溯”。

您可以编写一个惰性的、递归的distinctBy函数

implicit class DistinctStream[T](s: Stream[T]) {
  def distinctBy[V](f: T => V): Stream[T] = {
    def distinctBy(remainder: Stream[T], seen:Set[V]): Stream[T] =
      remainder match {
        case head #:: tail => 
          val value = f(head)
          if (seen contains value) distinctBy(tail, seen)
          else Stream.cons(head, distinctBy(tail, seen + value))
        case empty => empty
     }

    distinctBy(s, Set())  
  }
}

像这样使用它

def solutions(target: Int): Stream[Path] =
(for {
 pathSet <- pathSets
 path <- pathSet
 if path.endState contains target
} yield path) distinctBy (_.endState)

是的，现在有递归。但已经存在了，因为 Stream 的 map、flatMap 和 filter 函数已经都是惰性递归函数了。