lifting

(a -> b) -> (f a -> f b)

接收一個函數a -> b，回傳一個新的函數f a -> f b，新函數和舊函數的差別在於新函數可以處理任何type為functor typeclass的instance的值（例如[Int], [）

這件事情在Haskell中叫做lifting。

比較

使用 list comprehesion

[x * y | x <- [1..5], y <- [6..10]]

使用 Functor 和 Applicative

(*) <$> [1..5] <*> [6..10]

IO Action也是Applicative

1
2
3
4
5
6

instance Applicative IO where
    pure    = return
    a <*> b = do
        f <- a
        x <- b
        return (f x)

IO action 也是 Applicative 的一個 instance。IO action 中的 Applicative 涉及 sequencing。

根據上面的定義，在a <*> b當中：

• 先執行 IO Action a

  pure is all about putting a value in a minimal context that still holds it as its result

If <*> were specialized for IO it would have a type of (<*>) :: IO (a -> b) -> IO a -> IO b. It would take an I/O action that yields a function as its result and another I/O action and create a new I/O action from those two that, when performed, first performs the first one to get the function and then performs the second one to get the value and then it would yield that function applied to the value as its result. We used do syntax to implement it here. Remember, do syntax is about taking several I/O actions and gluing them into one, which is exactly what we do here.

With Maybe and [], we could think of <*> as simply extracting a function from its left parameter and then sort of applying it over the right one. With IO, extracting is still in the game, but now we also have a notion of sequencing, because we’re taking two I/O actions and we’re sequencing, or gluing, them into one. We have to extract the function from the first I/O action, but to extract a result from an I/O action, it has to be performed.

留言與分享

CH2 三個重要方法

corpus 的定義

the notion of “corpus” refers to a machine-readable collection of (spoken or written) texts that were produced in a natural communicative setting, and the collection of texts is compiled with the intention (I) to be representative and balanced with respe<:t to a particular linguistic variety or register or genre and (2) to be analyzed linguistically.

各種 corpora

general vs. specific

raw vs. annotated

幾種annoation:

• lemmatized
• POS tag
• morphological
• phonological
• syntactically parsed
• etc.

  歷時 vs. 共時

  靜態 vs. 動態

corpora能提供什麼資訊

簡單來說就是頻率：

• 各種pattern的出現頻率
• pattern之間的共同出現頻率

Frequency

詞的頻率。

但什麼是詞？不同語言中的詞。

type vs. token

從頻率能看出些什麼 (p. 14)

Collocation

Lexical Co-occurence

三種co-occurence

• collocation (本篇重點)
• colligation
• collostruction

應用

• 語言教學
• 語義學

Concordance

(Lexico-)Grammatical Co-occurence

相較於collocation，concordance關注的是一個詞所處於的更大的脈絡。

留言與分享

問題意識

如何根據現有的type組成新的type？有哪些組成方式？

讓我們先把 type 想成是 一組值的集合，舉例來說，正整數的type是從1開始一路往上加1的所有值所組成的一個集合；而Bool type則是由True和False這兩個值所組成的集合。

我們現在問的問題是，要如何根據原有的type組出新的type，就好像是在問說，我們要怎麼根據現有的不同集合，去拼湊出一個新的集合。

兩種思路

1. and思維／組合／Product Type

使用 and，將兩種以上的type組合在一起。假設我們想為一本書的建模，那麼我們可以說一本書是由:

• 書名
• 作者
• 出版年份
• 頁數
• ISBN

所構成。物件導向語言中的Class，遵循的就是這樣的思路，把和一個類別相關連的所有屬性組織在一起。舉例來說，我們可以建立一個名為Book的類別，相對應的，這個Book class中具有:

• 書名屬性（字串）
• 作者屬性（字串）
• 出版年份屬性（正整數）
• 頁數屬性（正整數）
• ISBN屬性（正整數屬性）

透過上述這種利用並列組合的思考方式，稱為Product Type。

1
2
3
4
5
6
7
8

# python程式碼範例
class Book:
    def __init__(self, title, author, year, pages, isbn):
        self.title = title
        self.author = author
        self.year = year
        self.pages = pages
        self.isbn = isbn

更多例子

• 一台電腦由CPU、記憶體、鍵盤、螢幕…等所組成
• 一個地址由郵遞區號、國家、縣市、路名、巷弄、號碼所組成

為什麼叫作Product type

Product type的名稱與集合論中的笛卡爾積(Cartesian Product)有關。

一個簡化的模型，

data ABC = ABC Bool Bool Bool

(True, False)

(False, True)

(True, True)

(False, False)

(待補)

2. or思維／並列／Sum Type

上面的and思維把焦點放在一個類型由哪些成分組合成在一起。但我們還有另一種看世界的方式：一個類型可以分別是哪些東西。舉個例子來說，我們可以根據男生、女生、其他這三種type，並列組合成性別這個新的type。

我們來對比一下兩種說法：

• 一本書由[書名、作者、出版年、頁數]所組成
• 一個性別由[男生、女生、其他]所組成

表面上，這兩個句子都是以「…由…所組成」的句型，乍看之下好像是同一件事，但其實仔細去想一下後，就可以發現其中最大的差別：

• 一本書必須同時具有[書名、作者、出版年、頁數]
• 一個人的性別只能是[男生]或者[女生]或者[其他]其中之一

使用 or，例如 Bool type 由 True 或 False 組成。。稱為Sum Type。

0與1

在乘法中，任何數a乘以1還是等於a自己。

a * 1 = a

在加法中，任何數a加上0還是等於a自己。

a + 0 = a

Void: 是一個不具有任何元素的type。

data Void
Void是一個type constructor
Void沒有data constructor，因為Void這個type不具有任何元素

1

data X a = X a | Y Void

Unit: 是一個只具有一個元素的type，以()表示。

Unit是一個type constructor
Unit只有一個元素： ()

1

type Y a = (a, ())

將Type與代數計算相關連

以代數中的加法與乘法來看資料結構：

代數

• Symbols: 0, 1, 2, …, x, y, z, ….
• Operations: +, -, *, /
• Laws: 結合律、分配律、0+x=x

Haskell

• Symbols: (), Int, Bool, …
• Operations: Type Constructors (Maybe, Either, [],…)
• Laws: ???

One

data Unit = Unit

data () = ()
type 為 Unit, 其 data constructor 沒有參數。只有一個值。

加法

data a:+ b = AddL a | AddR b

data Either a b = Left a | Right b

以Either Bool Bool為例，一共有四個值：

• Left True
• Left False
• Right True
• Right False

因此可以作為加法的定義。

乘法

data a:* b = Mul a b

data (a, b) = (a, b)

以(Bool, Bool)為例，一共有四個值：

• (T, T)
• (T, F)
• (F, T)
• (F, F)

tuple的第一個元素有T和F兩種選項，第二個元素也有T和F兩種選項，所以(Bool, Bool)會有 2 * 2 = 4 種可能。

Zero

data Void

Void是一個含有0個值的type。

Two

type Two = Unit :+ Unit

data Bool = True | False

Function

data a -> b

a->b <=> b^ a
因此可以作為加法的定義。

參考資料

• Wikipedia: Algebraic Data Type
• Why Sum Types Matter in Haskell
• The algebra (and calculus!) of algebraic data types
• The Algebra of Algebraic Data Types
• Haskell’s algebraic data types
• 資源整理

留言與分享

似然率和機率是不同的概念。

名詞定義

• 假說 hypothesis: 一個假說由欲估計的data model的一組parameter所構成。

提出假說的目的在於根據觀察得到的資料去回推現象背後的未知模型。一

機率：在給定的一假說（資料分布）之下，抽樣得到某特徵的資料的機率。關注的是資料。

似然率：在給定資料的條件下，去度量不同假說成立的可能性。關注的是假說。似然率的概念之所以與機率不同，是因為對於一組觀察到的資料而言，會有無窮多個假說，我們不可能全部列舉。但是對於機率而言，一個檢驗的所有可能結果必須先定義好，才能讓所有可能結果的機率加總等於一。

Maximum Likelihood Estimation

根據得到的資料，從眾多假說中找出Likelihood最高的假說，來作為Parameter。

likelihood是用來看假說的可能性。

參考資料

• Bayes for Beginners: Probability and Likelihood
• Understanding Bayes: A Look at the Likelihood
• StatQuest: Probability and Likilihood
• 這篇文章有簡單提到似然率和機率的差別

留言與分享

你有一個list，你想依序一次取出一個元素；
你有一個string, 你想依序一次取出一個字元；
你有一個tuple of tuple，你想依序一次取出一個tuple；
你有一個dict，你想一次取出一對(key, value)；
你有一個文本的file object，你想一次取出一行；

Iterable

可迭代對象。讓我們先看看Python3官方文件Glossary中Iterable條目的內容：

Iterable (可迭代物件)

iterable(可迭代物件)是一種能夠一次回傳一個成員的物件。所有sequence類別的物件（例如list, str, tuple）和一些 non-sequence類別的物件（例如dict, file objects）都是iterable物件。另外，任何定義有__iter__()方法或者__getitem__()方法的class，實例化後的物件也算是iterable。

Sequence: 定義有__getitem__()方法（可透過整數索引來存取其成員）和 __len__()方法（回傳sequence長度）的物件。

Iterables可以用在for迴圈和一些需要 sequence 的函數中(例如zip(), map()等等). 當iterable作為內建函數iter()的參數時，該函數會回傳該iterable的 iterator（迭代器）。Iterator可用來將包含一組值的集合拆開，一次取出其中一個值。在使用iterable，使用者通常不必自己呼叫__iter__()來產生iterator. Python中的 for 陳述式已經幫你把事情都處理好了：當你把一個iterable丟給for...in...時（例如for i in [1, 2, 3, 4, 5]），在執行迴圈時，會自動幫你產生一個iterator，並把該iterator賦予一個暫時的未命名變數。

iterable和iterator是用來稱呼同一件事的不同構成要素：可以把iterable想像成有待分配的素材，像是一籃裝有20顆籃球的籃子，籃子中的每一顆籃球都是籃子中的一份子。現在想把籃球發給班上20個人，但籃球不會自己長出腳來走到每個人的腳邊，因此需要指派體育股長，讓他一次從籃子中取出一顆籃球發給每個人，迭代器 (iterator)扮演的角色就如同體育股長一樣，每次從iterable中取出一個成員。

常見做法

Often the iterable classes will implement both iter() and next() in the same class, and have iter() return self, which makes the iterable class both an iterable and its own iterator. It’s perfectly fine to return a different object as the iterator, though.

能產生各種iterator的強大工具itertools

參考資料

• Iterables vs. Iterators vs. Generators
• DataCamp: Python Iterator Tutorial
• Python Practice Book: 5. Iterators & Generators
• Generator Tricks for Systems Programmers (v2.0) by (David M. Beazley)
• Generators: The Final Frontier (by David M. Beazley)
• Python3: itertools
• 為何要在 __iter__ 方法中回傳self: stackoverflow: What is the use of returning self in the iter method?

留言與分享

解決問題所依循的程序

以Dynamic Connectivity問題為例

問題的描述

輸入為一連串由一對對正整數所組成的序列，例如(2, 10), (0, 3), (4, 5)…，每個正整數代表的是某種類型的物件（可以代表社交網絡中的一個人、網絡中的一個節點等等），而一對正整數 (3, 10) 的意思是，將 3 與 10 「連在一起。

實際應用

• 網絡分析
• 程式語言中變數名稱的相等性
• 數學上的集合

開始製定Union-Find API

1
2
3
4
5
6
7
8
9
10
11

class UF:
    def __init__(self, n):
        self.id = [i for i in range(0, n)]
        
    def connected(self, a , b):
    
    # 找出位置  的元素
    def find(self, p):
    
    # 將 p 和 q 連在一起
    def union(self, p, q):

第一種實作: Quick-Find

留言與分享

Random access Machine

Pointer Machine

Python machine

更現代的Python結合以上兩種模型。

基本情況

List

Python中實作List的方式使用RAM模型，透過a_list[i]取得list中某一索引的元素，所花的時間為常數時間O(1)。

如果以linked list的方式來實作，那麼取出索引i的元素所花的時間即成為線性時間O(n)。

Object

如果一物件有適當數量的元素，那麼取出該物件屬性的執行時間也是常數時間O(1)。

幾個例子

list.append

使用 table doubling 方法（在之後的第九課將提到），使執行時間達到常數時間O(n)。

new_list = list1 + list2

上面的程式碼在底層其實是執行下方的程式碼。

1
2
3
4
5

new_list = []
for x in list1:
    new_list.append(x)
for y in list2:
    new_list.append(y)

因此可利用append()方法的執行時間來推導將兩個list相連在一起的執行時間: O(|list1| + |list2|)，即正比於兩個list的元素數量總和。

elm in a_list

線性時間O(n)，從第一個元素依序檢查到最後一個。

len(a_list)

常數時間O(1)，因為Python在底層已經先計算好並儲存每個list的長度。所以呼叫len(a_list)只是去叫出那個被儲存的值。

list.sort()

dict

以hash table實作，因此以dict[key]叫出該對應value的執行時間為常數時間O(n)。

Document distance Problem

目標

有兩份文件，想測量這兩份文件的距離，即這兩份文件的共通性。

應用

• Google index page
• Mirror of Wiki
• 檢查兩份期末報告是否互相抄襲

定義

• 文件:由words組成
• word: 為字元(a-z, A-Z, 0-9)組成的字串

概念

可以把兩份文件的共通性以兩份文件所包含字詞的共通性來思考。

主要步驟

1. 將文件分割為words
2. 算出每個word的出現頻率
3. 算兩個文件的word陣列的內積（即角度）

課程連結

MIT 6.006 Introduction to ALgorithms, Fall 2011

留言與分享