筛选算法缺失逻辑

Question

我正在尝试解决coursera scala课程的第三个任务。我已经完成了其中一些，但是在处理某个特定函数时，我认为我没有抓住重点。我必须实现filter函数，该函数将返回给定谓词满足的所有推文集合中的子集。我已经实现了一些函数，我认为这些函数将有助于我完成任务，但是测试失败。

请注意，请不要给我烤好的代码，因为这将违反coursera的荣誉准则。我只想要一些能帮助我调试逻辑并帮助我看到我哪里出错以及为什么测试失败的东西。

  abstract class TweetSet {

  def isEmpty: Boolean
  /**
   * This method takes a predicate and returns a subset of all the elements
   * in the original set for which the predicate is true.
   *
   * Question: Can we implment this method here, or should it remain abstract
   * and be implemented in the subclasses?
   */
  def filter(p: Tweet => Boolean): TweetSet

  /**
   * This is a helper method for `filter` that propagetes the accumulated tweets.
   */
  def filterAcc(p: Tweet => Boolean, acc: TweetSet): TweetSet

  /**
   * Returns a new `TweetSet` that is the union of `TweetSet`s `this` and `that`.
   *
   * Question: Should we implment this method here, or should it remain abstract
   * and be implemented in the subclasses?
   */
   def union(that: TweetSet): TweetSet;

  /**
   * Returns the tweet from this set which has the greatest retweet count.
   *
   * Calling `mostRetweeted` on an empty set should throw an exception of
   * type `java.util.NoSuchElementException`.
   *
   * Question: Should we implment this method here, or should it remain abstract
   * and be implemented in the subclasses?
   */
  def mostRetweeted: Tweet = ???

  /**
   * Returns a list containing all tweets of this set, sorted by retweet count
   * in descending order. In other words, the head of the resulting list should
   * have the highest retweet count.
   *
   * Hint: the method `remove` on TweetSet will be very useful.
   * Question: Should we implment this method here, or should it remain abstract
   * and be implemented in the subclasses?
   */
  def descendingByRetweet: TweetList = ???


  /**
   * The following methods are already implemented
   */

  /**
   * Returns a new `TweetSet` which contains all elements of this set, and the
   * the new element `tweet` in case it does not already exist in this set.
   *
   * If `this.contains(tweet)`, the current set is returned.
   */
  def incl(tweet: Tweet): TweetSet

  /**
   * Returns a new `TweetSet` which excludes `tweet`.
   */
  def remove(tweet: Tweet): TweetSet

  /**
   * Tests if `tweet` exists in this `TweetSet`.
   */
  def contains(tweet: Tweet): Boolean

  /**
   * This method takes a function and applies it to every element in the set.
   */
  def foreach(f: Tweet => Unit): Unit
}

class Empty extends TweetSet {


  def union(that: TweetSet): TweetSet = that  
  def isEmpty = true

  def filter(p: Tweet=> Boolean): TweetSet = new Empty()

  def filterAcc(p: Tweet => Boolean, acc: TweetSet): TweetSet = new Empty()


  /**
   * The following methods are already implemented
   */

  def contains(tweet: Tweet): Boolean = false

  def incl(tweet: Tweet): TweetSet = new NonEmpty(tweet, new Empty, new Empty)

  def remove(tweet: Tweet): TweetSet = this

  def foreach(f: Tweet => Unit): Unit = ()
}

class NonEmpty(elem: Tweet, left: TweetSet, right: TweetSet) extends TweetSet {

  def union(that: TweetSet): TweetSet = (left.union(right)).union(that).incl(elem)
  val isEmpty = false

  def filter(p: Tweet => Boolean): TweetSet = filterAcc(p,left.union(right))

  def filterAcc(p: Tweet => Boolean, acc: TweetSet): TweetSet = {
          if(acc.isEmpty) acc
          else if(p(elem)) {acc.incl(elem); left.filterAcc(p,acc).union(right.filterAcc(p,acc))}
          else new Empty


  }


  /**
   * The following methods are already implemented
   */

  def contains(x: Tweet): Boolean =
    if (x.text < elem.text) left.contains(x)
    else if (elem.text < x.text) right.contains(x)
    else true

  def incl(x: Tweet): TweetSet = {
    if (x.text < elem.text) new NonEmpty(elem, left.incl(x), right)
    else if (elem.text < x.text) new NonEmpty(elem, left, right.incl(x))
    else this
  }

  def remove(tw: Tweet): TweetSet =
    if (tw.text < elem.text) new NonEmpty(elem, left.remove(tw), right)
    else if (elem.text < tw.text) new NonEmpty(elem, left, right.remove(tw))
    else left.union(right)

  def foreach(f: Tweet => Unit): Unit = {
    f(elem)
    left.foreach(f)
    right.foreach(f)
  }
}

我认为这个问题主要在于filterAcc函数，当没有任何情况适用时，它返回"empty"，但我不确定我能做什么来解决这个问题。这就是一切失败的地方吗？如果是，我该怎么解决？

更新： 我也曾试图通过以下方式解决这个问题：

    def filterAcc(p: Tweet => Boolean, acc: TweetSet): TweetSet = {
          if(acc.isEmpty) acc
          else if(p(elem)) {acc.incl(elem); left.filterAcc(p,acc).union(right.filterAcc(p,acc))}
          else left.filterAcc(p,acc).union(right.filterAcc(p,acc))


  }

这种方法现在确保了如果没有匹配的条件，则仍会进行递归调用，但同时累加器不会增加。测试仍然失败。我的逻辑错误在哪里？

感谢@lpiepiora和@Ende Neu的努力告诉我，acc的起始应该为空。我最终使用了联合，因为我的想法太固化了，我就是摆脱不了这个思路。下面是最终的代码：

