Missing logic in filter algorithm

Question

I am trying to tackle the third assignment from the coursera scala course. I have completed some of it however I think I'm missing the point when it comes to one certain function. I have to implement the filter function which will return a subset of all of the tweets from the set of tweets given that satisfy a given predicate. I have implemented some functions which I think will help me with this however the tests fail

Note Please do not give me baked code as this will violate the coursera honor code. All I want is something which will help me debug my logic and help me see where I messed up and why the tests fail.

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

I think the major wrong thing about this is the filterAcc as it returns empty when none cases are applicable however I'm not sure exactly what else I could do. Is this where everything fails? If yes how should I go around it?

UPDATE Also I had tried to solve this problem this way:

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


  }

This method now makes sure that if none matched the condition then a recursive call is still made but at the same time the accumulator does not increase. The tests still fail. What is the flaw of my logic here?

Thanks

As @lpiepiora and @Ende Neu desperately tried to tell me, the starting of acc should be empty. I have ended up using still an union because my mind simply got stack with this idea and I just couldn't get it off. Here is the final piece of code:

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

This was very tricky for me too.

One of the problems in your approach is that you are not using the accumulator correctly, in fact you're passing the sets union, an accumulator should only store results that match a given predicate p, as you could use an accumulator in a for or while loop, it should be initialized to the starting value (e.g. for Int 0, for String the empty string, and so on).

As example, let's say you have a List[Int] and you want to count the number of positive integers:

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

The starting value for this accumulator is 0 for example, the same approach should be used for the accumulator in the filterAcc function.

What you're trying to do is have a union of sets and then use them as a standard collection where you can iterate, I guess the point of the problem is to handle a fully functional data structure like this one, that is there's no collection of sets but a bunch of object which are connected somehow. If you remember the videos at lecture 3.1 around 7.20 there's a part where Odersky shows that contains and include operations don't modify the three structure instead they create a new one, my understanding is that this is the spirit of the problem.

Back to the code, you could think about it as a collection that you can recurse on, my approach was using custom tail and head functions, if the tail exists you can keep iterating to the next object and adding head elements that satisfy the predicate to the accumulator. Every time you iterate you create a new three structure avoiding the part you already checked, you do know if a NonEmpty as a left or tight three using the isEmpty method.

Note that this methods (tail and head) could (in my implementation they are) be recursive, the very tricky part is that tail always return new threes objects (as shown on the video when Odersky defines the structure purely functional).

Another suggestion I can give is try to use a bottom-up strategy, that is always recurse to the last element of the left (or right) using left.isEmpty (or right.isEmpty) to check where the three ends, check if you have to add the element to the accumulator with head and then build a new three without the element just checked using tail.

It was for me very tricky and I don't know if I explained myself correctly or if this is enough to get you started, unfortunately for somebody like me with very few experience on purely functional data structures is very hard to explain it without showing code, good luck.

Answer 2

Your class "empty" returns wrong value for filterAcc function! (Hence too much unnecessary code & I got stuck with the same issue)

If you think about it - tweetSet binary tree always terminates with empty classes - then what should filterAcc on empty return?

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

Hint, hint --> notice that the accumulator is also passed into the filterAcc on Empty class