Everything is a function

最近刚刚学完Coursera上Functional programming in Scala的课程，通过看教学视频还有做assignments，对于functional programming（函数式编程）有一点点心得体会，在这里总结下。

Everything is a function，不是一种论断，而是函数式编程的思考方式。就像用汇编语言编程时候需要用寄存器和指令的角度来思考，C编程用变量和控制结构来组织程序，C++/Java中我们把任何东西都抽象成类和对象。

在Scala中我们用函数的眼光思考，例如：任何常量(immutable)，都可以看成是一个不需要输入但返回确定值的函数，反之亦然。所有可以用val定义一个Int常量a，也可以用def定义一个函数b返回Int常量，两者可以任意互换使用。

val a:Int = 1
def b:Int = 1

两者的不同在于：常量是传值(reference by value)，函数是传名（reference by name）；常量的值立即计算，函数的值只在被调用时计算；常量只计算一次，但函数每次调用都要重新计算。例如下面的例子中，s1初始求和计算后赋值为5050；s2每次调用时 （理论上 ）都要重新计算求和。

val s1 = (1 to 100).sum
def s2 = (1 to 100).sum

有没有一种折中的方案，只在被调用时计算，又可以只计算一次？有的，就是使用关键词lazy

lazy val s3 =  (1 to 100).sum

上面的s3初始化后，不会立即计算值，只在被调用时求值并且只计算一次值。

纯用函数式编程实现Set

集合Set是最基本的一种数据结构，常用的操作是判断一个值是否在某个Set里。Set的实现方式有很多，想TreeSet，HashSet，BitSet等。可以用纯函数来实现Set吗？答案是可以！下面以IntSet为例展示下。

1. 定义Set类型为一个函数——输入Int值，返回值是否存在。

/**
   * 使用Set最显著的特点来定义类型
   */
  type Set = Int => Boolean

2. 定义contains函数，输入一个集合和一个值，判断值是否在集合内。

def contains(s: Set, elem: Int): Boolean = s(elem)

3. 定义一个单例集合函数，就是只包含一个值的集合。

def singletonSet(elem: Int): Set = (x: Int) => (x == elem)

4. 定义集合的其他操作：

def union(s: Set, t: Set): Set = (x: Int) => (s(x) || t(x))

def intersect(s: Set, t: Set): Set = (x: Int) => (s(x) && t(x))

def diff(s: Set, t: Set): Set = (x: Int) => (s(x) && !t(x))

def filter(s: Set, p: Int => Boolean): Set = (x: Int) => (s(x) && p(x))

5 测试上面的集合实现

val s1 = singletonSet(1)
val s2 = singletonSet(2)
val s3 = singletonSet(3)

val s4 = union(s1, s2)
val s5 = union(s2, s3)

val s6 = intersect(s4, s5)

filter(s6, _%2 == 1)