滤波器算法中缺少逻辑

Question

我正在尝试从课程scala课程中解决第三项任务.我已经完成了一些但是我认为在某个特定功能方面我忽略了这一点.我必须实现过滤器函数,该函数将返回给定满足给定谓词的推文集中的所有推文的子集.我已经实现了一些我认为可以帮助我的功能,但测试失败了

注意请不要给我烘焙代码,因为这将违反课程荣誉代码.我想要的只是帮助我调试逻辑并帮助我查看我搞砸的地方以及测试失败的原因.

  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))


  }

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累加器添加满足谓词的元素.每次迭代时都会创建一个新的三个结构,避开已经检查过的部分,NonEmpty使用该isEmpty方法确实知道左边的还是紧的三个.

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

我可以给出的另一个建议是尝试使用自下而上的策略,总是递归到左边(或右边)的最后一个元素,使用left.isEmpty(或right.isEmpty)检查三个结束的位置,检查是否必须添加元素累加器,head然后构建一个新的三个没有刚刚使用的元素检查tail.

这对我来说非常棘手,我不知道我是否正确地解释了自己,或者这是否足以让你开始,不幸的是,像我这样对纯功能数据结构的经验很少的人很难解释它而不显示代码, 祝好运.