JavaScript = C + Lisp-Nirvana Studio ? Haskell :: 分享知识，传播技术

我在过去的几周内一直在写JavaScript代码──使用我们的对话框系统来个性化Mozilla。假设你要求：“嘿，电脑，我要教你如何在Amazon.com上找书。首先你象这样进入Amazon，然后在这里输入你要的书的名字。点击“Go”然后……”我的困难在于对Mozilla编码使我的对话框系统可以“看”浏览器中正在进行什么然后自己可以执行这些动作。
由于Mozilla中较高的层次是用JavaScript实现的。所以我一直在废寝忘食研究它（我的Rhino book里面全是我做的书签）我写的越多，我越觉得它像Lisp。
考虑以下代码：
semanticAccepter = acceptOnlyIf(acceptNot(emptyTextAccepter),scriptFilter,acceptAny(textAccepter,linkAccepter,formRelatedElementAccepter,linkImageAccepter));usefulContentOfThePage = new SemTree(semanticAccepter);
这里SemTree是一个对象，它允许你从一个HTML DOM 树中选出某些你感兴趣的节点，去掉那些你不感兴趣的节点。（根本上说，这是一个TreeWalker 类的包装器。）若要建立一个 SemTree ，你要给出一个接受器。一个接受器只是一个判断给定节点是否能被接受的一个函数：
function emptyTextAccepter(n) {return (n instanceof Text) && n.data.match(/^\s*$/);}
一旦有了一些基本的接受器和筛选器，很容易就可以定义组合筛选器──一种将筛选器以特殊形式组合起来的函数：
function acceptAny() {var disjuncts = arguments;return function(n) {for (var i = 0; i < disjuncts.length; ++i) {var shouldAccept = disjuncts[i](n);if (shouldAccept) return shouldAccept;}return false;}}
当它被调用的时候，以接受器作为参数，acceptAny返回一个新的接受器，可以接受只要是 disjuncts 能接受的那些给定节点 n。所以，semanticAccepter 中出现的acceptAny 能接受文本、链接、表单和链接中的图像。相反地，acceptOnlyIf只能接受被所有接受器组件接受的节点。acceptOnlyIf的定义类似于acceptAny：
function acceptOnlyIf() {var conjuncts = arguments;return function(n) {for (var i = 0; i < conjuncts.length; ++i) {var shouldAccept = conjuncts[i](n);if (shouldAccept != true) return shouldAccept;}return true;}}
acceptOnlyIf和acceptAny如此相似让我纳闷是否有一个通用的方法可以将任一个组合器（像否定、短路与、短路或）变成一个组合筛选器（象acceptNot、acceptOnlyIf、acceptAny）。的确有，但JavaScript不胜任这个任务。要完成这个，我们需要更强大的武器。
通过提供第一类型函数，JavaScript迈出了进入更广阔世界的第一步。而这个世界中最具影响的便是Haskell和它的一些变体。由于接受器告诉我们是否要接受一个节点，它们应该是一个从节点到布尔值的函数。在Haskell中，我们这样写：
type Accepter = Node -> Bool
这样，否定是一个布尔到另一布尔，合取和析取是从一个布尔的列表到一个单个布尔值，这样写：
not :: Bool -> Booland :: [Bool] -> Boolor :: [Bool] -> Bool
组合接受器有类似的形式：
acceptNot :: Accepter -> AccepteracceptOnlyIf :: [Accepter] -> AccepteracceptAny :: [Accepter] -> Accepter
我们给semanticAccepter下的定义和JavaScript版的类似：
semanticAccepter = acceptOnlyIf [acceptNot emptyTextAccepter,scriptFilter,acceptAny [textAccepter,linkAccepter,formRelatedElementAccepter,linkImageAccepter]];
我们怎样定义一个类似acceptOnlyIf的组合器？Haskell没有像一些语言中的命令结构。取代的是递归：
acceptOnlyIf [] n = trueacceptOnlyIf (a:as) n | a n = true| otherwise = acceptOnlyIf as n
由于某些原因，短变量名是Haskell中的标准。n是一个节点，a是一个接受器，as是一个接受器的列表。（以‘s‘结尾是代表某个变量是列表的标准形式。）你上面看到的定义是正确的，但我不常用这个方法。我会使用一个优美的小函数叫map：
map :: (a -> b) -> ([a] -> [b])map f [] = []map f (x:xs) = f x : map xs
当传了一个函数和一个列表，map返回对列表中的每个元素执行函数后生成的列表。有了map后，acceptOnlyIf就可以这样定义。
acceptOnlyIf as n = and (map (\a -> a n) as)
这里语法 (\a -> a n) 基本意思和JavaScript下面的一样：
function(a) {return a(n);}
整个acceptOnlyIf的定义本质上说明了，“给出一个节点n，找出每个接受器对n的值，然后返回这些值的合取值（和值AND）。”有了这种定义函数的优美方法之后，它们之间的相似之处立刻显现出来了：
acceptOnlyIf as n = and (map (\a -> a n) as)acceptAny as n = or (map (\a -> a n) as)
这样，泛化就是一些琐碎的事了：
liftCombiner :: ([Bool] -> Bool) -> ([Accepter] -> Accepter)liftCombiner c as n = c (map (\a -> a n) as)acceptOnlyIf = liftCombiner andacceptAny = liftCombiner or
现在我们是否可以更进一步了呢？我们是否可以也将 not搞成 acceptNot呢？and和 not的主要区别在于 and参数是一个布尔值的列表，而not只能针对单个布尔值。要更进一步泛化 liftCombiner，我们必须：
找出可以描绘出基本值和列表的共同特性的结构。
将这个结构应用到合成组合器的问题中.
Haskell 正好有我们所需要的。它称为单子Monad.
什么是单子？
之前就有人问过这个问题。单子到处可见。大多数结构和过程/进程像数据类型、函数、对象、、异常、I/O、副作用、同步、事务、分析器和编程语言，都可以接受单独的、原子的操作。组对（Pair）、元组（tuple）、列表、树、图──这些数据结构都有一个单子级的解释，是常常不止一个。由于是单子的东西太多了，所以很难对它们进行描述。不过我还是可以给你一个数学上的定义。但是正如“A continuation is the rest ofthe computation”所说的，给出单子的定义只有在你已经对它有了一些感性的认识才有用。否则直接给出定义只会混淆你的观点。那先让我们研究一下这个谦虚的列表作为我们受到单子启发的途径。
检验结构有很多方法。其中一个方法是查看各部分是如何一起工作来组成整体的。当以这种方法分析列表的时候，我们发现它们是连接的解码：一个列表要么是空的要么是一个由一个head和一个tail组成的Cons（一种构造函数，返回一个新的列表）。head是一个列表的元素，tail则是列表的其它部分。
data LinkedList a = Nil | Cons a (List a)
若要定义列表[1, 2, 3]，我们这样写：To define the list [1, 2, 3], we write:
oneTwoThree = Cons 1 (Cons 2 (Cons 3 (Cons Nil)))
Haskell中的列表就是这样工作的。除了用[]代表 Nil和用: 代表 Cons。逗号可以用来分隔条目，可以写成这样：
oneTwoThree = 1 : (2 : (3 : []))
链表有一个很长很有名的历史。不幸的是分解材料并不会显露出单子。
另一种分析列表的方法是通过研究它是如何和其它东西相关、进行交互的。Haskell提供了“class”机制根据和它们相关联的方法来定义对象。类似于抽象数据类型和接口：
class List ls wherenil :: ls acons :: a -> ls a -> ls ahead :: ls a -> atail :: ls a -> ls amap :: (a -> b) -> (ls a -> ls b)
这是一个看似完美的列表类，但它几乎没有从分解材料中抽象出什么东西。所有的方法，除了 map，都是特定于列表的逻辑结构的，map抓住了一个较抽象的概念。它将一个函数作为参数，然后返回一个被函数处理过新的列表。回忆一下 map 对定义 acceptAny 和 acceptOnlyIf 起了多大的帮助？这很明确是个值得研究的函数。
还有哪些其它函数对列表作为一个独立于它特定实现和形态的数据结构来说是至关重要的呢？好吧，还应该有一个方法 unit来把一个单独的元素放入一个列表，而且我们还需要一个 join 来将一个列表的列表组成一个长的列表。这个类定义像这样：
class List ls whereunit :: a -> ls amap :: (a -> b) -> (ls a -> ls b)join :: ls (ls a) -> ls a
以下是链表的实现：
instance List [] whereunit a = [a]map f [] = []map f (a:as) = f a : map f asjoin [] = []join [ls:lss] = ls ++ join lss
这些方法一目了然：unit将参数放入列表，map对列表中的每个元素执行函数，join将一个列表的列表连成一串。让我们确定一下串连接符（++）的定义吧：
(++) [] ls = ls(++) (k:ks) ls = k : (ks ++ ls)[1, 2, 3] ++ [4, 5, 6] --> [1, 2, 3, 4, 5, 6]unit 5 --> [5]map (\x -> x + x) [1, 2, 3] --> [2, 4, 6]join [[1], [2, 3], [4, 5, 6]] --> [1, 2, 3, 4, 5, 6]
这些函数都十分简单而且十分有用。它们确实是列表的标准成分，但就好比火药一样，如果你把它们正确地组合起来，你就能引爆一些东西：一个单子。我们等不及这个式子了：
class Monad m wherereturn :: a -> m a(>>=) :: m a -> (a -> m b) -> m b
就是它了。两个函数：return将一些东西放入单子中，同时（>>=），称为“绑定”，将一个单子变成另一个。我们立即来看看单子到底能做什么。不过首先为了明确起见，我们先将我们的列表实现扩展成应用一个单子：
instance Monad [] wherereturn a = [a](>>=) ls f = join (map f ls)
return定义和 unit一样：将它自己放入一个列表中。绑定 (>>=)将map 和 join 组合成一个操作。首先你将函数k映射到列表 ls ，然后由于 f返回一个列表的列表，你再用 join 将结果组成单个列表。
但单子这东西有什么好处呢？设想你想要将一个列表中的所有值和另一个列表中的值相加来产生一个大的列表：
sumTwoLists [1, 2, 3] [4, 5, 6] --> [5, 6, 7, 6, 7, 8, 7, 8, 9]
JavaScript代码应该像：
function sumTwoLists(ks, ls) {var result = [];for (var i = 0; i < ks.length; ++i) {for (var j = 0; j < ls.length; ++j) {result.push(ks[i] + ls[j]);}}return result;}
应用了单子我们可以这样写：
sumTwoLists ks ls = return (ks >>= \k ->ls >>= \l ->k + l)
代码看来很简练，但没什么特别的。幸运的是，由于单子是如此有用，所以更好的语法形式也出现很久了。我们应该这样写：
sumTwoLists ks ls = do k <- ksl <- lsreturn k + l
这称为“donotation做标记”为了明显起见。还有另一种变体，我个人喜欢叫“列表包含语法”或者“我无法相信这没有成为一个学说”：
sumTwoLists ks ls = [k + l | k <- ks, l <- ls]
不论哪种方法，都是所有的单子之上的一种较好语法。这种较好语法也许看上去像某种命令语言或什么蛇的东西（指Python语言──译注）。但我不接受其它替代语法，在Haskell中任何单子都能使用两者之一。
我们看看一个列表单子是如何工作的，但我们仅有的单子是 LinkedList。对于not，我们只需要一个直接变换值的单子就行了：一个一致单子。它不会对值做特殊的改变，仅仅直接返回值：
instance Monad Identity wherereturn a = a(>>=) a f = f a
现在我们终于可以完整地定义 liftCombiner了：
liftCombiner c as n = c [a n | a <- as]
现在“让组合器能工作在所有接受器上”的这个想法已经不难实现了：
acceptOnlyIf = liftCombiner andacceptAny = liftCombiner oracceptNot = liftCombiner not最后的思考
今天我们看了如何处理组合的接受器（从节点到布尔的函数），组合器可以是任何单子。结果接受器也是单子。你认为是否有一种方法，可以让组合器组合任意单子和其它单子（除了接受器之外）？如果有，怎样做？如果没有，单子之间要有怎样的关联才能这样？