Haskell類型推導
a = a + 1
在命令式編程的時代，區(qū)分一個人是否能學會編程的關鍵是看他能否理解a=a+1這個違反自然規(guī)律的表達式星虹，在函數式編程里，這個金絲雀測試變成了能否推導出下面這個函數的類型平夜。
f = const id
--const及id是prelude庫的庫函數
--const的作用是對于給定的兩個參數卸亮，返回第一個參數，const的類型信息如下
const :: a->b->a
--id的作用是段直，輸入任意值溶诞，返回這個給定的值，id的類型信息如下
id :: a->a
預備知識
柯里化
對于一個有n個參數的函數喧务，給定第一個參數，將返回一個結果是n-1個參數的函數功茴。那些沒有給出所有參數的函數應用被稱為函數的不完全應用（partitial application坎穿，有時候譯為偏函數調用）。而所生成的函數栖茉，就是柯里化函數。
Haskell中函數的結合順序是左結合
f = const id
類型推導
const的類型是a->b->a衡载，是一個有兩個參數的函數隙袁，const id是對const的不完全應用菩收，按照柯里化的定義，它會返回一個一元函數娜饵，函數的返回值類型就是函數id的類型箱舞，a->a拳亿。由此推導出f的類型: b->(a->a)。
f :: b->(a->a)
b->a->a與b->(a->a)是同一類型
我們對b->a->a進行柯里化肺魁，只應用第一個參數b，則返回一個參數為a寂呛，返回值為a的函數瘾晃，也就是(a->a)。因此蹦误，b->a->a與b->(a->a)是同一類型。也就是說最右邊的最外層括號是可以去掉的尚镰。
f :: b->a->a
lambda演算
const id a b
運用const id a狗唉，返回函數id
運用id b，返回b
由此也可以推導出const id的類型為：b->a->a
baby step
f = const const
const :: a->b->a
f = const const
函數是左結合的分俯，函數f是對第一個const進行柯里化缸剪，返回一個b->a的函數。而這里的a是const唬渗，它的類型是a->b->a。因此镊逝，f的類型為：
f::c->(a->b->a)
--等價方式
f::c->a->b->a
問題來了
f = const const
const的類型是a->b->a撑蒜，對左邊的const做柯里化座菠，變成了一個參數類型被b，返回值類型為a的函數浴滴，其中a被指定為const巡莹，類型為a->b->a甜紫。
那么問題來了，為什么f的類型不是b->a->b->a呢腰根？
原因在于a和b都是類型變量拓型，每一次對const的應用瘸恼，a和b可能代表不同的類型东帅。也就是說左邊const函數的參數b的類型與右邊const的b的類型不一定相同球拦，區(qū)別起見坎炼，分別用b和b1代表這兩個類型。
one more step
x0 :: t1 -> t2 -> (t1 -> t2 -> t) -> t
x0 = \x y z -> z x y
x1 = \y-> x0 y y
x2 = \y-> x1 $ x1 y
x1的類型推導
x1 = \y-> x0 y y谣光，x1對三元函數x0做了兩個參數的部分應用，返回的是一個參數類型為(t1 -> t2 -> t)蟀悦，返回值為t的函數熬芜。x1的參數是y福稳，用同一個參數作為t1和t2來部分應用x0的圆，因此t1半火、t2必須有相同的類型，都是y的類型梅掠。把y的類型指定為t1阎抒，則x1的類型為：
x0 = \x y z -> z x y
x1 = \y -> x0 y y
x1 :: t1->(t1->t1->t)->t
x2的類型推導
x2 = \y -> x1 $ x1 y
x2的參數是y消痛，由于$的作用，首先對計算右邊的x1 y逞带，即用y對x1做局部應用。記y的類型為t2展氓，x1 y返回的柯里化函數類型是：(t2->t2->t)->t遇汞，為后文描述方便勺疼，記為函數f。
接下來對左邊的x1做柯里化执庐，x1的第一個參數的類型就是函數f的類型轨淌。注意x2對x1做了兩次應用，兩次應用中t的類型有可能是不一樣的递鹉，為了避免混淆盟步，做alpha替換記f的類型為：(t2->t2->t1)->t1。
用f作為t1對x1做柯里化躏结，返回一個入參是類型是(t2->t2->t1)->t1)->((t2->t2->t1)->t1)->t却盘，返回值類型為t的函數。
因此媳拴，x2的類型為：
x2 ::
t2
-> (((t2 -> t2 -> t1) -> t1) -> ((t2 -> t2 -> t1) -> t1)
-> t)
-> t
