iT邦幫忙

2018 iT 邦幫忙鐵人賽
DAY 11
0
Software Development

30天快樂學習 Functional Programming系列 第 11

Algebraic Data Types ,在 Functional Programming 定義資料結構

本章重點

  • 在 FP 中使用 Algebraic Data Types 定義資料結構。
  • type 是 將已有的 Type 組合在一起,然後重新命名 ,而 data 是 創造新的 Type
  • Type 可以帶有參數,使它可以由不同種 Type 組成,如 Array a
  • Type 可以是 recursive , 像是 Linked list 、 Binary search tree
  • FP 從 數學與範疇論 中擷取了不同種的 Class ,它們像是 OOP 的 interface,當 instance 某個 Class ,必須實作某些方法,而他必須符合某些 法則 (Law)

Algebraic Data Types

Maybe Maybe 的機率, Either 恨或愛 中,我們自己創造了新的資料結構,並且讓它有一些我的在 Array 上學的特性。
相同的概念,我們可以繼續延伸到其他資料結構上,在 FP 稱之為 Algebraic Data Types(代數資料型別),簡稱 ADT ,就像 Type Signature,特別的語法定義資料。

來複習一下怎麼定義 Boolean

// data Boolean = False | True

這邊定義了一種 Type 叫 Boolean ,而且有兩種值 False 與 True 。在程式實作中,使用的是 False 與 True ,而 Boolean 是指 Type 的名稱。
特別注意, Type 與 Data 皆為大寫,而 Function 為小寫

// data Shape = Circle Number Number Number

不過 Number Number Number 沒有語意,這有一點頭痛。

Record

Record 可以賦予每個屬性一點語意,讓我們直接看語法。

// data Shape = Circle { x :: Number, y :: Number, radius :: Number }

太好了,現在你看得出這三個 Number 是什麼了,你也可以把它看成 Circle 的參數是傳入一個 Object ,而不是三個 Number 。

Type

我們再另外宣告一個 Rectangle ︰

// data Shape = Circle { x :: Number, y :: Number, radius :: Number }
//            | Rectangle { x1 :: Number, y1 :: Number, x2 :: Number, y2 :: Number }

{ x :: Number, y :: Number } 不斷重複,可以使用 Type 降低重複的部份︰

// type Point = { x :: Number, y :: Number }
// data Shape = Circle Point Number
//            | Rectangle Point Point

type 是 將已有的 Type 組合在一起,然後重新命名 ,而 data 是 創造新的 Type

舉例來說,這是 String ︰

// type String = Array Char

如何實作

接下就能根據 Shape 的定義,把它實作出來︰

// type Point = { x :: Number, y :: Number }
// data Shape = Circle Point Number
//            | Rectangle Point Point
class Circle {
	constructor(p, r) {
		this._p = p
		this._r = r
	}
}

class Rectangle {
	constructor(p0, p1) {
		this._p0 = p0
		this._p1 = p1
	}
	create(p0, p1) {
		return new Rectangle(p0, p1)
	}
}

// showShape :: Shape -> String
const showShape = shape => {
	if (shape instanceof Circle) {
		// 取出 _vaule0 當中的 x, y
		// 與 const [x,...xs] = shape._v1alue0 類似
		const { x, y } = shape.p
		const r = shape.r

		return `Circle (${x}, ${y}) ${r}`
	} else if (shape instanceof Rectangle) {
		// 把 x, y 取出後,重新命名(在 : 之後的名稱)
		const { x: x1, y: y1 } = shape.p0
		const { x: x2, y: y2 } = shape.p1

		return `Rectangle (${x1}, ${y1}) (${x2}, ${y2})`
	}
}

const Shape = {
	Circle: curry((p, r) => {
		return new Circle(p, r)
	}),
	Rectangle: curry((p0, p1) => {
		return new Rectangle(p0, p1)
	})
}

const circle = Shape.Circle({ x: 0, y: 0 }, 10)
const rect = Shape.Rectangle({ x: 0, y: 0 }, { x: 100, y: 100 })
console.log(
	showShape(circle), // Circle (0, 0) 10
	showShape(rect) // Rectangle (0, 0) (100, 100)
)

觀察這段程式碼會發現︰

  • Circle 的 Data Constructor 接受兩個參數, Rectangle 也是。
  • Data Constructor 是可以 Curry 的
  • 在 showShape 的 Type Signature 中,型別是放 Shape
  • 在實作中,先判斷是 Circle 或 Rectangle ,然後採取各自的實作。

Type parameters

在 Shape 中,所有的參數 Type 都是固定住的,與昨天的 Maybe 相比, Maybe 則有一個不限定 Type 的參數。

// data Maybe a = Nothing | Just a
// 
// Just 1 :: Maybe Int
// Just 8.7 :: Maybe Number
// Just "Monica" :: Maybe String
// Nothing :: Maybe a

