バイナリツリーをトラバースしながら不変なコレクションを構築する

Question

以下のクラスMessageTreeを使用して、Messageのインスタンスを含むバイナリツリーを表し、すべてのメッセージを含む新しいMessageTreeを返すメソッドfilterを実装したい与えられた述語を満たす。私はListBufferを使用するソリューションを持っていますが、ツリーを横断しながら、ListBufferの代わりに不変のコレクションを構築するソリューションを探しています。どんな洞察にも感謝します。

object scratchpad extends App { 

    import scala.collection.mutable.ListBuffer 

    // A class to represent messages 
    class Message(val text: String, val user: String, val comments: Int) { 
    override def toString: String = 
     "User: " + user + "\n" + 
     "Text: " + text + " [" + comments + " comments]" 
    } 

    /* --------------------------------------------------------------------- */ 

    abstract class MessageTree { 

    type MessagePredicate = Message => Boolean 

    def traverse(p: MessagePredicate, storage: ListBuffer[Message]) : Unit 

    def filter(p: Message => Boolean): MessageTree = filterAcc(p, new Empty) 

    def filterAcc(p: Message => Boolean, acc: MessageTree): MessageTree 

    def incl(tweet: Message): MessageTree 

    def foreach(f: Message => Unit): Unit 

    } 

    /* --------------------------------------------------------------------- */ 

    class Empty extends MessageTree { 

    override def traverse(p: MessagePredicate, storage: ListBuffer[Message]): Unit = {} 

    override def filterAcc(p: (Message) => Boolean, acc: MessageTree): MessageTree = acc 

    def incl(tweet: Message): MessageTree = new NonEmpty(tweet, new Empty, new Empty) 

    def foreach(f: Message => Unit): Unit =() 

    } 

    /* --------------------------------------------------------------------- */ 

    class NonEmpty(elem: Message, left: MessageTree, right: MessageTree) extends MessageTree { 

    override def traverse(p: MessagePredicate, storage: ListBuffer[Message]): Unit = { 
     left.traverse(p, storage) 
     if (p(elem)) storage += elem 
     right.traverse(p, storage) 
    } 

    override def filterAcc(p: (Message) => Boolean, acc: MessageTree): MessageTree = { 
     val tweet_collector = ListBuffer.empty[Message] 
     traverse(p, tweet_collector) 
     def loop(listBuffer: ListBuffer[Message], accum: MessageTree) : MessageTree = { 
     if (listBuffer.isEmpty) accum 
     else loop(listBuffer.tail, accum incl listBuffer.head) 
     } 
     loop(tweet_collector, acc) 
    } 

    def incl(x: Message): MessageTree = { 
     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 foreach(f: Message => Unit): Unit = { 
     left.foreach(f) 
     f(elem) 
     right.foreach(f) 
    } 

    } 

    /* --------------------------------------------------------------------- */ 
    /* Test 
    /* --------------------------------------------------------------------- */ 
    val keyword_list: List[String] = "one" :: "three" :: "five" :: "seven" :: "nine" :: Nil 

    def search_predicate(msg: Message): Boolean = { 
    keyword_list.exists(msg.text.contains(_)) 
    } 

    val msg_00 = new Message("zero", "John_00", 50) 
    val msg_01 = new Message("one", "John_01", 10) 
    val msg_02 = new Message("two", "John_02", 20) 
    val msg_03 = new Message("three", "John_03", 30) 
    val msg_04 = new Message("four", "John_04", 40) 
    val msg_05 = new Message("five", "John_05", 50) 

    val tmp_message_tree = new NonEmpty(msg_00, new Empty, new Empty) 
    val message_tree = tmp_message_tree incl msg_01 incl msg_02 incl msg_03 incl msg_04 incl msg_05 

    println("All messages") 
    message_tree foreach println 

    println("Filtered messages") 
    (message_tree filter search_predicate) foreach println 


} 

出力は

すべてのメッセージ

ユーザーです：John_05
テキスト：5 [50コメント]
ユーザー：John_04
テキスト：4 [40コメント]
ユーザー：John_01
テキスト：1 [10コメント]
ユーザー：John_03
本文：3 [30コメント]
ユーザー：John_02
本文2つの[20コメント]
ユーザー：John_00
本文：ゼロ[50コメント]

濾過メッセージ

ユーザー：John_05
本文：5 [50コメント]
ユーザー：John_01
本文：1 [10件のコメント]
ユーザー：John_03
テキスト：3 [30件のコメント]

Answer 1

あなたはほとんどそこにいる：あなたはそうのようなトラバースを変更するだけで済みます：

def traverse(p: MessagePredicate):List[Message] = { 
    left.traverse(p) ++ 
    (if (p(elem)) List(elem) else List()) ++ 
    right.traverse(p) 
} 

この解決策は単純ですが、それはあまりにも活用高価な多くのコンカチネーションをリストアップします。別のアプローチは、concatinationsを減らすために、アキュムレータを使用することです：

def traverse(p: MessagePredicate, acc:List[Message]):List[Message] = { 
    val r = right.traverse(acc) 
    left.traverse(p, if(p (elem)) elem::r else r) 
} 

と空のノードのために：

def traverse(p: MessagePredicate, acc:List[Message]):List[Message] = acc