Реализовать DISTINCT для понимания

В предпоследней лекции своего курса 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 перед возвратом. Однако, похоже, что при этом теряются преимущества ленивых вычислений при использовании Stream.

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

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


sql scala for-comprehension
person Daniel Ashton    schedule 27.06.2014    source источник
comment
Вы могли бы использовать рекурсивное определение Stream, но тогда, конечно, вы не могли бы использовать for-comprehension...   -  person Erik Kaplun    schedule 28.06.2014
comment
Использование mutable.Set действительно было бы простым и эффективным. Почему это так беспокоит вас? map и flatMap также реализованы с изменчивостью, даже если вы используете их с этим for. Таким образом, в вашей функции в любом случае есть изменчивость, но посторонний не имеет права использовать эту изменчивость, и это важно. Это также может сделать ваш код более читабельным. изменчивость не дьявол :)   -  person Kigyo    schedule 28.06.2014
comment
Сможете ли вы использовать отдельный метод Stream а-ля этот пост?   -  person wwkudu    schedule 30.06.2014
comment
Это интересная особенность Streams. Тем не менее, похоже, что это должно быть сравнение всего объекта == для сопоставления с отличным. В этом случае я хочу вывести любые следующие элементы, для которых атрибут endState уже был замечен.   -  person Daniel Ashton    schedule 30.06.2014
comment
Если вы выполнили последнее задание курса, если я правильно помню, там была функция, где именно это действие должно было быть реализовано, и это было сделано с использованием аккумулятора, содержащего конечные состояния, которые мы видели до сих пор, и вспомогательной функции, которая фильтровала на основе на том. Это очень выполнимо.   -  person Aakash Jain    schedule 01.07.2014
comment
Чего бы мне действительно хотелось, так это того, чтобы язык Scala изначально поддерживал это расширение для понятий, чтобы один из фильтров в объяснении мог получить доступ к результатам, которые уже были получены этим же пониманием, что позволяет не только использовать DISTINCT на основе на == (как уже поддерживается потоками), но DISTINCT, который основан на пользовательской функции, в данном случае сравнивая атрибуты вещей, которые уже были получены.   -  person Daniel Ashton    schedule 03.07.2014
comment
Нет необходимости добавлять нативную поддержку для Different, и одна из основных идей Scala заключается в том, что вы должны иметь возможность писать нужные вам расширения на самом языке, и они будут выглядеть как примитивы языка. Если вы хотите быть полностью неизменным, вам нужен какой-то преобразователь монады состояния, составленный из монады Stream.   -  person GClaramunt    schedule 12.07.2014
comment
Единственный способ, которым я думаю, будет работать, - это сохранить состояние, независимо от того, делаете ли вы это в изменяемой карте или абстрагируете его в монадах.   -  person Gertjan Assies    schedule 24.09.2014
comment
Я правильно понял вас на этом упрощенном примере? val values = Seq(1, 2, 3, 4); for { value <- values; if !(__ contains 6) } yield value * 2 где __ относится к полученным значениям?   -  person EECOLOR    schedule 13.10.2014

Ответы (1)


arrow_upward
1
arrow_downward

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

Ваш для понимания 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 уже являются ленивыми рекурсивными функциями.

person James Iry    schedule 17.10.2014