Fleurer.Lee

发觉算法太弱了 =”=

当年在ACM那里呆了两天就隐身了，可惜那个老师非常非常非常好的（实验室里还有空调 >_<）。总觉得这玩意水太深，掉进去就出不来了....“不成熟的优化乃万恶之源”这话又正好应了惰性心理，心安理得地“出了性能问题再说之前先弄出来再说管算法干嘛”...可现实往往是，不会算法你压根就弄不出来...

先从一棵二叉查找树开始好了。挖坑慢慢填，时间有的是(?)

module BTree where
 
data BTree a b = Empty 
               | BNode {
                    kv :: (a, b), 
                    left :: BTree a b,
                    right :: BTree a b
               } 
               deriving(Show, Eq)
 
insert :: (Ord a) => (a, b) -> BTree a b -> BTree a b
insert (k,v) Empty = BNode (k, v) Empty Empty
insert (k,v) pnode@(BNode (pk, _) lnode rnode) 
    | k == pk   = pnode { kv = (k,v) }
    | k <  pk   = pnode { left  = insert (k,v) lnode }
    | k >  pk   = pnode { right = insert (k,v) rnode }
 
find :: (Ord a) => a -> BTree a b -> Maybe b
find k Empty = Nothing
find k (BNode (pk,pv) lnode rnode)
    | k == pk = Just pv
    | k <= pk = find k lnode
    | k >  pk = find k rnode
find _ _ = Nothing
 
remove :: (Ord a) => a -> BTree a b -> BTree a b
remove k Empty = Empty
remove k pnode@(BNode (pk,pv) lnode rnode) 
    | k == pk = merge lnode rnode
    | k <= pk = pnode { left = remove k lnode }
    | k >  pk = pnode { right = remove k rnode }
 
merge :: (Ord a) => BTree a b -> BTree a b -> BTree a b
merge lnode rnode = fromList $ (toList lnode) ++ (toList rnode)
 
--helper
isEmpty Empty = True 
isEmpty _     = False
 
fromList :: (Ord a) => [(a,b)] -> BTree a b
fromList = foldl (flip insert) Empty 
 
toList :: BTree a b -> [(a,b)]
toList Empty = [] 
toList (BNode (k,v) lnode rnode) = 
    (toList lnode) ++ [(k,v)] ++ (toList rnode)
 
-- for test
root = fromList $ [
    (4, "fleurer"), 
    (10, "ssword"), 
    (100, "ssword"), 
    (2, "xx")]

haskell做数据结构好像别扭的很…不用ST Monad或者IO的话什么都是值还不能引用，像二叉树的旋转什么的就没想出常数时间的办法。像上面那个remove就直接简单粗暴了orz

(邪恶音：用ST Monad不就好了嘛)
(ST Monad都用了还用haskell干嘛 TvT)

老师：Monad想到什么呢？
同学：毛茸茸的猫猫!

好同学们，请默念“Warm and Fuzzy”100遍~

。。
。。
。。
。
。
。
。
。
。

。
。
。
。。
。。

100遍了没。。。好，我们先看看State猫猫的类型吧 ^_^

newtype State s a = State { runState :: s -> (a, s) }

里面有个难看的record syntax，咱们无视之，改成：

data State g v = State (g -> (v, g))

就是一个lambda，外加一二元组：v表示猫猫正经计算中的值，g就表示猫猫的状态啦(就一个全局变量嘛)~那个lambda的参数g也一样。相应的猫猫Instance也就是如下：