def filterAcc(p: Tweet => Boolean, acc: TweetSet): TweetSet = {

    if(left.isEmpty && right.isEmpty) acc
    else if(p(elem)){ left.filterAcc(p,acc.incl(elem)).union(right.filterAcc(p,acc.incl(elem)))}
    else left.filterAcc(p,acc).union(right.filterAcc(p,acc))


  }

- Bula

---

记住你的TweetSet是不可变的，所以如果你调用一个添加元素的方法，你会得到一个新的集合。你必须对结果做些什么，否则它就会丢失。在编写filterAcc时不需要使用union - 使用acc累加器和递归即可。此外，当你第一次运行该方法时会发生什么？acc的值是什么 - 它有任何元素吗？另外，如果你遇到空集，会发生什么 - 返回什么？ - lpiepiora

@lpiepiora 是的。它应该是空的。我最终还是使用了一个联合，但是嘿！它起作用了。感谢您的解释。 - Bula

最后一个提示，也许你可以简化一下。如果你得到了一个 EmptySet 并且使用 filterAcc(_ => true, acc)，其中 acc 已经包含了一些元素，你会返回什么？你确定 EmptySet 是正确的吗？ - lpiepiora

@lpiepiora 我什么时候会返回一个EmptySet？ - Bula

int filterAcc的初始值应为空集。就像当你开始计算总和时，它是0。 - Kostiantyn Koval

发布解决方案也违反了荣誉准则，你知道的！ - Sikorski

Answer 1

这对我来说也是非常棘手的。您的方法之一存在的问题是您没有正确地使用累加器，实际上您正在传递集合的并集，而累加器应该仅存储与给定谓词p匹配的结果，因为您可以在for或while循环中使用累加器，它应该初始化为起始值（例如对于Int 0，对于String空字符串等）。例如，假设您有一个List [Int]，并且希望计算正整数的数量：

val list = List(0, -1, -2, 4, 9, -7)

def countPositive(list: List[Int]): Int = {
  def loop(list: List[Int], acc: Int): Int = list match {
    case Nil => acc
    case head :: tail => {
      if( head > 0) loop(tail, acc + 1)
      else loop(tail, acc)
    }
  }
  loop(list, 0)
}

这个累加器的起始值为0，例如，在filterAcc函数中应使用相同的方法处理累加器。

您要做的是拥有一组集合，然后将它们用作标准集合，您可以迭代。我猜问题的重点是处理像这样的完全功能数据结构，也就是说，没有集合的集合，而是一堆以某种方式连接的对象。如果您记得在第3.1讲座的视频中大约在7.20左右有一个部分，Odersky展示了contains和include操作不修改三个结构，而是创建一个新的结构，我的理解是这是问题的精髓。

回到代码，您可以将其看作可以递归的集合，我的方法是使用自定义的tail和head函数，如果存在tail，则可以继续迭代到下一个对象并将满足谓词的head元素添加到累加器中。每次迭代时，都会创建一个新的三个结构，避免已经检查过的部分，您可以使用isEmpty方法知道NonEmpty作为左侧或右侧三个。

请注意，这些方法（tail和head）可能（在我的实现中）是递归的，非常棘手的部分是tail始终返回新的三个对象（如当Odersky定义纯功能结构时所示的视频）。

我可以给出的另一个建议是尝试使用自下而上的策略，即始终使用left.isEmpty（或right.isEmpty）递归到左侧（或右侧）的最后一个元素来检查三个结束的位置，并检查是否必须使用head将元素添加到累加器中，然后使用tail构建一个不包含刚刚检查过的元素的新三个。

对于像我这样几乎没有纯函数数据结构经验的人来说，这对我来说非常棘手，我不知道我是否解释得很清楚或者这是否足以让您开始，不幸的是，很难在不展示代码的情况下解释它，祝好运。

- Ende Neu

---

很抱歉，题目要求不提供句首和句尾的翻译，否则这个练习就太简单了 :(. 同时我不确定你所说的累加器误用是什么意思？我只包含正确的项。在我想做的事情之后，我会再次过滤它，同时合并这两个二叉树。我试图使用一种与找零硬币问题相关的方法，但不是算法方面而是功能方面。你自己实现了头部和尾部吗？ - Bula

我做了一些更新，这个例子中不再使用头部和尾部，而是使用它们的替代方法。仍然对每个左侧和右侧进行递归调用，并将它们合并在一起，以便在递归停止时合并找到的项目。测试仍然失败。我错过了什么？ - Bula

我为“累加器”添加了一个示例。关于头和尾，你必须自己实现它们，也许函数名有点误导，“head”获取左侧（或右侧）叶子中三个元素中最低的元素，而“tail”返回一个新的三元组，其中不包括最后一个已检查的元素。我知道我的方法与你的方法非常不同，很难理解，不幸的是这就是我能解释的范围，我不确定是否可以按照你想要的方式完成，无论如何，我认为这不是练习的方式。主要的重点始终是创建一个新的三元组。 - Ende Neu

检查更新。你的方法肯定会起作用，但我的思维卡在这个想法上，阻碍了其他与我的不同的解决方案。谢谢。 - Bula

Answer 2

您的类"empty"在filterAcc函数中返回了错误的值！（因此会导致过多的不必要代码而且我也遇到了同样的问题）

如果您想一下，tweetSet二叉树总是以空类终止 - 那么空类在filterAcc中应该返回什么？

class Empty extends TweetSet {
    def filterAcc(p: Tweet => Boolean, acc: TweetSet): TweetSet = ???

提示，注意累加器也被传递到 Empty 类的 filterAcc 方法中。

- MrLehiste