Fleurer.Lee

老师：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/

众所周知，lambda演算通过递归就可以图灵完备。好，用纯lambda演算写个递归吧。

等等，要递归必须得有名字，而lambda演算里赋予名字的唯一方式就是传递参数。像lisp那样define可不行啊。只能这样绕个圈子：

(\f.\x.
    (if  (= x 1)
        1
        (* x (f f  (- x 1)))))

这里把函数本身作为第一个参数传递给自己，从而实现的递归。要调用这个递归函数，还得套一个let（当然，换成lambda形式）:

((\fac. (fac fac 5))
        (\f.\x.
              (if (= x 1)
                    1
                    (* x (f f (- x 1))))))

真难看！每次递归都得把自己当作参数传递一遍，很机械！机械的活不应由人类做！想下，如果将递归函数里的(f f (- x 1))换成(f (- x 1))，或许还可以接受…好，Y组合子应运而生，现在你可以这样自然地递归了：

Y (\f.\x
     (if (= x 1)
          1
          (* x (f (- x 1))))) 5

数学家在追求美感上可是不遗余力啊。不过Y是如何做到的？

想想，Y组合子又叫不动点函数。什么是不动点？x=f(x)=f(f(x))…，这个x就是不动点：不管套多少层函数调用，在不动点上的值总是相等。Y f = f (Y f)=f (f (Y f))，这个Y f就是个不动点，高阶函数的不动点。什么是组合子？很简单，可以柯里化、没有自由变量的函数就是组合子 :)

便于理解，我们给(\f.\x (if (= x 1) 1 (* x (f (- x 1)))))这个lambda一个名字fac，看看一步步的递归是怎么来的：

Y fac 3
> fac (Y fac) 3         	//transform, Y!
> 3 * ((Y fac) 2)        	//3 !=1 so recurse
> 3 * (fac (Y fac) 2)    	//Y transform again
> 3 * (2 * ((Y fac) 1))       //2 !=1 so recurse
> 3 * (2 * (fac (Y fac) 1))   	//Y transform again
> 3 * (2 * 1)             	//1=1, so recursion ends.
> 6

就是这样了。里面有柯里化，也有惰性求值（缺一不可！）。一环套一环，然后就递归了。

Y组合子的定义：Y = \y. (\x.y (x x)) (\x.y (x x))，天知道大神（大神的名字叫做Haskell Curry! -v-）是怎么想出来的 =v=

不妨自己在纸上推倒一下(也只能在纸上推倒，这东西在实际的编程中貌似是没有应用的 :D)

58853867

原haskell交流群