有了 Type parameters 讓 Maybe 可以由多種型別組成,但若方法有限定型別,必須在函數加註型別。

// 只有 Number 可以 + 1
// divdeMaybe :: Number a => Maybe a -> a -> Maybe a
const incMaybe = maybe => maybe.map(x => x + 1))

在後續我們會引入 Type System 能夠做檢查,在這只要各位看得懂即可。

Recursive data structures

像是 Linked List , 每一個節點互相連結︰

// data List a = Nil | Cons a (List a)

Nil 代表一個空的節點,而 Cons 的 constructor 則有兩個參數︰

  • a
    這個節點的值。
  • List a
    連結到下一個 List,如果這是最後一個節點,連接一個 Nil

可能有點抽象,讓我們直接看實作。

// data List a = Nil
//             | Cons a (List a)
class Nil {
	constructor() {}
	append(a) {
		return new Cons(a, this)
	}
	toString() {
		return 'Nil'
	}
}

class Cons {
	constructor(a, rest) {
		this._a = a
		this._rest = rest
	}
	append(a) {
		return new Cons(a, this)
	}
	toString() {
		const a = this._a
		const rest = this._rest
		
        return `Cons(${a}, ${rest.toString()})`
	}
}

const List = {
	Nil: _ => new Nil(),
	Cons: curry((a, rest) => new Cons(a, rest))
}

const myList = List.Nil()
	.append(613)
	.append(69)
	.append(42)
console.log(myList.toString())

// Cons(42, Cons(69, Cons(613, Nil)))

圖例︰

雖然這個 List 看起來不太實用,不過我們可以用相同的概念寫出 Binary search tree
Binary search tree 底下共有兩個節點,值較小的放左邊,較大放右邊,最後一個節點則連接兩個 Nil 。

圖例︰

// data Tree a = Nil 
//             | Node a (Tree a) (Tree a)
class Nil {
	constructor() {}
	insert(a) {
		return new Node(a, new Nil(), this)
	}
	search(_) {
		return false
	}
	toString() {
		return 'Nil'
	}
}

class Node {
	constructor(a, left, right) {
		this._a = a
		this._left = left
		this._right = right
	}
	insert(b) {
		const a = this._a
		const left = this._left
		const right = this._right

		if (b < a) {
			return new Node(a, left.insert(b), right)
		} else {
			return new Node(a, left, right.insert(b))
		}
	}
	search(b) {
		const a = this._a
		const left = this._left
		const right = this._right

		if (b == a) {
			return true
		} else if (b < a) {
			return left.search(b)
		}
		else{
		    return right.search(b)    
        }
	}
	toString() {
		const a = this._a
		const left = this._left
		const right = this._right

		return `Node(${a}, ${left.toString()}, ${right.toString()})`
	}
}

const Tree = {
	Nil: _ => new Nil(),
	Node: curry((a, left, right) => new Node(a, left, right)),
	fromArray: array => 
		array.reduce(
			(tree, a) => tree.insert(a),
			new Nil()
		)
}

const myTree = Tree.fromArray([8, 6, 1, 7, 9])

console.log(myTree.toString())
// Node(8, Node(6, Node(1, Nil, Nil), Node(7, Nil, Nil)), Node(9, Nil, Nil))
//     8
//    /\
//   6  9
//  /\
// 1  7

console.log(
    myTree.search(8), // true
    myTree.search(7), // true
    myTree.search(0) // false
)

Binary Search Tree 看起來實用多了,主要的概念都來自我們先前的文章。
而外實作了

Typeclass

可以把 FP 的 Typeclass 理解為 OOP 的 Interface ,也就是說 具有某 Typeclass ,該 Type 必須實作某些方法

如果你有注意到的話,上述 Type 都具有 toString 方法。
而在純 FP 語言中,通常 toString 稱為 show ,而它屬於名為 Show 的 Typeclass 。

我想你應該也猜到了, map 也屬於某個 Typeclass , 它屬於 Functor ,因此我在各種 Type 實作 map。

這邊有一張簡易的 Typeclass 圖,你可以在上面找到 Show 與 Functor。

而這些 Typeclass 皆來自 數學與範疇論 ,還記得我們在 認識 Functional Programming 提過這件事嗎?

也有著各種 規格 (Specification) ,規定了 FP 該有哪些 Typeclass ,而這些 Typeclass 必須遵守某些 Law 。

在精通 FP 的路上,你必須能掌握這些 Typeclass ,讓我們在後續的文章一一介紹。

後記

參考資料


上一篇
Maybe Maybe 的機率, Either 恨或愛
下一篇
The Way to Fantasy Land
系列文
30天快樂學習 Functional Programming14

尚未有邦友留言

立即登入留言