单子一瞥

by

at 2012-05-21 06:25:00

original http://typeof.net/mechanix/a-glance-at-monad.html

在 JavaScript 开发里我们经常会遇到一些和顺序有关的情况，最常见的就是异步资源加载和处理

loadResource url, (resource) =>
    extractPicture resource, (picture) =>
        showPicture picture, (result) => null

也许你会说“你个狗 invis 为啥要把你的代码写成一个楼梯？这样不行吗？”

url |loadResource |extractPicture |showPicture

我倒是很想写成这样，多简单，多清楚，可是人家 API 是异步的啊！我要是照上面这么写，动不了啊！

另一个案例是列表综合。通常来说列表综合是数组上的“平映射”，即：

def ncat(a, b) = [].concat(a, b)
def flatmap(a, f) = a.map(f).reduce(ncat, [])

flatmap [1, 2, 3, 4, 5], (x) =>
    flatmap [1, 2, 3, 4, 5], (y) =>
        [x * y]

上面这个式子的计算结果是一个 25 个元素的数组。

另一个有趣的案例是“尝试性的取属性”。众所周知在 JavaScript 里，给 null 和 undefined 取属性会报异常，但是有时候编程时希望这个情况不报异常，而是返回 null。比如

a.b.c.d.e

如果 a.b == null，那么 JS 会毫不留情的给你个“试图取 null 的属性 c”的异常，但是经常我们需要直接得到 null，比如用在配置里的时候。这时我们可以用个方法来解决：

def type Flexy(o):
    def @val = o
    def @part(name) = piecewise
        when(o == null or o == undefined) new Flexy(o)
        otherwise                         new Flexy(o[name])

new(Flexy(a)).part('b').part('c').part('d').part('e').val

把这个方法稍微改一改就得到：

def type Flexy(o):
    def @val = o
    def @part(name, cb) = piecewise
        when(o == null or o == undefined) new Flexy(o)
        otherwise                         new Flexy(o[name])

new(Flexy(a)).part 'b', (b) =>
    b.part 'c', (c) =>
        c.part 'd', (d) =>
            d.part 'e', (e) =>
                e

上面的代码显示了一定的相似性：它们都是梯子形状的。（众人：……）为了进一步体现出这种相似性，把第一个例子和第三个改写成：

def bind(task, f) = task f

bind (loadResource url), (resource) =>
    bind (extractPicture resource), (picture) =>
        bind (showPicture picture), (result) => null

def part(name)(o)(cb) = piecewise
    when(o == null or o == undefined) cb o
    otherwise                         cb o[name]

def partBind(fPart, g) = (a) => 
    def b = fPart a
    b(g) b(itself)
def partRet(x) = () => x

def f = partBind (part 'b'), (b) =>
    partBind part('c'), (c) =>
        partBind (part 'd'), (d) =>
            partBind (part 'e'), (e) => 
                partRet(x)

f [b:[c:[d:[e: "oxox"]]]]

现在可以看出来了么？好好比较下

// 例 1
bind (loadResource url), (resource) =>
    bind (extractPicture resource), (picture) =>
        bind (showPicture picture), (result) =>
            null

// 例 2
flatmap [1, 2, 3, 4, 5], (x) =>
    flatmap [1, 2, 3, 4, 5], (y) =>
        [x * y]

// 例 3
partBind (part 'b'), (b) =>
    partBind part('c'), (c) =>
        partBind (part 'd'), (d) =>
            partBind (part 'e'), (e) => 
                partRet(x)

如果把例 2 里的 flatmap 给换成 bind，例 3 里 partBind 也换成 bind，那上面三个例子都有下面的形式：

bind x, (a) =>
    bind y, (b) =>
        bind z, (c) =>
            bind w, (d) => v

也就是说，对于“很多种”情况，我们都可以把它改写成使用 bind 和“楼梯”的形式。比如对异步资源加载，bind 形式就是：

def bind(task, f) = task f

对于列表综合，bind 形式是：

