algorithm - 过滤算法中缺少逻辑

Question

我正在尝试解决 coursera scala 类(class)中的第三个作业。我已经完成了其中的一些，但是我认为在涉及某个特定功能时我错过了重点。我必须实现过滤器函数，该函数将从满足给定谓词的推文集中返回所有推文的子集。我已经实现了一些我认为可以帮助我的功能，但是测试失败了

注意 请不要给我烘焙代码，因为这会违反 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))


  }

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 中的累加器。功能。

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

回到代码，您可以认为它是一个可以递归的集合，我的方法是使用自定义 tail和 head功能，如果 tail存在你可以继续迭代到下一个对象并添加 head满足累加器谓词的元素。每次迭代时，您都会创建一个新的三结构，避开您已经检查过的部分，您确实知道是否 NonEmpty使用 isEmpty 作为左三或紧三方法。

请注意，此方法(tail 和 head)可以(在我的实现中)是递归的，非常棘手的部分是 tail始终返回新的 threes 对象(如 Odersky 定义纯函数结构时的视频所示)。

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

这对我来说非常棘手，我不知道我自己的解释是否正确，或者这是否足以让你开始，不幸的是对于像我这样在纯函数式数据结构方面经验很少的人来说很难解释它没有显示代码，祝你好运。