背景

春节闲着上Coursera看了看scala的课 Functional Programming Principles in Scala ,其中有个要合并二叉树的题目。题中把一系列推特上的推文用二叉树的结构存储为TweetSet类。题目要求对二叉树类(TweetSet)实现一个Union的方法,对二叉树调用this.union(that) 方法实现this和that两棵树的合并。由于对函数式编程了解的不够深入,做作业的时候死活也写不对递归函数。

Scala介绍

Scala是门函数式和面向对象的多范式语言。可以像Java一样有类、对象、继承、接口等等熟悉的结构。同时也有像lisp、clojure之类的函数式编程特性。

另外,Scala是运行在JVM上的语言,利用了JVM的性能优势和广泛的现存Java代码。

由于以上两点原因,Scala可以import许多Java的包,兼具性能优势、社区优势。

首先大概描述一下scala的语法,scala的函数定义如下:

def 函数名(参数1:参数1类型, 参数2:参数2类型):返回值类型{
    ...
    函数体
}

题目如下,在TweetSet类中,定义了许多函数,其中我们要用的有incl函数,include一条推文(tweet)并返回新生成的TweetSet。


class TweetSet {
  /*
  *其他函数
  ...
  */

  /*
  include 函数,对TweetSet添加一条tweet后返回新的TweetSet
  def incl(tweet: Tweet): TweetSet={
    ...
  }
  
  def union(that: TweetSet): TweetSet  = {
    if(that.isEmpty) return this
    else {
        return ???
    }
  }

}

// 烂尾了,不会画图,有心情再更

//      that.incl(elem).union(left.union(right))
//      that.union(left).incl(elem).union(right)

      //right version
      left.union(right.union(that.incl(elem)))

      //Stack Overflow:
      //that.incl(elem).union(left).union(right)
//      (left union right) union that



反汇编代码


   /**
        * decompile from class file
        *
        * Stack Overflow
        * public TweetSet union(TweetSet that)
          {
            return that.isEmpty() ? this :

            that.incl(this.elem).union(this.left).union(this.right);
          }



        *Right Version
        *   public TweetSet union(TweetSet that)
            {
              return that.isEmpty() ? this :

              this.left.union(this.right.union(that.incl(this.elem)));
            }
        *
        *
        */