def ncat(a, b) = [].concat(a, b)
def bind(a, f) = a.map(f).reduce(ncat, [])

除了 bind 定义不同之外，这三种目的迥异的应用其实有着一样的形式，他们都会串接某种“动作”（尽管从你看来数组根本不像是“动作”）和一个返回“动作”的函数。所谓“单子”就是来抽象这种东西的。单子是一个泛型类综（Type class，相当于元类/接口），如果 M 是一个单子，则 M(T) 有以下接口：

return(t) 方法：把一个 T 类型对象转换成 M(T) 类型，相当于从一个值生成一个平凡动作。
bind(m, f) 方法：把一个 M(T) 对象 m 和一个从 T 生成 M(T) 的函数 f 绑定复合成一个新的单子 M(T) 对象。这相当于把两个动作相互连接，同时还能处理第一个动作的返回值。

对于列表综合来说，return(t) = [t]，bind(m, f) = m.map(f).reduce(ncat, [])；对异步调用来说，return(t) = (f) => f(t)，bind(task, f) = task(f)。但是这样我们仍然得把程序写成楼梯，但是有了统一的形式后，如何“铲平”楼梯就变得容易多了。Moe 编译器就提供了两种内建语法，<- 和 ! 来帮你铲平楼梯，构建单子。

table =>
    x <- [1, 2, 3, 4, 5]
    y <- [1, 2, 3, 4, 5]
    return x * y

这是 Moe 内建的单子原语形式，它引入了个新符号 <-，用来表示 bind。在编译器处理后，它和下面的代码等价：

table [build: fBuild]
where fBuild(schemata)()() =
    schemata.bind [1, 2, 3, 4, 5], (x) =>
        schemata.bind [1, 2, 3, 4, 5], (y) =>
            schemata.return (x * y)

还是楼梯，不过这次的楼梯是编译器生成的，不是你人肉写的，啊哈哈感觉好好！同时可以清楚的看到，bind 和 return 是对象 schemata 的方法——符合单子的定义。没办法，JavaScript 是动态类型，所以不能从代码内文推断出你写的单子是哪一种，只能手工传入，索性无伤大雅，毕竟你写列表综合的时候也肯定觉得，明确写出 table {...} 比利用类型推断出 {...} 是列表综合要舒服。这里的 table 实现相当简单。（当然这是个简化的实现，Moe Prelude 里的 bind，传给 bind 的第一项是任意可迭代对象，实现也要复杂的多。）

def table(G) = 
    def ncat(a, b) = [].concat(a, b)
    def bind(a, f) = a.map(f).reduce(ncat, [])
    def ret(x)     = [x]
    def schemata   = [bind: bind, return: ret]

    G.build(schemata)()()

part 的例子也许会有些难理解，那个单子是状态单子（State monad）的变体，状态单子 State(t) 是个函数，表示“对状态的一次修改”（其实是生成新状态啦）。它的 return 形式如下：

def stateRet(t)(s) = 
    ...
    return [value: t, state: s]

它的 bind 定义是这样：

def stateBind(m, k) = (s) =>
    def [value: a, state: s1] = m s
    k(a) s1

一个状态单子实际上是对某个状态进行修改的函数，因此它的绑定复合就是对状态的连续修改。例 3 的 partBind 就和这里的 stateBind 很相似，事实上可以方便的改写成标准的状态单子形式：

def part(name) = (s) =>
    if(s) [value: s[name], state: s[name]]
    else  [value: s, state: s]
def stateBind(m, k) = (s) =>
    def [value: a, state: s1] = m s
    k(a) s1
def stateRet(x) = (s) => [value: x, state: s]

def f = stateBind part('b'), (b) =>
    stateBind part('c'), (c) =>
        stateBind part('d'), (d) =>
            stateBind part('e'), (e) => stateRet(e)

trace (f [b: [c: [d: [e: ".b.c.d.e is here!"]]]]).value

（未完待续。）

Google Reader

单子一瞥

单子一瞥

by

at 2012-05-21 06:25:00

original http://typeof.net/mechanix/a-glance-at-monad.html