Реализуйте 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с, которые имеют DISTINCTendState,

Есть ли способ вернуться изнутри предложения фильтра того же понимания к элементам, которые уже были получены?

Другой подход может заключаться в преобразовании pathSets к Map от endState в path перед for заявление, а затем преобразовать его обратно в Stream прежде чем вернуть его. Тем не менее, это может привести к потере ленивых вычислений от использования Stream,

Более ранний метод из того же конкретного случая достигал сходных целей, но он уже был рекурсивной функцией, в то время как этот метод не должен (кажется) быть рекурсивным.

Похоже, я мог бы использовать изменчивый Set отслеживать endStates, которые уступают, но это неудовлетворительно, так как курс до сих пор успешно избегал использования изменчивости.

Answer 1

Есть ли способ вернуться изнутри предложения фильтра того же понимания к элементам, которые уже были получены?

Вы для понимания desugars к чему-то более или менее, как

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

Последняя карта с функцией идентичности - это ваша доходность. Я не могу вспомнить, позволяет ли спецификация исключать эту карту, когда это функция идентичности.

Во всяком случае, я надеюсь, что это более ясно показывает, почему нет "обратной связи" с этой структурой.

Вы можете написать ленивую, рекурсивную функцию DifferentBy

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, flatMap и filter являются уже ленивыми рекурсивными функциями.