Scala Functional Language 簡介 (Session 5)

Scala Functional Language 簡介

Functional Language 其實很早就有了，只是 OOP 概念比較能讓人接受，因此 Functional Language 就被忽略。近來大數據需要做大量平行與分散式的運算，Functional Lanauge 才又被重視。

Functional Language 簡單來說，就是：

Treats computation as the evaluation of mathematical functions and avoids changing-state and mutable data (Side Effects)

截自 Wiki: Functional Lanauge

名詞解釋

Mathematical Functions

Mathematical Functions 簡單來說，就是兩個集合間的關係，且每一個輸入值，只會對應到一個輸出值。

最簡單的數學函數的表示式：

\[f: X \mapsto Y\]

比如說：Square

\[Square: Int \mapsto Int \] \[f(x) = x^2\]

比如 \(f(3) = 9\), \(f(-3) = 9\) ，每次計算 \(f(3)\) 一定都會是 9 不會變成其他值。

Side Effects

程式的函式有以下的行為時，就會稱該函式有 Side Effects。

• Reassigning a variable (val v.s. var)
• Modify a data structure in place (mutable v.s. immutable)
• Setting a field on an object (change object state)
  • 這裏指的 object 是 OOP 的 Object 不是 Scala 的 object (singleton)
  • OOP 修改物件的值，在程式語言的術語：改變物件的狀態，如上說的 changing-state
• Throwing an exception or halting with error
• Printing to the console or reading user input (I/O)
• Reading from or write to a file (I/O)
• Drawing on the screen (I/O)

截自 Functional Language in Scala

就實際狀況來說，我們寫程式不可能不去碰 I/O。

Purely Functions

Purely functional functions (or expressions) have no side effects (memory or I/O).

截自 Wiki: Purely Function

Referential Transparency (RT)

An expression is said to be referentially transparent if it can be replaced with its value without changing the behavior of a program

截自 Wiki: Referential Transparency

簡單來說，程式碼中的變數，可以用此變數的值或運算式子來取代，而且不會改變輸出的結果。

舉例來說：String 是 immutable，當每次呼叫 reverse 時，都會回傳固定的值。

scala> val x = "Hello, World"
x: String = Hello, World

scala> val r1 = x.reverse
r1: String = dlroW ,olleH

scala> val r2 = x.reverse
r2: String = dlroW ,olleH

此時，可以將上述的 x 直接替換成 Hello, World，程式的結果都不會被改變。此特性，就是 Referential Transparency。如下：

scala> val r1 = "Hello, World".reverse
r1: String = dlroW ,olleH

scala> val r2 = "Hello, World".reverse
r2: String = dlroW ,olleH

另舉反例：StringBuilder 是 mutable，append 會修改 StringBuffer 內的值 (change object state)。

scala> val x = new StringBuilder("Hello")
x: StringBuilder = Hello

scala> val y = x.append(", World")
y: StringBuilder = Hello, World

scala> val r1 = y.toString
r1: String = Hello, World

scala> val r2 = y.toString
r2: String = Hello, World

當將 y 替換成 x.append(", World") 時：

scala> val r1 = x.append(", World").toString
r1: String = Hello, World

scala> val r2 = x.append(", World").toString
r2: String = Hello, World, World

此時 r1 及 r2 的值並不一致，這樣子就沒有 Referential Transparency 。

範例截自： Functional Language in Scala

為什麼 Referential Transparency 如此重要

當程式設計都符合 Referential Transparency 時，就代表程式可以分散在不同 Thread, CPU核心，甚至不同主機上處理(空間)，而且不論什麼時候被處理(時間)，都不會影響輸出的結果。

Funcational Language 程式設計的終極目標就是 Referential Transparency。

First-Class Function and High Order Function

First-Class Function

一個程式語言有 First-Class Function 特性，是指此程式語言將 Function 當作是一種資料型態。

在 Scala 中，有定義 Function 這個 class。如下：

scala> val max = (x: Int, y:Int) => if (x > y) x else y
max: (Int, Int) => Int = <function2>

scala> max(3, 4)
res5: Int = 4

High Order Function

Hight Order Function 是指 Function 其中一個參數的資料型別是 Function。比如 List 的 foreach。

scala> List(1, 2, 3, 4) foreach { x => println(x + x) }
2
4
6
8

Function Composition

數學的複合函數：

\[f: X \mapsto Y\]

\[g: Y \mapsto Z\]

\[ g \circ f: X \mapsto Z\]

\[ (g \circ f )(x) = g(f(x))\]

在 Scala 上的實作，有 compose 及 andThen

f andThen g 等同於 \( g \circ f \)

f compose g 等同於 \( f \circ g \)

eg:

scala> val f = (x: Int) => x * x
f: Int => Int = <function1>

scala> val g = (x: Int) => x + 1
g: Int => Int = <function1>

scala> val goff = f andThen g
goff: Int => Int = <function1>

scala> goff(10)
res10: Int = 101

scala> val fofg = f compose g
fofg: Int => Int = <function1>

scala> fofg(10)
res11: Int = 121

轉成 Function Class

一般會用 def 宣告 function；可以使用 _ 轉換成 Function Class。如下：

scala> def f(x: Int) = x * x
f: (x: Int)Int

scala> def g(x: Int) = x + 1
g: (x: Int)Int

scala> f andThen g
<console>:10: error: missing arguments for method f;
follow this method with `_' if you want to treat it as a partially applied function
              f andThen g
              ^
<console>:10: error: missing arguments for method g;
follow this method with `_' if you want to treat it as a partially applied function
              f andThen g
                        ^
                        
 scala> f _ andThen g _