instance Monad (State g) where
    return v = 
        State $ \g -> (v, g)
 
    (>>=) (State m) f = 
        State $ \g -> 
                let (v, g') = m g
                    (State m') = f v
                in  m' g'

还是一环套一环，函数编程没有变量，那就向下传递的时候改变它的值就行了。再加两个小喽骡：

get_g = State $ \g -> (g, g)
set_g v = State $ \_ -> (v, v)

全局变量的值不也在那个lambda的参数里么，get_g它设成计算中的值，这样在do-notation中就可以g <- get_g了。set_g则是把它的参数设到g里，而原先的g无视扔掉即可。

加个函数试验下：

run (State m) i = m i 
 
add1 :: State Int Int
add1 = do {
    g <- get_g;
    set_g $ g + 1;
}
 
add3 = do {
    add1;
    add1;
    add1;
}

进ghci输入run add3 1可得(4,4)，可见那个“全局变量”就这么变化了。

回头再想想它的类型，一个二元组不就够了嘛，为什么要套那层lambda呢？试下就知道

data State g v = State (g, v) 
 
instance Monad (State g) where
    (>>=) (State (g, v)) f = (g, f v)

看着不错，接着来：

    return v = ...

发现问题了没，return我们实现不了…搞不到原先g的值，链子就断在了这一环。解决方法就是把它推后，不是没有g么，于是放到参数里等着别人(>>=)给，这算不算惰性呢？ :)

ps:明白了State是怎么回事，附一山寨parsec ^_^ http://github.com/Fleurer/FParser

去年听王猫猫讲过之后就一直心安理得再也没看过Monad，以至于到昨天还不知State Monad为何物…囧

关于State Monad，似乎见过的教材都是拿随机数作例子，拿Monad跟一堆let对比，满眼的二元组绕啊绕啊，我给你个Monad让它不那么绕（存疑）～其实什么东西理解不了，往往就是因为不知道它怎么用（比如复变函数 =”=）

换个例子，像那个筛掉一个List中重复元素的nub函数多好….在命令式语言下边大约是这样：

def nub(xs)
    result=[]
    for x in xs
        if not result.include? x
	     result << x
    return result

若在函数式语言下边，用迭代大约是这样：

inub :: (Eq a) => [a] -> [a]
inub = inub' [] 
inub' rs [] = rs
inub' rs (x:xs) 
    | x `elem` rs    = inub' rs xs
    | otherwise     = inub' (rs++[x]) xs

inub’这个函数中有个rs参数，就相当于前面那个result变量。它的值会随着迭代发生改变，不同之处就是ts是引用透明的没有副作用。每次函数调用就是一个状态，状态就是一个值。

不喜欢给函数多加个参数怎么办？State Monad可以做到。在State Monad里面有两个函数可以使用：put，设置当前状态的值；get，获得当前状态的值。就相当于给函数加了一个（只有一个）可变的全局变量，在调用别的函数或者递归时这个值可以保留。

State Monad版本（我没觉得好看 =”=）：

mnub :: (Eq a) => [a] -> [a]
mnub xs = evalState (mnub' xs) []
mnub' [] = get
mnub' (x:xs) = do {
    rs <- get;
    if x `elem` rs then (do {
        mnub' xs;
    })
    else (do {
        put $ (rs++[x]);
        mnub' xs;
    });
}

原理大约就是do-notation中的每个语句都是用一个wrapper的类型包起来再不断往下传递么，而State的wrapper就是个类型为(a,s)的二元组（外加一层lambda？），每个语句的返回值放到s里，那个全局的值则放在a里…具体还有点迷糊，哪天推导下再说好了 >_<

译言前几天被杯具了，还好当初嗅到苗头全都抓了来 -v-

新地址见http://fleurer-lee.com/lyah。

用自己写的小工具生成的html，parser的代码不到200行，代码写的非常之perl，不过显然还算够用。
代码高亮用的一个jquery插件Chili，很容易扩展，随便改两个正则就自制了个haskell高亮。

顺便校对了下翻译。

• ChinaUnix上的朋友对“柯里函数”等译法的意见比较大，不过在校对中没有做修改。关于人名构成的术语，例如“Fourier transform”还是“傅立叶变换”，译者认为后者更好看。
• “Function Application”直译作“函数应用”，在这里译为“函数调用”。相应的“partial application”直译作“部分应用”，在这里译为“不全调用”。
• “predicate”在这里译为“限制条件”，因为译者认为“断言”这个词有点吓人。
• 保留了List，Tuple，List Comprehension等名词，不过将Triple之类译为“三元组”，“function with two parameters”译为“二元函数”。
• 把原先译文中“在处理数字时是非常有用的”类的句式改为“在处理数字时非常有用”，“的”真的是很别扭的。
• 有一节的标题“Texas Range”译为“德州区间”，因为译者老家在德州…囧

修改的比较仓促，bug依然还有很多。呵呵，欢迎提意见！ ^_^

update: 可以svn checkout它的源码：https://lyah-cn.googlecode.com/svn/trunk/

翻译：ssword
作者：J J O’Connor and E F Robertson
原文：http://www.gap-system.org/~history/Biographies/Curry.html

Haskell Brooks Curry

哈斯克尔•柯里的父亲塞缪尔•塞拉斯•柯里是波士顿Expression学校的校长，他母亲安娜•布里特则是这所学校的一位院长。高中时代的哈斯克尔并没有表现出对数学的特殊爱好，到1916年高中毕业的时侯，他还认为自己会成为一名医生。不久后，他进入了哈弗大学读本科，在医学的课程之余选修了数学。

影响他研究方向的一个重大事件就是1917年春，美国宣布了参与第一次世界大战。欲为祖国效力的柯里认为数学要比学医更有用—-当然，他也是喜欢数学，而且成绩非常好—-他就转到了数学系，并于1918年10月18日加入了学生军事训练营。战争不久就结束了（当年11月），12月9日柯里复员回到学校，继续数学专业的学习。1920年，柯里得到了一个A.B学位，顺利毕业。

柯里在通用电气公司找了一份电气工程师的工作，这一来就可以在业余时间中在麻省理工大学进修电气工程了。不过他很快就发现了自己与别人的不同：别人对待学习，都只是“答案正确即可”，而他则关心“答案为什么正确”。意识到自己更适合搞理论研究而非应用科学后，柯里于1922年转专业到物理学。在理论研究上，哈弗要更好，于是柯里作为了P W Bridgeman 在1922-1923学期的助教，回到了哈弗。1924年，柯里得到了物理硕士学位。也正在这时，他意识到自己不属于物理—-数学才是他的归宿。他开始在哈弗攻读数学博士学位。

转业期的柯里也有其他劳心事。他父亲在1921年不幸去世，其所有不动产都由柯里继承。而其中最大的不动产自然就是波士顿Expression学校。1924年他母亲去世的三年后，这所学校成为了一个股份公司。从创立伊始，柯里就一直担任公司的会计，不过1928年他就卖掉了它。

如果觉得柯里在1924年从此投身数学事业，那你就错了。他的研究方向本是George Birkhoff的微分方程理论，不过与此同时他开始接触了一些逻辑学的书籍，而且发现自己对逻辑更感兴趣。于是他咨询了哈弗的几位教授以及MIT的Norbert Wiener，自己是不是可以转专业到逻辑学，结果遭到了他们的一致反对。在担任1926-27的第一学期兼职讲师的时候，他阅读了罗素和怀特海的《数学原理》。这为他后来的研究奠定了基础，也就是使用组合子来分析复杂的代换规则的设想。他又去咨询哈弗的教授们和Norbert Wiener，问自己可不可以写篇逻辑方面的博士论文。这时他得到的回应却与上次大不相同，其中最典型的当属Wiener—-他说：如果你有话可说，就别碰逻辑；不过你显然有话可说！

于是，柯里转了最后一次专业。他放弃了微分方程的研究，而准备撰写一篇逻辑方面的博士论文。在Birkhoff的强烈推荐下，他决定在开始新专业的研究之前先去普林斯顿做一年讲师。随后他一边与Velben商讨着他的研究计划，一边翻着普林斯顿大学图书馆里的Mathematische Annalen，其中他们发现1924年M Schönfinkel的一篇论文über die Bausteine der mathematischen Logiküber die Bausteine der mathematischen Logik里有提到一种类似组合子的想法。Velben向柯里保证这是项有意义的研究，不过Alexander告诉他Schönfinkel现在在精神病院里而无法继续这项研究。柯里需要一名最好的博士导师，Velben就向他推荐德国哥廷根的Bernays。为了便于申请经费，柯里便事先公开了他关于组合子的想法，也就是1929年他的第一篇论文《逻辑代换的分析》（An analysis of logical substitution）在《美国数学报》（American Journal of Mathematics）的发布。

动身去哥廷根之前，1928年7月3日，柯里完成了与玛丽•弗吉尼亚•威利的婚事。他们在波士顿Expression学校初识，当时的玛丽还是个学生。随后，两人一起踏上了去德国的旅程。大约一年之后（7月24日），他提交了论文Grundlagen der kombinatorischen Logik。名义上虽是希尔伯特审阅，而天天给予对他帮助的人其实是Bernays。他的论文最终发表于1930年的《美国数学报》。

回到美国之后的1929年9月，柯里被宾夕法尼亚州立学院（即现在的宾夕法尼亚州立大学）聘请。次年7月27日，哈斯克尔和弗吉尼亚的女儿安妮•莱特•柯里出生了，1934年7月6日，他们的儿子罗伯特•威利•柯里出生。在大萧条刚开始时候，柯里能搞到这份工作是很幸运的。随后在大萧条期间，对数理逻辑学家而言就少有工作机会了。柯里在宾夕法尼亚大学担任教员直至1966年退休，他也在其他学校中呆了不少时间。尤其是芝加哥大学，他在1931-1932年间担任其国家研究委员；他也在1938-39年间担任普林斯顿的高级学会会员。其间他发表了一些论文，包括《组合子逻辑的全称量词》（The universal quantifier in combinatory logic，1931），《组合子理论的补遗》（ome additions to the theory of combinators，1932），《显式变量的组合逻辑观点》（Apparent variables from the standpoint of combinatory logic，1933），《组合逻辑中相等性及推导的几个性质》（Some properties of equality and implication in combinatory logic ，1934）。

1936年符号逻辑学会成立。作为创办者之一，柯里在1936-1937的两年里担任学会的发言人，后于1939-1940年间担任会长。1942年，他的离职演说《数理逻辑的组合子基础》发表于《符号逻辑期刊》（Journal of Symbolic Logic）。在里面，柯里先阐明了组合子逻辑的提纲，展示了与Church的lambda演算之间的密切联系，随后开始阐述他的近期工作。他检验了几种从不相容系统中导出悖论（如理查德和罗素悖论）的简便方法。他还为组合子逻辑引入了未定义的概念，如量词、形式推导。这一来，类似Church和Rosser的完备系统就可以推导出来。

40年代的柯里已经成为了世界顶尖的数理逻辑学家之一。此时，他被邀请做一个数学演说来解释下形式主义的基础概念，并提几个新的建议。这次演说的内容被记录在论文《数学严谨性问题的几个方面》（Some aspects of the problem of mathematical rigor）中，后发表于1941年的《美国数学论坛》。其中囊括了对非形式化理论的评论、形式系统的概念、演算的概念、对元理论的讨论、数学的定义、形式系统的可接受性，并讨论了直觉主义与形式主义之争。同在40年代，柯里与波士顿Expression学校重新建立了关系，此时该学校已更名为柯里学院。1940年，他加入了该校校董，并担任了十年。

第二次世界大战期间，柯里开始研究应用数学。1943年，他发表了《Heaviside演算》（the Heaviside operational calculas）。在其中，他阐述了一个简单的代数方法，对着它的不足也有所留意：

…优点，自然就是导出了方程解的约束条件，不过它只对有理数运算，如常项系数的线性微分方程适用。对于更一般的情况而言，如偏微分方程、小数运算等，数值变换理论必然是不可或缺的。

1942年5月到1944年1月，他在Frankford Arsenal工作。离开Frankford Arsenal之后，他在John Hopkins大学的应用物理实验室工作至1945年5月。随后，他去了一个军用武器测试点，即阿伯丁实验场。在那里他接触到了使用ENIAC电脑做的一些研究。1946年，《使用ENIAC的逆向插值法研究》和《使用ENIAC的四阶插值法研究》发布。1946年他回到宾夕法尼亚州立大学后，曾试图说服校领导购置一台电脑，不过失败了。

他的主要著作有《组合逻辑》（同Robert Feys合著）和《数理逻辑基础》（1963）。《组合逻辑》的编写工作始于1950年，当时柯里刚刚获得福尔布莱特奖，从而可以在Louvain与Robert Feys合作。柯里回到美国之后，他们依然保持着此书的合作，最后于1956年完成。E J Cogan论及此书，给了组合逻辑以极高的评价：

组合逻辑解释了数学中一般被认为是直觉而不予考虑的概念。像代换，一般就认为是变量的使用；像系统的类型抽象，通常是通过辅助手段引入，而不被当作系统的一部分。但在组合逻辑中，这些基础性的问题都可以由组合子理论解决。

在《数理逻辑基础》一书中，柯里使用Gentzen方法阐述了一个代数基础的论题。J Tucker说：

这方法最引人注目的地方就是，有循序渐进的规约：先是连词和或，再在后面章节中引入否定和量词。不像传统方法那样在开头将基本连词的含义一一列出，而是使用逻辑的推理将其一一导出。

1966年，他接受了阿姆斯特丹的逻辑学、逻辑史、科学哲学教授的职位。工作四年之后，他回到了宾夕法尼亚州立大学开始自己的离休生活。

[3]的作者高度评价了柯里和他的妻子：

柯里夫妇为人友善，美名远扬。哈斯克尔对同事和学生所做的一切，远多于自己。人若想找他说话，他会随时欢迎，在一同探讨问题的同时给予对方一切能及的鼓励…他办公室的门总是开着。这无疑也对我们研究组合子提供了莫大的鼓舞。不管住在何地，柯里的好客都是很有名的。他经常在家举行派对，而不拘泥形式。我想，弗吉尼亚的厨艺也烘培了我们对组合逻辑的兴趣！