Logica mancante nell'algoritmo del filtro

Question

Sto cercando di affrontare il terzo incarico dal corso Coursera Scala. Ne ho completato alcune, ma penso che mi manchi il punto in cui si tratta di una determinata funzione. Devo implementare la funzione filtro che restituirà un sottoinsieme di tutti i tweet dall'insieme di tweet dato che soddisfano un dato predicato. Ho implementato alcune funzioni che credo possano aiutarmi con questo, ma i test falliscono

Nota Si prega di non darmi codice cotto in quanto ciò violerà il codice onore coursera. Tutto quello che voglio è qualcosa che mi aiuterà a mettere a punto la mia logica e aiutarmi a vedere dove ho incasinato e perché i test falliscono.

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

penso che la principale cosa sbagliata di questo è l'filterAcc come si ritorna empty quando nessuno dei casi sono applicabili tuttavia io non so esattamente che cosa altro avrei potuto fare. È qui che tutto fallisce? Se sì, come dovrei aggirarlo?

UPDATE Anche io avevo cercato di risolvere questo problema in questo modo:

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


    } 

Questo metodo rende ora in modo che se nessuno ha trovato la condizione poi una chiamata ricorsiva è ancora fatta, ma allo stesso tempo la l'accumulatore non aumenta I test falliscono ancora. Qual è il difetto della mia logica qui?

Grazie

Come @lpiepiora e @Ende Neu disperatamente cercato di dirmi, l'avvio del secondo dovrebbe essere vuoto. Ho finito per usare ancora un sindacato perché la mia mente si è semplicemente impilata con questa idea e io non riuscivo a farcela. Ecco l'ultimo pezzo di codice:

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

Questo è stato molto difficile anche per me.

Uno dei problemi nell'approccio è che non si sta utilizzando l'accumulatore correttamente, infatti si passa il set unione, un accumulatore deve memorizzare solo i risultati che corrispondono a un dato predicato p, come si potrebbe utilizzare un accumulatore in un ciclo for o while, deve essere inizializzato sul valore iniziale (ad esempio per Int0, per String la stringa vuota e così via).

Come esempio, supponiamo che tu abbia un List[Int] e si desidera contare il numero di interi positivi:

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

Il valore di partenza di questo accumulatore è 0 ad esempio, lo stesso approccio dovrebbe essere utilizzato per la accumulatore nella funzione filterAcc.

Quello che stai cercando di fare è unire un insieme di insiemi e quindi usarli come una raccolta standard dove puoi iterare, immagino che il punto del problema sia gestire una struttura di dati completamente funzionale come questa, che non c'è una collezione di set ma un mucchio di oggetti che sono collegati in qualche modo. Se ricordi i video alla lezione 3.1 attorno a 7.20 c'è una parte in cui Odersky mostra che le operazioni contains e include non modificano le tre strutture invece ne creano una nuova, la mia comprensione è che questo è lo spirito del problema.

Torna codice, si potrebbe pensare su di esso come una collezione che si può recurse, il mio approccio è stato utilizzato su misura tail e head funzioni, se il tail esiste è possibile mantenere l'iterazione all'oggetto successivo e aggiungendo head elementi che soddisfano il predicato all'accumulatore. Ogni volta che si itera, si crea una nuova struttura a tre, evitando la parte già controllata, si sa se uno NonEmpty come uno a sinistra o tre stretti usando il metodo isEmpty.

noti che questo metodo (tail e head) potrebbero (nel mio attuazione sono) essere ricorsiva, la parte più difficile è che tail ritornano sempre nuovi oggetti threes (come mostrato a video quando Odersky definisce la struttura puramente funzionale) .

Un altro suggerimento che posso dare è provare a utilizzare una strategia bottom-up, che è sempre recurse all'ultimo elemento di sinistra (o destra) utilizzando left.isEmpty (o right.isEmpty) per controllare dove si trovano le tre estremità, verificare se si è necessario aggiungere l'elemento all'accumulatore con head e quindi creare un nuovo tre senza l'elemento appena controllato utilizzando tail.

Era per me molto complicato e non so se mi sono spiegato correttamente o se questo è sufficiente per iniziare, sfortunatamente per qualcuno come me con pochissima esperienza su strutture dati puramente funzionali è molto difficile spiegare senza mostrare codice, buona fortuna.

Answer 2

La classe "vuoto" restituisce un valore errato per la funzione filterAcc! (Quindi troppo codice non necessario & Mi sono bloccato con lo stesso problema)

Se ci pensate - tweetSet l'albero binario termina sempre con le classi vuote - quindi cosa dovrebbe filterAcc sul ritorno vuoto?

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

suggerimento, suggerimento -> Si noti che l'accumulatore è anche passato al filterAcc sulla classe vuota