res1: Int => Int = <function1>

Partially Applied Function

def sum(x: Int, y: Int, z: Int) = x + y + z
sum: (x: Int, y: Int, z: Int)Int

scala> val a = sum _
a: (Int, Int, Int) => Int = <function3>

scala> val b = sum(1, _: Int, 3)
b: Int => Int = <function1>

scala> b(2)
res1: Int = 6

Closure

A function object that captures free variables, and is said to be “closed” over the variables visible at the time it is created.

舉例：

scala> var more = 10
more: Int = 10

scala> val addMore = (x: Int) => x + more
addMore: Int => Int = <function1>

addMore 是一個 Closure. more 這個變數是 free variable. x 是 bounded variable.

Currying

假設有個 function 由兩個以上的集合對應到一個集合：

\[f: X \times Y \mapsto Z\]

比如說：

\[f(x, y) = \frac{y}{x}\]

我們可以定義一個 Curring Function ：

\[h(x) = y \mapsto f(x, y)\]

\(h(x)\) 是一個 Function ，它的輸入值是 x ，回傳值是 Function 。

比如說：

\[h(2) = y \mapsto f(2, y)\]

這時候的 \( h(2) \) 是一個 Function：

\[ f(2, y) = \frac {y}{2} \]

此時，我們可以再定義一個 Function: \(g(y) \)

\[g(y) = h(2) = y \mapsto f(2, y)\]

也就是

\[g(y) = f(2, y) = \frac {y}{2}\]

在 Scala 的實作：

定義 \( f: X \times Y \mapsto Z \)

scala> def f(x: Int)(y: Int) = y / x
f: (x: Int)(y: Int)Int

scala> f(4)(2)
res7: Int = 0

scala> f(2)(4)
res8: Int = 2

定義 \( g(y) = h(2) = y \mapsto f(2, y) \) i.e. \[g(y) = f(2, y) = \frac {y}{2} \]

scala> val h = f(2) _
h: Int => Int = <function1>

當 \( y = 4 \) 時，

\[g(4) = f(2, 4) = \frac {4} {2} = 2\]

scala> h(4)
res9: Int = 2

範例截自 Wiki: Curring

另一種使用時機：

scala> def modN(n: Int)(x: Int) = ((x % n) == 0)
modN: (n: Int)(x: Int)Boolean

scala> val nums = List(1, 2, 3, 4, 5, 6, 7, 8)
nums: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8)

scala> nums filter { modN(2) }
res10: List[Int] = List(2, 4, 6, 8)

scala> nums filter { modN(3) }
res11: List[Int] = List(3, 6)

數學式對應：

\[modN: Int \times Int \mapsto Boolean\]

\[modN(n, x) \Rightarrow ((x \bmod n ) == 0)\]

\[mod2(x) = modN(2, x) \Rightarrow ((x \bmod 2) == 0)\]

\[mod3(x) = modN(3, x) \Rightarrow ((x \bmod 3) == 0)\]

範例截自：Scala Document: Currying

Scala Partial Function

一般定義 Function 都會去處理輸入值的所有情況。比如說：

def plusOne(x: Int) = x + 1

所有 Int 整數值，傳進 plusOne 都會被處理。

Partial Function 換言之就是只處理某些狀況下的值。

定義：

scala> val one: PartialFunction[Int, String] = { case 1 => "one" }
one: PartialFunction[Int,String] = <function1>

使用：如果輸入沒有要處理的值時，會出現 Exception。比如 1 有定義，但 2 沒有，所以輸入 1 沒問題，輸入 2 就會有 Exception。

scala> one(1)
res0: String = one

scala> one(2)
scala.MatchError: 2 (of class java.lang.Integer)
  at scala.PartialFunction$$anon$1.apply(PartialFunction.scala:253)
  at scala.PartialFunction$$anon$1.apply(PartialFunction.scala:251)
  at $anonfun$1.applyOrElse(<console>:7)
  at $anonfun$1.applyOrElse(<console>:7)
  at scala.runtime.AbstractPartialFunction.apply(AbstractPartialFunction.scala:36)
  ... 33 elided

查詢輸入值，是否已在處理的範圍內：

scala> one.isDefinedAt(1)
res2: Boolean = true

scala> one.isDefinedAt(2)
res3: Boolean = false

Composition of Partial Function

可以使用多個 Partial Function 組成一個複合函數。

scala> val two: PartialFunction[Int, String] = { case 2 => "two" }
two: PartialFunction[Int,String] = <function1>

scala> val three: PartialFunction[Int, String] = { case 3 => "three" }
three: PartialFunction[Int,String] = <function1>

scala> val wildcard: PartialFunction[Int, String] = { case _ => "something else" }
wildcard: PartialFunction[Int,String] = <function1>

scala> val partial = one orElse two orElse three orElse wildcard
partial: PartialFunction[Int,String] = <function1>

scala> partial(5)
res4: String = something else

scala> partial(3)
res5: String = three

scala> partial(2)
res6: String = two

scala> partial(1)
res7: String = one

scala> partial(0)
res8: String = something else

scala> partial.isDefinedAt(10)
res9: Boolean = true

scala> partial.isDefinedAt(1000)
res10: Boolean = true

範例截自：Twitter Scala School - Partial Function

總結

開始使用 Functional Lanague 時，思維需要做改變，程式設計時，以往用 OO 處理的設計，要轉換到是否可以切割成 Function 來處理，尤其是 Function 要符合數學函數或 Purly Function 的定義，Functional Language 程式的設計思維，會更倚重數學邏輯。

進階：

• Wiki: Monad
• Coursera: 響應式編程原理 - Week 1