滤波算法中的缺失逻辑

Question

我正试图解决coursera课程的第三项任务。我已经完成了其中的一些，但是，我认为，当涉及到某一特定功能时，我忽略了这一点。我必须实现过滤器函数，它将从满足给定谓词的一组tweet返回所有tweet的子集。我已经实现了一些功能，我认为这些功能可以帮助我，但是测试失败了。

备注，请不要给我烘焙代码，因为这将违反课程荣誉代码。我所想要的就是帮助我调试我的逻辑，帮助我了解我在哪里搞砸了，为什么测试失败了。

  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时，没有任何情况是适用的，但是我不确定我还能做些什么。这是一切都失败的地方吗？如果是的话，我该怎么做？

UPDATE我也尝试过这样解决这个问题：

    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拼命想告诉我的那样，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))


  }

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 --有一部分奥德斯基表示，contains和include操作没有修改这三种结构，而是创建了一个新的结构，我的理解是，这就是问题的精神所在。

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

注意，这个方法(tail和head)可以是递归的(在我的实现中它们是)，非常棘手的部分是，tail总是返回新的三个对象(正如在Odersky定义纯函数的结构时在视频中显示的那样)。

我可以给出的另一个建议是尝试使用自下而上的策略，即始终使用left.isEmpty (或right.isEmpty)对左侧(或右侧)的最后一个元素进行递归检查，检查是否必须将元素添加到带有head的累加器中，然后在不使用tail检查元素的情况下构建一个新的元素。

这对我来说非常棘手，我不知道我是否正确地解释了自己，或者这是否足以让你开始工作。不幸的是，对于像我这样对纯功能数据结构缺乏经验的人来说，很难在没有显示代码的情况下解释它，祝你好运。

Answer 2

类“空”返回filterAcc函数的错误值！(因此，太多不必要的代码&我被同一个问题困住了)

如果您考虑一下-- tweetSet二叉树总是以空类结束，那么在空返回时filterAcc应该是什么呢？

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

提示，提示->注意累加器也被传递到空类上的filterAcc中。