生者有涯，知则无涯。故不敢不勉力为之。
使用教材：《learn you a Haskell》，1-8章戳我
准备工作。
编译器&调试器：安装Haskell Platform，也就是著名的GHC；
文本编辑器：
①安装Eclipse（最新的是4.2），安装EclipseFP，根据Extra configuration steps安装一些必要的插件；
②安装GVIM，调教一下_vimrc；
③安装leksah，虽然这是一个IDE，但是仍然需要和GHC配合工作；
④使用其他Editor，比如Emacs、Yi甚至notepad等；
其实像Haskell这种小众语言，还是用Vim或者Emacs更好一些，这里推荐一个VIM，里面已经修正了对haskell的一些支持，并且加入了补全系统。
不过如果写大的工程文件的话，个人感觉Eclipse更方便一些。
Haskell的基本思想：高等抽象，不依赖于计算机模型。语法尽量接近数学上的表达式。
例如，在数学上一元函数表达式为，在haskell中对应的函数就是f x = x + x，除了将括号换成空格，其余都一样。二元函数也类似，对应的Haskell函数也就表示为 g x y = x*3 + y*5，我们也可以定义，在Haskell中对应的也就是：h x y = f x + g x y，很明显具有形式上的一致性。
条件函数：
条件函数对应Haskell中的if语句，与其他编程语言不通但是与数学上的函数相同的是：每个if必须对应一个else，不可以省略。对于上述函数，这里的表达式显然是：
smallNumber x = if x&100
在haskell中，如果一个函数没有参数，那么它是一个"定义"，也就是其他语言中的"常量"(在ghci下使用关键字let来定义)。
为了书写的方便，可以通过使用`操作符将前缀函数变成中缀函数，例如div x y=x/y,在实际调用时可以写成 x `div` y。
另外需要注意的是，在Haskell中所有函数的首字母都不能大写。
list（序列）与其他语言中的array（数组）是相对应的，虽然在STL中list表示的是"链表"。list的特点：单类型，这点和array显然是一致的，不同的是list可以嵌套list，而且这些list的长度可以不同（类型必须相同）。list的表达形式如：[1,2]，在方括号中放入元素，以comma分隔。字符（串）字面值的表达方式与C一致。字符串就是字符的list，所有适用于list的操作都可以直接用在字符串上。
list的特性比较像stack，可以使用 ++ 操作符进行pushback操作，但是haskell需要遍历整个list，效率很低。但是如果使用 : 操作符进行pushfront操作，速度就很快。需要注意的是++操作符的右表达式必须也为list，如果是单个元素，就放入[]，而 : 操作符的左表达式必须为元素，如果需要插入多个元素，就按次序分开插入（:表达式的执行顺序是自右向左）。下标运算符!!，下标从0开始计算。list的比较方式同C中strcmp。
与C语言中array最大的不同之处在于list是haskell原生支持类型，也就是可以直接以"字面值"存在的类型，而C中的array必须以variable形式存在。所以在haskell中可以直接使用函数操作list，常用的几个函数：
head:返回头部；
tail：返回去掉头部的其他部分（尾部）；
last：返回最后一个元素；
init：返回除了最后一个元素的其他部分；
length：返回长度；
null：检测是否为空；
reverse：反转序列；
take n list:从list中取前n个元素组成list，n&=0,如果n=0，得到一个空list；
maximum/minimum：得到最大/小元素（list中的元素必然可以比较）；
sum：求和；
elem x list:判断x是否存在于list中；
list的Range特性仍然是来源于数学，比如常数集{x}，x取1到100，一般写作{x}={1,2,3..100}，在list中也可以这么干，写出前两个元素确定step，两个点号表示range，最后是上/下界（由于计算机本身的限制，最好不要在浮点数中使用range特性）。如果不标上/下界的话，我们会得到一个无限长的list（显然这在数学上是合法的），haskell为了尽量与数学抽象一致，引入了"惰性求值"的特性，也就是说，haskell不会管这个无限长的list，只在你需要它的一部分时，再处理这个一部分。
生成list的一些函数：
cycle list：生成重复的无限长序列；
repeat n：生成仅含有n的无限长序列
replicate n x：生成含有n个x的序列
List comprehension
list comprehension来源于数学中的集合表达式，如，在haskell中表示为[x*2 | x &- [1,2..10] ].如果有多个条件，就用comma隔开，表示取所有满足条件集合的交集。例如对应于[x*2 | x &- [1,2..10], x*2 &=12].在 | 左边是取值，右边是filter的条件。&-表示"属于"，如果不关心取出的值，可以用_ &- []这种形式，可以省去一个变量名。对于嵌套的list类型，可以写出对应的嵌套list comprehension，用 | 隔开过滤条件。
Tuple（元组）与list的特性正好相反：每个tuple可以装不同类型的元素；两个tuple只有元素个数和对应次序的元素类型都相同时，才能视为同一类型。如果用C语言来比较的话，和一个defined的struct类型有行为上的一致性。如果要嵌套list和tuple，注意list要求类型的一致，而tuple类型一致的条件是很苛责的。tuple的表达行式是(x,y)，括号内至少有两个元素，因为有一个元素没有什么意义（想一想只有一个元素的struct），空的tuple也就是()也算是一种类型。tuple不能增加或者减少元素，不同类型的tuple也不能相互比较。
只有两个元素的tuple通常称为pair（序对），和STL中的pair一致。pair常用的操作函数：
fst：返回首项；
snd：返回次项；
zip list1 list2：将两个list中的元素进行交叉配对，返回一个由pair组成的list；如果两个list中的元素个数不一致，以较短的那个为界；
第二章 类型与类型类
Haskell是静态类型语言，但是与C++或者java不同的是，haskell有类似动态语言中的自动类型推导特性（C++11中引入auto关键字后也有了此特性）。在ghci中可以使用:t 来解析表达式或者函数，返回形如 表达式::类型 的结构。其中 :: 符号表示类型约束，在声明函数时也可使用该符号来明确定义域和值域。
如：addThree :: Int-&Int-&Int-&Int
addThree x y z= x+y+z
使用-&符号分隔参数，返回值类型在最后（显然每个函数只能返回一个值）。常见类型包括：Char，Int，Integer（前者有界，后者无界但是效率不如前者），Float，Double，Bool。所有类型的首字母大写。
类型类，类型类的概念类似于java中的"接口"，它规定了满足一系列特性的类的集合。常见的类型类包括：Eq（相等性），Ord（可比较性，返回LT、GT、EQ等），Show（可显示性，对应函数show），Read（与Show相反，对应函数read可以将字符串转为需要的类型，形式是read x ::type或者让read根据所在的表达式自己推断需要的类型如 read "3.5"+4），Enum（可枚举性，即可以用succ和pred得到后继或者前驱值），Bounded（有界性，可以使用minBound和maxBound函数获得上下界），Num（数字类型），Integral（整数类型），Floating（浮点类型）。
使用=&符号来声明类型类的约束，如fromIntegral :: (Integral a, Num b) =& a -& b（这个函数用于将整数类转换成更通用的Num类型）
第三章 函数的语法
模式匹配的本质就是一大串swith…case，或者说if…else if…这些，遇到第一个匹配值后就会跳出该函数（有些类似C++中try…catch的匹配过程）。这里举著名的斐波那契数作为例子。我我们知道Fibonacci sequence的数学定义为
那么对应的Haskell代码为
fibonacci :: ( Integral a) =&a-&a
fibonacci 0=0
fibonacci 1=1
fibonacci x=fibonacci (x-1) + fibonacci (x-2)
显然这段代码与公式(2)具有形式上的一致性。注意这里没有约束x&=0，所以匹配不是健全的。
对list进行模式匹配，常见的方法是将list分解为(x:xs)，x匹配head，xs匹配tail，但是不能用++进行分割，原因很简单，因为++作用于list而不是元素。操作符@匹配全体引用，例如all@(x:xs)，就意味着可以用all来代替(x:xs)，这被称为as模式。
门卫（guard）是与模式匹配配合使用的，它的作用是增加过滤条件。对于区间匹配的条件函数，使用门卫是很简洁而恰当的。Guard的语法：在函数和=之间插入 | guard。
关键字where用于在函数中进行变量或者函数的声明，一般放置在guard函数之后。在where函数中声明的辅助函数中可以嵌套使用where，这样就可以把一个复杂的表达式通过换元表达为几个符合的简单函数式。
完善上面的fibonacci函数，将第4行改为
fibonacci x
| otherwise = fibonacci (x-1) + fibonacci (x-2)
当然这里让x&0的时候返回一个负值并不是很恰当，不过这样不会有异常抛出了。
今天的复习就到这里：）
阅读(...) 评论()haskell的IDE——leksah编译过程 - Haskell - Tech - ITeye论坛
haskell的IDE——leksah编译过程
锁定老帖子
精华帖 (0) :: 良好帖 (3) :: 新手帖 (0) :: 隐藏帖 (0)
等级: 初级会员
来自: 深圳
发表时间：&&
相关知识库：
&&&&&&& 对haskell一直比较有兴趣，但是苦于没有一个好的IDE工具，不能做到编码运行调试一条龙。在网上看到国外有牛人用haskell本身写了一个IDE——Leksah。但是它还处于bata状态，没有现成的安装包，只能从源代码编译安装。周末有空的时候试了一下，把过程写出来，希望起个抛砖引玉的作用。
&&&&&&& Leksah的编译过程在它的wiki上有详细的描述，传送门。我在windows和ubuntu下都有尝试，但是只在ubuntu下面成功了。windows下面一直说有些包找不到，明明已经安装了也不行，可能是因为我用的是GHC 6.10.2，路径设置不太对。那位牛人成功了，指点一下。我比较希望在windows下面编译出来之后，自己打个包，能发到公司去用。
&&&&&&& ubuntu我用的是kubuntu 9.04，GHC是6.10.2。编译详细过程仍然参照wiki，只是有两个要注意的地方。一个是刚开始sudo aptitude build-dep ghc6的时候，会报一个darc-grep依赖不满足的问题。这个问题可以忽略，这个包太老了，已经有新的包来代替它了。而且这一步只是安装一下编译GHC需要的工具和库，所以没关系。第二个问题是后面编译GHC的时候，我的ubuntu是中文环境，这种情况下会报一个编译错误。原因是在中文环境下，#被错认成别的东西。解决方法也很简单，在开始编译之前先在shell下执行一下 export LC_ALL=C 将locale切换成POSIX即可。
&&&&&&& 这篇文章本来早就写好了，本来想等有一些使用经验以后一些发一下，但是最近一直没空。所以先把这篇发出来，希望有兴趣的人，编译使用之后，把使用感受也发一下。
等级: 初级会员
来自: 深圳
发表时间：&&
最近出了一个Haskell Platform，好像就是把常用的一些扩展库打包到一起。应该配置起来更简单一些，回头试一下。http://hackage.haskell.org/platform/
请登录后投票
等级: 初级会员
来自: 成都
发表时间：&&
還有個yi，可以嘗試一下。看起來像emacs的haskell移植。
请登录后投票
来自: 杭州
发表时间：&&
http://leksah.org/Leksah-0.6.1.0.exe 这个下载下来,不能直接安装跑么?
请登录后投票
night_stalker
文章: 1366
来自: 杭州
发表时间：&&
dogstar 写道http://leksah.org/Leksah-0.6.1.0.exe 这个下载下来,不能直接安装跑么?
lz 发这个帖子的时候，一键安装包还没出来。
请登录后投票
跳转论坛:移动开发技术
Web前端技术
Java企业应用
编程语言技术&img src=&/50/v2-cdaa6b160f5_b.jpg& data-rawwidth=&8000& data-rawheight=&3406& class=&origin_image zh-lightbox-thumb& width=&8000& data-original=&/50/v2-cdaa6b160f5_r.jpg&&&p&最近喜欢上通勤路上听 podcast 了。本来是一个人去吃火锅时听的，不过刚发现通勤路上听也很适合，一集差不多一小时，从地铁站出来正好听完，听熟悉话题的 podcast 对放松身心很有帮助，听到熟悉的梗还能会心一笑，偶尔还能有点启发，以前看不懂的 paper 啥的一下子好像就有点感觉了。所以在这里推荐一下，大家有好的也欢迎在评论补充。&/p&&p&&a href=&/?target=https%3A///category/podcasts/& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Podcasts | Functional Geekery&i class=&icon-external&&&/i&&/a&&/p&&p&已经做了上百个 episode，更新勤快，邀请嘉宾背景相当丰富。&/p&&p&&a href=&/?target=http%3A///& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&The Haskell Cast&i class=&icon-external&&&/i&&/a&&/p&&p&顾名思义，主要是 Haskell 向的节目。推荐最近的两集，Richard Eisenberg 讲 Haskell 中 dependent type 的一集，以及 John Wiegley 讲 Compiling to Categories 和 Writing Haskell with Coq 的一集（两项都是 ICFP'17 发表的工作）。&/p&&p&&a href=&/?target=http%3A///& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&The Type Theory Podcast&i class=&icon-external&&&/i&&/a&&/p&&p&类型论相关的播客，对我来说相当硬核了。Stephenie Weirich 的那一集也有讲 Haskell 中依赖类型，还有 Edwin Brady 介绍 Idris 设计的一集也相当不错，对 Idris 感兴趣的同学不要错过。&/p&&p&后记：9月份空余时间多不少，有许多坑可以填一下了（笑&/p&
最近喜欢上通勤路上听 podcast 了。本来是一个人去吃火锅时听的，不过刚发现通勤路上听也很适合，一集差不多一小时，从地铁站出来正好听完，听熟悉话题的 podcast 对放松身心很有帮助，听到熟悉的梗还能会心一笑，偶尔还能有点启发，以前看不懂的 paper 啥…
&img src=&/50/v2-5aa5b971b51772baaff0fc0ba7144d3d_b.jpg& data-rawwidth=&1920& data-rawheight=&1080& class=&origin_image zh-lightbox-thumb& width=&1920& data-original=&/50/v2-5aa5b971b51772baaff0fc0ba7144d3d_r.jpg&&&p&原文在我博客：&a href=&/?target=http%3A//ice1000.org//HaskellParsers2/& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&使用 Haskell 编写灵活的 Parser （下）&i class=&icon-external&&&/i&&/a&&/p&&p&上一篇也是：&a href=&/?target=http%3A//ice1000.org//HaskellParsers/& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&使用 Haskell 编写灵活的 Parser （上）&i class=&icon-external&&&/i&&/a&&/p&&p&本篇主要讲 Parser Combinator 的组合，比如二元运算符的解析以及优先级结合性的处理。&/p&&h2&some 与 many&/h2&&p&上篇还剩下一个内容，就是 some 和 many 。这两个函数是 Control.Applicative 内置的，可以直接拿来用。&/p&&p&比如我们可以有一个解析空字符串的 Parser ：&/p&&div class=&highlight&&&pre&&code class=&language-haskell&&&span&&/span&&span class=&c1&&-- | one or more&/span&
&span class=&nf&&spacesP&/span& &span class=&ow&&::&/span& &span class=&kt&&Parser&/span& &span class=&kt&&String&/span&
&span class=&nf&&spacesP&/span& &span class=&ow&&=&/span& &span class=&n&&some&/span& &span class=&o&&$&/span& &span class=&n&&oneOf&/span& &span class=&s&&& &/span&&span class=&se&&\n\r\t&/span&&span class=&s&&&&/span&
&span class=&c1&&-- | zero or more&/span&
&span class=&nf&&spaces0P&/span& &span class=&ow&&::&/span& &span class=&kt&&Parser&/span& &span class=&kt&&String&/span&
&span class=&nf&&spaces0P&/span& &span class=&ow&&=&/span& &span class=&n&&many&/span& &span class=&o&&$&/span& &span class=&n&&oneOf&/span& &span class=&s&&& &/span&&span class=&se&&\n\r\t&/span&&span class=&s&&&&/span&
&/code&&/pre&&/div&&p&非常简单，对吧。它们看起来也很直观。&/p&&h2&其他小工具&/h2&&p&另外，为下文做准备，我们先加上这几个 Parser 。他们的意义看名字就知道，不再介绍。&/p&&div class=&highlight&&&pre&&code class=&language-haskell&&&span&&/span&&span class=&kr&&import&/span& &span class=&nn&&Data.Char&/span&
&span class=&nf&&stringP&/span& &span class=&ow&&::&/span& &span class=&kt&&String&/span& &span class=&ow&&-&&/span& &span class=&kt&&Parser&/span& &span class=&kt&&String&/span&
&span class=&nf&&stringP&/span& &span class=&p&&[&/span&
&span class=&p&&]&/span& &span class=&ow&&=&/span& &span class=&n&&return&/span& &span class=&kt&&[]&/span&
&span class=&nf&&stringP&/span& &span class=&p&&(&/span&&span class=&n&&c&/span& &span class=&kt&&:&/span& &span class=&n&&cs&/span&&span class=&p&&)&/span& &span class=&ow&&=&/span& &span class=&kr&&do&/span&
&span class=&n&&charP&/span& &span class=&n&&c&/span&
&span class=&n&&stringP&/span& &span class=&n&&cs&/span&
&span class=&n&&return&/span& &span class=&o&&$&/span& &span class=&n&&c&/span& &span class=&kt&&:&/span& &span class=&n&&cs&/span&
&span class=&c1&&--&/span&
&span class=&nf&&reservedP&/span& &span class=&ow&&::&/span& &span class=&kt&&String&/span& &span class=&ow&&-&&/span& &span class=&kt&&Parser&/span& &span class=&kt&&String&/span&
&span class=&nf&&reservedP&/span& &span class=&ow&&=&/span& &span class=&n&&tokenP&/span& &span class=&o&&.&/span& &span class=&n&&stringP&/span&
&span class=&nf&&natP&/span& &span class=&ow&&::&/span& &span class=&kt&&Parser&/span& &span class=&kt&&Int&/span&
&span class=&nf&&natP&/span& &span class=&ow&&=&/span& &span class=&n&&read&/span& &span class=&o&&&$&&/span& &span class=&n&&some&/span& &span class=&n&&digitP&/span&
&span class=&nf&&digitP&/span& &span class=&ow&&::&/span& &span class=&kt&&Parser&/span& &span class=&kt&&Char&/span&
&span class=&nf&&digitP&/span& &span class=&ow&&=&/span& &span class=&n&&satisfy&/span& &span class=&n&&isDigit&/span&
&span class=&nf&&tokenP&/span& &span class=&ow&&::&/span& &span class=&kt&&Parser&/span& &span class=&n&&a&/span& &span class=&ow&&-&&/span& &span class=&kt&&Parser&/span& &span class=&n&&a&/span&
&span class=&nf&&tokenP&/span& &span class=&n&&p&/span& &span class=&ow&&=&/span& &span class=&kr&&do&/span&
&span class=&n&&a&/span& &span class=&ow&&&-&/span& &span class=&n&&p&/span&
&span class=&n&&spaces0P&/span&
&span class=&n&&return&/span& &span class=&n&&a&/span&
&span class=&c1&&--&/span&
&/code&&/pre&&/div&&h2&chainl1 与 chainr1&/h2&&p&首先，我们考虑这样两种 Parser 。&/p&&ol&&li&解析一个运算单元&/li&&li&解析一个运算符&/li&&/ol&&p&看起来是个半群，不过这并不是重点。我们以整数和加减法作为具体的例子，然后可以考虑写出对应的 Parser 。&/p&&div class=&highlight&&&pre&&code class=&language-haskell&&&span&&/span&&span class=&c1&&-- the parsers&/span&
&span class=&nf&&numberP&/span& &span class=&ow&&::&/span& &span class=&kt&&Parser&/span& &span class=&kt&&String&/span&
&span class=&nf&&numberP&/span& &span class=&ow&&=&/span& &span class=&kr&&do&/span&
&span class=&n&&s&/span& &span class=&ow&&&-&/span& &span class=&n&&stringP&/span& &span class=&s&&&-&&/span& &span class=&o&&&|&&/span& &span class=&n&&return&/span& &span class=&kt&&[]&/span&
&span class=&n&&cs&/span& &span class=&ow&&&-&/span& &span class=&n&&some&/span& &span class=&n&&digitP&/span&
&span class=&n&&spaces0P&/span&
&span class=&n&&return&/span& &span class=&o&&$&/span& &span class=&n&&s&/span& &span class=&o&&++&/span& &span class=&n&&cs&/span&
&span class=&c1&&--&/span&
&span class=&nf&&plusSymbolP&/span& &span class=&ow&&::&/span& &span class=&kt&&Parser&/span& &span class=&kt&&String&/span&
&span class=&nf&&plusSymbolP&/span& &span class=&ow&&=&/span& &span class=&kr&&do&/span&
&span class=&n&&stringP&/span& &span class=&s&&&+&&/span&
&span class=&n&&spaces0P&/span&
&span class=&n&&return&/span& &span class=&s&&&+&&/span&
&/code&&/pre&&/div&&h2&AST&/h2&&p&沿用一下上次类似的 AST 表述。&/p&&div class=&highlight&&&pre&&code class=&language-haskell&&&span&&/span&&span class=&cm&&{-# LANGUAGE DeriveFunctor #-}&/span&
&span class=&kr&&data&/span& &span class=&kt&&OpTree&/span& &span class=&n&&a&/span& &span class=&n&&b&/span& &span class=&ow&&=&/span& &span class=&kt&&Term&/span& &span class=&n&&b&/span&
&span class=&o&&|&/span& &span class=&kt&&Op&/span& &span class=&p&&(&/span&&span class=&kt&&OpTree&/span& &span class=&n&&a&/span& &span class=&n&&b&/span&&span class=&p&&)&/span& &span class=&n&&a&/span& &span class=&p&&(&/span&&span class=&kt&&OpTree&/span& &span class=&n&&a&/span& &span class=&n&&b&/span&&span class=&p&&)&/span&
&span class=&kr&&deriving&/span& &span class=&p&&(&/span&&span class=&kt&&Show&/span&&span class=&p&&,&/span& &span class=&kt&&Eq&/span&&span class=&p&&,&/span& &span class=&kt&&Functor&/span&&span class=&p&&)&/span&
&/code&&/pre&&/div&&p&这个也很清晰，比如 1+1 的 AST 就是：&/p&&div class=&highlight&&&pre&&code class=&language-text&&&span&&/span&Op (Term &1&) &+& (Term &1&)
&/code&&/pre&&/div&&h2&问题&/h2&&p&但是我们这里有一个巨大的问题。当我们在描述一颗复杂语法树的时候，比如 1+1+1+1 这种好几个二元运算符组合起来，我们需要&/p&&div class=&highlight&&&pre&&code class=&language-haskell&&&span&&/span&&span class=&nf&&p&/span& &span class=&ow&&=&/span& &span class=&kr&&do&/span&
&span class=&n&&n1&/span& &span class=&ow&&&-&/span& &span class=&n&&numberP&/span&
&span class=&n&&plusSymbolP&/span&
&span class=&n&&n2&/span& &span class=&ow&&&-&/span& &span class=&n&&numberP&/span&
&span class=&n&&plusSymbolP&/span&
&span class=&n&&n3&/span& &span class=&ow&&&-&/span& &span class=&n&&numberP&/span&
&span class=&n&&plusSymbolP&/span&
&span class=&n&&n4&/span& &span class=&ow&&&-&/span& &span class=&n&&numberP&/span&
&span class=&n&&return&/span& &span class=&o&&$&/span& &span class=&kt&&Op&/span& &span class=&p&&(&/span&&span class=&kt&&Op&/span& &span class=&p&&(&/span&&span class=&kt&&Op&/span& &span class=&p&&(&/span&&span class=&kt&&Term&/span& &span class=&s&&&1&&/span&&span class=&p&&)&/span& &span class=&s&&&+&&/span& &span class=&p&&(&/span&&span class=&kt&&Term&/span& &span class=&s&&&1&&/span&&span class=&p&&))&/span& &span class=&s&&&+&&/span& &span class=&p&&(&/span&&span class=&kt&&Term&/span& &span class=&s&&&1&&/span&&span class=&p&&))&/span& &span class=&s&&&+&&/span& &span class=&p&&(&/span&&span class=&kt&&Term&/span& &span class=&s&&&1&&/span&&span class=&p&&)&/span&
&/code&&/pre&&/div&&p&这种复杂而傻逼的 Parser 。&/p&&h2&抽象&/h2&&p&为了解决这个问题，我们首先重构一下 plusSymbolP ，把所有的二元运算抽象成一个新的 Parser 。&/p&&div class=&highlight&&&pre&&code class=&language-haskell&&&span&&/span&&span class=&c1&&-- | binary operators&/span&
&span class=&nf&&binOp&/span& &span class=&ow&&::&/span& &span class=&kt&&String&/span& &span class=&ow&&-&&/span& &span class=&p&&(&/span&&span class=&n&&b&/span& &span class=&ow&&-&&/span& &span class=&n&&b&/span& &span class=&ow&&-&&/span& &span class=&n&&b&/span&&span class=&p&&)&/span& &span class=&ow&&-&&/span& &span class=&kt&&Parser&/span& &span class=&p&&(&/span&&span class=&n&&b&/span& &span class=&ow&&-&&/span& &span class=&n&&b&/span& &span class=&ow&&-&&/span& &span class=&n&&b&/span&&span class=&p&&)&/span&
&span class=&nf&&binOp&/span& &span class=&n&&sym&/span& &span class=&n&&func&/span& &span class=&ow&&=&/span& &span class=&kr&&do&/span&
&span class=&n&&stringP&/span& &span class=&n&&sym&/span&
&span class=&n&&return&/span& &span class=&n&&func&/span&
&/code&&/pre&&/div&&p&当然你也可以不使用 do notation ，毕竟这个很简单。&/p&&div class=&highlight&&&pre&&code class=&language-haskell&&&span&&/span&&span class=&c1&&-- | binary operators&/span&
&span class=&nf&&binOp&/span& &span class=&ow&&::&/span& &span class=&kt&&String&/span& &span class=&ow&&-&&/span& &span class=&p&&(&/span&&span class=&n&&b&/span& &span class=&ow&&-&&/span& &span class=&n&&b&/span& &span class=&ow&&-&&/span& &span class=&n&&b&/span&&span class=&p&&)&/span& &span class=&ow&&-&&/span& &span class=&kt&&Parser&/span& &span class=&p&&(&/span&&span class=&n&&b&/span& &span class=&ow&&-&&/span& &span class=&n&&b&/span& &span class=&ow&&-&&/span& &span class=&n&&b&/span&&span class=&p&&)&/span&
&span class=&nf&&binOp&/span& &span class=&n&&s&/span& &span class=&ow&&=&/span& &span class=&p&&(&/span&&span class=&n&&stringP&/span& &span class=&n&&s&/span& &span class=&o&&&&&/span&&span class=&p&&)&/span& &span class=&o&&.&/span& &span class=&n&&return&/span&
&/code&&/pre&&/div&&p&上面是 point-free 的版本。&/p&&p&这个函数的意思是：&/p&&ol&&li&拿到运算符和 &b&通过结合运算符左右的两个语法树节点生成新的语法树节点的函数&/b&（此处是 \l r -& Op l &+& r）&/li&&li&解析运算符&/li&&li&如果解析成功，那么返回这个函数&/li&&/ol&&h2&重写&/h2&&p&于是我们的加法符号解析器，以及剩下的四则运算就可以很简单地重写：&/p&&div class=&highlight&&&pre&&code class=&language-haskell&&&span&&/span&&span class=&nf&&addOp&/span& &span class=&ow&&=&/span& &span class=&n&&binOp&/span& &span class=&s&&&+&&/span& &span class=&o&&$&/span& &span class=&nf&&\&/span&&span class=&n&&x&/span& &span class=&n&&y&/span& &span class=&ow&&-&&/span& &span class=&kt&&Op&/span& &span class=&n&&x&/span& &span class=&s&&&+&&/span& &span class=&n&&y&/span&
&span class=&nf&&subOp&/span& &span class=&ow&&=&/span& &span class=&n&&binOp&/span& &span class=&s&&&-&&/span& &span class=&o&&$&/span& &span class=&nf&&\&/span&&span class=&n&&x&/span& &span class=&n&&y&/span& &span class=&ow&&-&&/span& &span class=&kt&&Op&/span& &span class=&n&&x&/span& &span class=&s&&&-&&/span& &span class=&n&&y&/span&
&span class=&nf&&mulOp&/span& &span class=&ow&&=&/span& &span class=&n&&binOp&/span& &span class=&s&&&*&&/span& &span class=&o&&$&/span& &span class=&nf&&\&/span&&span class=&n&&x&/span& &span class=&n&&y&/span& &span class=&ow&&-&&/span& &span class=&kt&&Op&/span& &span class=&n&&x&/span& &span class=&s&&&*&&/span& &span class=&n&&y&/span&
&span class=&nf&&divOp&/span& &span class=&ow&&=&/span& &span class=&n&&binOp&/span& &span class=&s&&&/&&/span& &span class=&o&&$&/span& &span class=&nf&&\&/span&&span class=&n&&x&/span& &span class=&n&&y&/span& &span class=&ow&&-&&/span& &span class=&kt&&Op&/span& &span class=&n&&x&/span& &span class=&s&&&/&&/span& &span class=&n&&y&/span&
&/code&&/pre&&/div&&p&要解析一个 1 op 1 （左边 op 是任意一个二元运算符）也就可以这样：&/p&&div class=&highlight&&&pre&&code class=&language-haskell&&&span&&/span&&span class=&nf&&operatorP&/span& &span class=&ow&&::&/span& &span class=&kt&&Parser&/span& &span class=&p&&(&/span&&span class=&n&&a&/span& &span class=&ow&&-&&/span& &span class=&n&&a&/span& &span class=&ow&&-&&/span& &span class=&n&&a&/span&&span class=&p&&)&/span& &span class=&ow&&-&&/span& &span class=&kt&&Parser&/span& &span class=&n&&a&/span&
&span class=&nf&&operatorP&/span& &span class=&n&&op&/span& &span class=&ow&&=&/span& &span class=&kr&&do&/span& &span class=&n&&l&/span& &span class=&ow&&&-&/span& &span class=&n&&numberP&/span& &span class=&n&&o&/span& &span class=&ow&&&-&/span& &span class=&n&&op&/span& &span class=&n&&r&/span& &span class=&ow&&&-&/span& &span class=&n&&numberP&/span& &span class=&n&&return&/span& &span class=&o&&$&/span& &span class=&n&&o&/span& &span class=&n&&l&/span& &span class=&n&&r&/span&
&/code&&/pre&&/div&&p&只需要传入 op 就能构造一个二元运算符。&/p&&h2&左结合&/h2&&p&同理。我们可以进行“不断地尝试往右边解析运算符，直到解析不了，返回表达式链”。&/p&&div class=&highlight&&&pre&&code class=&language-haskell&&&span&&/span&&span class=&nf&&chainl1&/span& &span class=&ow&&::&/span& &span class=&kt&&Parser&/span& &span class=&n&&a&/span& &span class=&ow&&-&&/span& &span class=&kt&&Parser&/span& &span class=&p&&(&/span&&span class=&n&&a&/span& &span class=&ow&&-&&/span& &span class=&n&&a&/span& &span class=&ow&&-&&/span& &span class=&n&&a&/span&&span class=&p&&)&/span& &span class=&ow&&-&&/span& &span class=&kt&&Parser&/span& &span class=&n&&a&/span&
&span class=&nf&&chainl1&/span& &span class=&n&&p&/span& &span class=&n&&op&/span& &span class=&ow&&=&/span& &span class=&kr&&do&/span&
&span class=&n&&a&/span& &span class=&ow&&&-&/span& &span class=&n&&p&/span&
&span class=&n&&rest&/span& &span class=&n&&a&/span&
&span class=&kr&&where&/span&
&span class=&n&&rest&/span& &span class=&n&&a&/span& &span class=&ow&&=&/span& &span class=&p&&(&/span&&span class=&kr&&do&/span&
&span class=&n&&f&/span& &span class=&ow&&&-&/span& &span class=&n&&op&/span&
&span class=&n&&b&/span& &span class=&ow&&&-&/span& &span class=&n&&p&/span&
&span class=&n&&rest&/span& &span class=&o&&$&/span& &span class=&n&&f&/span& &span class=&n&&a&/span& &span class=&n&&b&/span&&span class=&p&&)&/span&
&span class=&o&&&|&&/span& &span class=&n&&return&/span& &span class=&n&&a&/span&
&span class=&c1&&--&/span&
&/code&&/pre&&/div&&p&上面这个实现基本上是你能想到的最简单最朴素好像也是唯一的实现。&/p&&p&比如链状的 + 操作：&/p&&div class=&highlight&&&pre&&code class=&language-text&&&span&&/span&adds = chainl1 numberP addOp
&/code&&/pre&&/div&&p&它可以这样工作：&/p&&div class=&highlight&&&pre&&code class=&language-haskell&&&span&&/span&&span class=&kt&&Main&/span&&span class=&o&&&&/span& &span class=&n&&parseCode&/span& &span class=&n&&adds&/span& &span class=&s&&&1+1+1+1&&/span&
&span class=&kt&&Op&/span& &span class=&p&&(&/span&&span class=&kt&&Op&/span& &span class=&p&&(&/span&&span class=&kt&&Op&/span& &span class=&p&&(&/span&&span class=&kt&&Term&/span& &span class=&s&&&1&&/span&&span class=&p&&)&/span& &span class=&s&&&+&&/span& &span class=&p&&(&/span&&span class=&kt&&Term&/span& &span class=&s&&&1&&/span&&span class=&p&&))&/span& &span class=&s&&&+&&/span& &span class=&p&&(&/span&&span class=&kt&&Term&/span& &span class=&s&&&1&&/span&&span class=&p&&))&/span& &span class=&s&&&+&&/span& &span class=&p&&(&/span&&span class=&kt&&Term&/span& &span class=&s&&&1&&/span&&span class=&p&&)&/span&
&span class=&kt&&Main&/span&&span class=&o&&&&/span& &span class=&n&&parseCode&/span& &span class=&n&&adds&/span& &span class=&s&&&1+1+1&&/span&
&span class=&kt&&Op&/span& &span class=&p&&(&/span&&span class=&kt&&Op&/span& &span class=&p&&(&/span&&span class=&kt&&Term&/span& &span class=&s&&&1&&/span&&span class=&p&&)&/span& &span class=&s&&&+&&/span& &span class=&p&&(&/span&&span class=&kt&&Term&/span& &span class=&s&&&1&&/span&&span class=&p&&))&/span& &span class=&s&&&+&&/span& &span class=&p&&(&/span&&span class=&kt&&Term&/span& &span class=&s&&&1&&/span&&span class=&p&&)&/span&
&span class=&kt&&Main&/span&&span class=&o&&&&/span& &span class=&n&&parseCode&/span& &span class=&n&&adds&/span& &span class=&s&&&1+1&&/span&
&span class=&kt&&Op&/span& &span class=&p&&(&/span&&span class=&kt&&Term&/span& &span class=&s&&&1&&/span&&span class=&p&&)&/span& &span class=&s&&&+&&/span& &span class=&p&&(&/span&&span class=&kt&&Term&/span& &span class=&s&&&1&&/span&&span class=&p&&)&/span&
&/code&&/pre&&/div&&p&我们也可以同时加入减法：&/p&&div class=&highlight&&&pre&&code class=&language-text&&&span&&/span&addAndSubs = chainl1 numberP $ addOp &|& subOp
&/code&&/pre&&/div&&p&这个读者可以自行尝试。&/p&&h2&右结合&/h2&&p&这里也有一个最简最智障实现：&/p&&div class=&highlight&&&pre&&code class=&language-haskell&&&span&&/span&&span class=&nf&&chainr1&/span& &span class=&ow&&::&/span& &span class=&kt&&Parser&/span& &span class=&n&&a&/span& &span class=&ow&&-&&/span& &span class=&kt&&Parser&/span& &span class=&p&&(&/span&&span class=&n&&a&/span& &span class=&ow&&-&&/span& &span class=&n&&a&/span& &span class=&ow&&-&&/span& &span class=&n&&a&/span&&span class=&p&&)&/span& &span class=&ow&&-&&/span& &span class=&kt&&Parser&/span& &span class=&n&&a&/span&
&span class=&nf&&chainr1&/span& &span class=&n&&p&/span& &span class=&n&&op&/span& &span class=&ow&&=&/span& &span class=&n&&scan&/span&
&span class=&kr&&where&/span&
&span class=&n&&scan&/span& &span class=&ow&&=&/span& &span class=&kr&&do&/span&
&span class=&n&&a&/span& &span class=&ow&&&-&/span& &span class=&n&&p&/span&
&span class=&n&&rest&/span& &span class=&n&&a&/span&
&span class=&n&&rest&/span& &span class=&n&&a&/span& &span class=&ow&&=&/span& &span class=&p&&(&/span&&span class=&kr&&do&/span&
&span class=&n&&f&/span& &span class=&ow&&&-&/span& &span class=&n&&op&/span&
&span class=&n&&b&/span& &span class=&ow&&&-&/span& &span class=&n&&scan&/span&
&span class=&n&&rest&/span& &span class=&o&&$&/span& &span class=&n&&f&/span& &span class=&n&&a&/span& &span class=&n&&b&/span&&span class=&p&&)&/span&
&span class=&o&&&|&&/span& &span class=&n&&return&/span& &span class=&n&&a&/span&
&span class=&c1&&--&/span&
&/code&&/pre&&/div&&p&举例比如乘方：&/p&&div class=&highlight&&&pre&&code class=&language-text&&&span&&/span&sq = chainr1 numberP $ binOp &^& $ \x y -& Op x &^& y
&/code&&/pre&&/div&&h2&优先级&/h2&&p&对应地，要加入优先级，也很简单，只要把优先级高的运算（比如乘法）的结果作为优先级低的运算（比如加法）的元素就好了：&/p&&div class=&highlight&&&pre&&code class=&language-haskell&&&span&&/span&&span class=&nf&&addP&/span& &span class=&ow&&=&/span& &span class=&n&&chainl1&/span& &span class=&n&&mulP&/span& &span class=&o&&$&/span& &span class=&n&&binOp&/span& &span class=&s&&&+&&/span& &span class=&o&&$&/span& &span class=&nf&&\&/span&&span class=&n&&x&/span& &span class=&n&&y&/span& &span class=&ow&&-&&/span& &span class=&kt&&Op&/span& &span class=&n&&x&/span& &span class=&s&&&+&&/span& &span class=&n&&y&/span&
&span class=&nf&&mulP&/span& &span class=&ow&&=&/span& &span class=&n&&chainl1&/span& &span class=&n&&oneP&/span& &span class=&o&&$&/span& &span class=&n&&binOp&/span& &span class=&s&&&*&&/span& &span class=&o&&$&/span& &span class=&nf&&\&/span&&span class=&n&&x&/span& &span class=&n&&y&/span& &span class=&ow&&-&&/span& &span class=&kt&&Op&/span& &span class=&n&&x&/span& &span class=&s&&&*&&/span& &span class=&n&&y&/span&
&span class=&nf&&oneP&/span& &span class=&ow&&=&/span& &span class=&n&&numberP&/span&
&/code&&/pre&&/div&&p&上面的 Parser 可以正确解析 1+1*1 和 1*1+1 这两个执行顺序不同的表达式。&/p&&h2&括号&/h2&&p&这个也很简单，我就不说了，可以当作作业。&/p&&p&提示一下，它的作用是把优先级低的运算提高，因此它里面是需要解析一个优先级低的运算，然后这个东西本身可以变成一个最基层的运算单元。其实大家看看括号表达式在 bnf 里面的表示就一目了然了。&/p&&h2&杂话&/h2&&h2&关于构建&/h2&&p&根据上一篇文章在水乎的反馈，在 2017 年， Haskell 工程应该使用 Stack 而不是 Cabal 构建，而且也应该使用 Megaparsec 这个 Parser Combinator 库。不过我都不会用就是了。&/p&&h2&关于 Applicative&/h2&&p&而且上面的很多事情都可以用 Applicative + Alternative 做，不需要 Monad 。比如我们有使用 Monad 的 Parser ：&/p&&div class=&highlight&&&pre&&code class=&language-haskell&&&span&&/span&&span class=&nf&&parseUsingMonad&/span& &span class=&ow&&=&/span& &span class=&kr&&do&/span&
&span class=&n&&x&/span& &span class=&ow&&&-&/span& &span class=&n&&itemP&/span&
&span class=&n&&o&/span& &span class=&ow&&&-&/span& &span class=&n&&operatorP&/span&
&span class=&n&&y&/span& &span class=&ow&&&-&/span& &span class=&n&&itemP&/span&
&span class=&n&&return&/span& &span class=&o&&$&/span& &span class=&kt&&Op&/span& &span class=&n&&x&/span& &span class=&n&&o&/span& &span class=&n&&y&/span&
&/code&&/pre&&/div&&p&其实它等价于这个使用 Applicative 的 Parser ：&/p&&div class=&highlight&&&pre&&code class=&language-haskell&&&span&&/span&&span class=&nf&&parseUsingApplicative&/span& &span class=&ow&&=&/span& &span class=&kt&&Op&/span& &span class=&o&&&$&&/span& &span class=&n&&itemP&/span& &span class=&o&&&*&&/span& &span class=&n&&operatorP&/span& &span class=&o&&&*&&/span& &span class=&n&&itemP&/span&
&/code&&/pre&&/div&&p&上面的代码远远简洁于 Monad 的版本。为了让 GHC 在处理 do notation 的时候尽可能转化为 Applicative 操作而不是 Monad 操作，可以使用&/p&&div class=&highlight&&&pre&&code class=&language-text&&&span&&/span&{-# LANGUAGE ApplicativeDo #-}
&/code&&/pre&&/div&&p&这个扩展。&/p&&h2&CodeWars Challenges&/h2&&p&这里列出一些我认为很有趣的 CodeWars 的 Parser 题。我建立了&a href=&/?target=https%3A///collections/parser-combinators& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&一个 collection 来收藏相关题目&i class=&icon-external&&&/i&&/a&， 感兴趣的同学可以去做一下。&/p&&p&下面分别介绍一下各个题目。&/p&&h2&&a href=&/?target=https%3A///kata/operator-parser& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Operator Parser&i class=&icon-external&&&/i&&/a&&/h2&&p&此题非常新颖，给你一个结合性的 List ，里面放的是以优先级排序的二元中缀符号的 Parser ， 然后你需要把它们组合起来成为一个大的表达式 Parser 。这题一看就知道是 foldr/foldl ，哈哈。&/p&&p&前文所使用的 OpTree 就是这道题里面的。&/p&&h2&&a href=&/?target=https%3A///kata/writing-applicative-parsers-from-scratch& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Writing Applicative Parsers From Scratch&i class=&icon-external&&&/i&&/a&&/h2&&p&此题禁止你使用 Control.Applicative, Prelude 的 fmap 和 Data.Functor（我觉得它很 SB 的一点在于它没有禁止你使用 &$&）， 然后让你从 0 开始写一个 Applicative 的 Parser 。&/p&&h2&&a href=&/?target=https%3A///kata/regular-expression-parser& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Regular Expression Parser&i class=&icon-external&&&/i&&/a&&/h2&&p&这个题目是让你解析正则表达式的，需要特别注意一些结合性的问题（这道题我的解法比较 dirty ，特判了两组数据）。做这题的时候我不知道有 chainr1 ，结果写出来的代码很伤。&/p&&h2&&a href=&/?target=https%3A///kata/tiny-three-pass-compiler& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Tiny Three Pass Compiler&i class=&icon-external&&&/i&&/a&&/h2&&p&老经典的题，支持很多语言，写起来贼爽。&/p&
原文在我博客：上一篇也是：本篇主要讲 Parser Combinator 的组合，比如二元运算符的解析以及优先级结合性的处理。some 与 many上篇还剩下一个内容，就是 some 和 many 。这两…
&img src=&/50/v2-f5b1fadb980eecc874f945addac3dc93_b.jpg& data-rawwidth=&2560& data-rawheight=&1600& class=&origin_image zh-lightbox-thumb& width=&2560& data-original=&/50/v2-f5b1fadb980eecc874f945addac3dc93_r.jpg&&&p&为什么我会想到去用 Haskell 写 Parser 呢？因为 Haskell 的 do notation 对这种 Monad 组合子真的太友好了。&/p&&p&另一个原因是因为最近在 &a href=&/?target=https%3A///r/8-drmA& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&CodeWars&i class=&icon-external&&&/i&&/a& 上做了不少 Parser 题，刷分巨快(因为 Parser 题都是紫色的)，很快把我推上了 1kyu 。&/p&&p&全文代码如有误欢迎指出，我会诚恳地改正。本文讲的内容不多，主要是介绍，下篇文章会说怎么解析带优先级/结合性的表达式。&/p&&p&首先我说说 Parser Combinator （就是函数式编程中采用的编写 Parser 的方式） 的基本使用。 篇幅所限， Parsre Combinator 库的编写就不说了。它其实是将针对某种语法模块的 Parser 单元组合起来成为可以解析复杂语法的 Parser 。 比如我有一个可以解析数字的 Parser 和一个可以解析符号 + 的 Parser ，那么组合他们就可以得到加法运算的 Parser 。大概是这样：&/p&&div class=&highlight&&&pre&&code class=&language-haskell&&&span&&/span&&span class=&nf&&plusParser&/span& &span class=&ow&&::&/span& &span class=&kt&&Parser&/span& &span class=&kt&&Char&/span&
&span class=&nf&&plusParser&/span& &span class=&ow&&=&/span& &span class=&n&&xxxx&/span&
&span class=&nf&&numberParser&/span& &span class=&ow&&::&/span& &span class=&kt&&Parser&/span& &span class=&kt&&Int&/span&
&span class=&nf&&numberParser&/span& &span class=&ow&&=&/span& &span class=&n&&xxxx&/span&
&span class=&kr&&data&/span& &span class=&kt&&Op&/span& &span class=&n&&a&/span& &span class=&n&&b&/span& &span class=&ow&&=&/span& &span class=&kt&&Op&/span& &span class=&n&&a&/span& &span class=&n&&b&/span& &span class=&n&&a&/span&
&span class=&nf&&plusOperationParser&/span& &span class=&ow&&::&/span& &span class=&kt&&Parser&/span& &span class=&p&&(&/span&&span class=&kt&&Op&/span& &span class=&n&&a&/span& &span class=&n&&b&/span&&span class=&p&&)&/span&
&span class=&nf&&plusOperationParser&/span& &span class=&ow&&=&/span& &span class=&kr&&do&/span&
&span class=&n&&a&/span& &span class=&ow&&&-&/span& &span class=&n&&numberParser&/span&
&span class=&n&&plusParser&/span&
&span class=&n&&b&/span& &span class=&ow&&&-&/span& &span class=&n&&numberParser&/span&
&span class=&n&&return&/span& &span class=&o&&$&/span& &span class=&kt&&Op&/span& &span class=&n&&a&/span& &span class=&sc&&'+'&/span& &span class=&n&&b&/span&
&/code&&/pre&&/div&&p&是不是一目了然呢？&/p&&h2&语法介绍&/h2&&p&首先我有类型及对应构造器 Op 表示一个二元运算，然后有解析数字的 numberParser 和解析加号的 plusParser ， 他们通过最下面那个超级简单的 do notation （就是按从上到下的顺序运行这些 Parser ，解析成功则返回解析好的那个东西 （比如 Parser a 解析后就返回 a ，那么同理上面的 plusParser 解析完后返回一个 Char 。而 numberParser 返回的是解析好的 Int ， 我们通过那个箭头的语法来捕获它返回的值。后者我们需要保留解析后留下的数字，但前者我们都知道它返回的一定是 '+' ， 因此再获取这个返回的值意义不大，因此它就没有箭头，最后用一个 return 把返回值拼起来）组合到一起 （事实上 do notation 只是 Monad 的系列套餐的一个语法糖，但这是一个非常厉害的语法糖。 篇幅所限，本文不讨论，也不需要读者懂 do notation 展开后到底啥样）。&/p&&h2&总结&/h2&&p&一个 Parser a 解析字符串，返回 a 类型的东西。&/p&&p&Parser a 之间可以互相组合，成为一个大 Parser b 。&/p&&h2&构建最简单的 Parser&/h2&&p&首先我们有一个函数 satisfy ，通过一个 Char -& Bool 构造出一个 Parser Char ，也就是给定一个函数，把字符传入， 返回 True 则代表成功解析。举个例子，这个函数接收一个 Char ，返回专门解析这个 Char 的 Parser ：&/p&&div class=&highlight&&&pre&&code class=&language-text&&&span&&/span&char :: Parser Char
char = satisfy . (==)
&/code&&/pre&&/div&&p&如果不 point-free 并进行 eta 展开的话就是这样（如果看不懂上面的版本就看这个吧）：&/p&&div class=&highlight&&&pre&&code class=&language-text&&&span&&/span&char c = satisfy (\x -& x == c)
&/code&&/pre&&/div&&p&而如果我们要编写一个解析字符串 &&= 的 Parser ，则：&/p&&div class=&highlight&&&pre&&code class=&language-haskell&&&span&&/span&&span class=&nf&&bind&/span& &span class=&ow&&::&/span& &span class=&kt&&Parser&/span& &span class=&kt&&String&/span&
&span class=&nf&&bind&/span& &span class=&ow&&=&/span& &span class=&kr&&do&/span&
&span class=&n&&char&/span& &span class=&sc&&'&'&/span&
&span class=&n&&char&/span& &span class=&sc&&'&'&/span&
&span class=&n&&char&/span& &span class=&sc&&'='&/span&
&span class=&n&&return&/span& &span class=&s&&&&&=&&/span&
&/code&&/pre&&/div&&p&再抽象一下，解析某个长度为 3 的字符串（作为参数）的 Parser ：&/p&&div class=&highlight&&&pre&&code class=&language-haskell&&&span&&/span&&span class=&nf&&three&/span& &span class=&ow&&::&/span& &span class=&kt&&String&/span& &span class=&ow&&-&&/span& &span class=&kt&&Parser&/span& &span class=&kt&&String&/span&
&span class=&nf&&three&/span& &span class=&n&&s&/span&&span class=&o&&@&/span&&span class=&p&&[&/span&&span class=&n&&a&/span&&span class=&p&&,&/span& &span class=&n&&b&/span&&span class=&p&&,&/span& &span class=&n&&c&/span&&span class=&p&&]&/span& &span class=&ow&&=&/span& &span class=&kr&&do&/span&
&span class=&n&&char&/span& &span class=&n&&a&/span&
&span class=&n&&char&/span& &span class=&n&&b&/span&
&span class=&n&&char&/span& &span class=&n&&c&/span&
&span class=&n&&return&/span& &span class=&n&&s&/span&
&/code&&/pre&&/div&&p&再抽象一下，解析任意长度为 3 的字符串：&/p&&div class=&highlight&&&pre&&code class=&language-haskell&&&span&&/span&&span class=&nf&&oneC&/span& &span class=&ow&&::&/span& &span class=&kt&&Parser&/span& &span class=&kt&&Char&/span&
&span class=&nf&&oneC&/span& &span class=&ow&&=&/span& &span class=&kr&&do&/span&
&span class=&n&&c&/span& &span class=&ow&&&-&/span& &span class=&n&&satisfy&/span& &span class=&o&&$&/span& &span class=&n&&const&/span& &span class=&kt&&True&/span&
&span class=&n&&return&/span& &span class=&n&&c&/span&
&span class=&c1&&--&/span&
&span class=&nf&&three'&/span& &span class=&ow&&::&/span& &span class=&kt&&Parser&/span& &span class=&kt&&String&/span&
&span class=&nf&&three'&/span& &span class=&ow&&=&/span& &span class=&kr&&do&/span&
&span class=&n&&a&/span& &span class=&ow&&&-&/span& &span class=&n&&oneC&/span&
&span class=&n&&b&/span& &span class=&ow&&&-&/span& &span class=&n&&oneC&/span&
&span class=&n&&c&/span& &span class=&ow&&&-&/span& &span class=&n&&oneC&/span&
&span class=&n&&return&/span& &span class=&p&&[&/span&&span class=&n&&a&/span&&span class=&p&&,&/span& &span class=&n&&b&/span&&span class=&p&&,&/span& &span class=&n&&c&/span&&span class=&p&&]&/span&
&/code&&/pre&&/div&&p&到这里你是不是已经大概清楚怎么使用 Parser Combinator 了？想不想动手试试？&/p&&h2&（有毒）具体在 GHCi 中使用&/h2&&p&首先，大家可以选择使用我在文章末尾提供的微型实现;&/p&&p&或者安装：&/p&&ul&&li&版本算正常的 GHC&/li&&li&版本算正常的 Cabal&/li&&/ul&&p&然后执行：&/p&&div class=&highlight&&&pre&&code class=&language-text&&&span&&/span&$ cabal install parsec
Prelude& :m +Text.ParserCombinators.ReadP
&/code&&/pre&&/div&&p&然后剩下的我也不会，我只知道我的 Parser 实现在这个库中的等价物是（应该是） ReadP a。 所以你们还是直接用我在附录里面放的网上找的那份独立的吧（雾（其实我还魔改过一点点啦，编码习惯啥的，不是大事））。&/p&&h2&用法：&/h2&&p&首先写好你的 Parser （假设就是 myP ，直接和我给的代码写一起），然后打开 GHCi 加载你的文件，然后运行：&/p&&div class=&highlight&&&pre&&code class=&language-text&&&span&&/span&parseCode myP &the code you want to parse&
&/code&&/pre&&/div&&p&就可以看到返回的结果了。具体的例子：&/p&&div class=&highlight&&&pre&&code class=&language-haskell&&&span&&/span&&span class=&kt&&Main&/span&&span class=&o&&&&/span& &span class=&n&&parseCode&/span& &span class=&p&&(&/span&&span class=&n&&satisfy&/span& &span class=&p&&(`&/span&&span class=&n&&elem&/span&&span class=&p&&`&/span& &span class=&s&&&jfly&&/span&&span class=&p&&))&/span& &span class=&s&&&j&&/span&
&span class=&sc&&'j'&/span&
&span class=&kt&&Main&/span&&span class=&o&&&&/span& &span class=&n&&parseCode&/span& &span class=&p&&(&/span&&span class=&n&&satisfy&/span& &span class=&p&&(`&/span&&span class=&n&&elem&/span&&span class=&p&&`&/span& &span class=&s&&&jfly&&/span&&span class=&p&&))&/span& &span class=&s&&&f&&/span&
&span class=&sc&&'f'&/span&
&span class=&kt&&Main&/span&&span class=&o&&&&/span& &span class=&n&&parseCode&/span& &span class=&p&&(&/span&&span class=&n&&satisfy&/span& &span class=&p&&(`&/span&&span class=&n&&elem&/span&&span class=&p&&`&/span& &span class=&s&&&jfly&&/span&&span class=&p&&))&/span& &span class=&s&&&g&&/span&
&span class=&o&&***&/span& &span class=&kt&&Exception:&/span& &span class=&kt&&Hugh&/span&&span class=&o&&?&/span&
&/code&&/pre&&/div&&p&读者感兴趣的话可以试试实现一个 Parser ，解析一个带括号的字符串，返回括号内部的东西。&/p&&h2&你学到了什么&/h2&&ul&&li&简易的 Parser Combinator 的使用&/li&&/ul&&h2&预告&/h2&&ul&&li&稍微复杂点的表达式的解析&/li&&/ul&&h2&（附） Parser Combinator 简易实现&/h2&&p&成功解析返回解析结果，失败则 error &Hugh?& （模仿 dram）。&/p&&div class=&highlight&&&pre&&code class=&language-haskell&&&span&&/span&&span class=&kr&&import&/span& &span class=&nn&&Data.Char&/span&
&span class=&kr&&import&/span& &span class=&nn&&Data.List&/span&
&span class=&kr&&import&/span& &span class=&nn&&Control.Monad&/span&
&span class=&kr&&import&/span& &span class=&nn&&Control.Applicative&/span&
&span class=&c1&&-----------------------------------------------------&/span&
&span class=&c1&&--------------- my parser combinator ----------------&/span&
&span class=&c1&&-----------------------------------------------------&/span&
&span class=&kr&&newtype&/span& &span class=&kt&&Parser&/span& &span class=&n&&val&/span& &span class=&ow&&=&/span& &span class=&kt&&Parser&/span& &span class=&p&&{&/span& &span class=&n&&parse&/span& &span class=&ow&&::&/span& &span class=&kt&&String&/span& &span class=&ow&&-&&/span& &span class=&p&&[(&/span&&span class=&n&&val&/span&&span class=&p&&,&/span& &span class=&kt&&String&/span&&span class=&p&&)]&/span&
&span class=&p&&}&/span&
&span class=&nf&&parseCode&/span& &span class=&ow&&::&/span& &span class=&kt&&Parser&/span& &span class=&n&&a&/span& &span class=&ow&&-&&/span& &span class=&kt&&String&/span& &span class=&ow&&-&&/span& &span class=&n&&a&/span&
&span class=&nf&&parseCode&/span& &span class=&n&&m&/span& &span class=&n&&s&/span& &span class=&ow&&=&/span& &span class=&kr&&case&/span& &span class=&n&&parse&/span& &span class=&n&&m&/span& &span class=&n&&s&/span& &span class=&kr&&of&/span&
&span class=&p&&[(&/span&&span class=&n&&res&/span&&span class=&p&&,&/span& &span class=&kt&&[]&/span&&span class=&p&&)]&/span& &span class=&ow&&-&&/span& &span class=&n&&res&/span&
&span class=&kr&&_&/span&
&span class=&ow&&-&&/span& &span class=&ne&&error&/span& &span class=&s&&&Hugh?&&/span&
&span class=&c1&&--&/span&
&span class=&kr&&instance&/span& &span class=&kt&&Functor&/span& &span class=&kt&&Parser&/span& &span class=&kr&&where&/span&
&span class=&n&&fmap&/span& &span class=&n&&f&/span& &span class=&p&&(&/span&&span class=&kt&&Parser&/span& &span class=&n&&ps&/span&&span class=&p&&)&/span& &span class=&ow&&=&/span& &span class=&kt&&Parser&/span& &span class=&o&&$&/span& &span class=&nf&&\&/span&&span class=&n&&p&/span& &span class=&ow&&-&&/span& &span class=&p&&[&/span& &span class=&p&&(&/span&&span class=&n&&f&/span& &span class=&n&&a&/span&&span class=&p&&,&/span& &span class=&n&&b&/span&&span class=&p&&)&/span& &span class=&o&&|&/span& &span class=&p&&(&/span&&span class=&n&&a&/span&&span class=&p&&,&/span& &span class=&n&&b&/span&&span class=&p&&)&/span& &span class=&ow&&&-&/span& &span class=&n&&ps&/span& &span class=&n&&p&/span& &span class=&p&&]&/span&
&span class=&c1&&--&/span&
&span class=&kr&&instance&/span& &span class=&kt&&Applicative&/span& &span class=&kt&&Parser&/span& &span class=&kr&&where&/span&
&span class=&n&&pure&/span& &span class=&ow&&=&/span& &span class=&n&&return&/span&
&span class=&p&&(&/span&&span class=&kt&&Parser&/span& &span class=&n&&p1&/span&&span class=&p&&)&/span& &span class=&o&&&*&&/span& &span class=&p&&(&/span&&span class=&kt&&Parser&/span& &span class=&n&&p2&/span&&span class=&p&&)&/span& &span class=&ow&&=&/span& &span class=&kt&&Parser&/span& &span class=&o&&$&/span& &span class=&nf&&\&/span&&span class=&n&&p&/span& &span class=&ow&&-&&/span&
&span class=&p&&[&/span& &span class=&p&&(&/span&&span class=&n&&f&/span& &span class=&n&&a&/span&&span class=&p&&,&/span& &span class=&n&&s2&/span&&span class=&p&&)&/span& &span class=&o&&|&/span& &span class=&p&&(&/span&&span class=&n&&f&/span&&span class=&p&&,&/span& &span class=&n&&s1&/span&&span class=&p&&)&/span& &span class=&ow&&&-&/span& &span class=&n&&p1&/span& &span class=&n&&p&/span&&span class=&p&&,&/span& &span class=&p&&(&/span&&span class=&n&&a&/span&&span class=&p&&,&/span& &span class=&n&&s2&/span&&span class=&p&&)&/span& &span class=&ow&&&-&/span& &span class=&n&&p2&/span& &span class=&n&&s1&/span& &span class=&p&&]&/span&
&span class=&c1&&--&/span&
&span class=&kr&&instance&/span& &span class=&kt&&Monad&/span& &span class=&kt&&Parser&/span& &span class=&kr&&where&/span&
&span class=&n&&return&/span& &span class=&n&&a&/span& &span class=&ow&&=&/span& &span class=&kt&&Parser&/span& &span class=&o&&$&/span& &span class=&nf&&\&/span&&span class=&n&&s&/span& &span class=&ow&&-&&/span& &span class=&p&&[(&/span&&span class=&n&&a&/span&&span class=&p&&,&/span& &span class=&n&&s&/span&&span class=&p&&)]&/span&
&span class=&n&&p&/span& &span class=&o&&&&=&/span& &span class=&n&&f&/span&
&span class=&ow&&=&/span& &span class=&kt&&Parser&/span& &span class=&o&&$&/span& &span class=&n&&concatMap&/span& &span class=&p&&(&/span&&span class=&nf&&\&/span&&span class=&p&&(&/span&&span class=&n&&a&/span&&span class=&p&&,&/span& &span class=&n&&s1&/span&&span class=&p&&)&/span& &span class=&ow&&-&&/span& &span class=&n&&f&/span& &span class=&n&&a&/span& &span class=&p&&`&/span&&span class=&n&&parse&/span&&span class=&p&&`&/span& &span class=&n&&s1&/span&&span class=&p&&)&/span& &span class=&o&&.&/span& &span class=&n&&parse&/span& &span class=&n&&p&/span&
&span class=&c1&&--&/span&
&span class=&kr&&instance&/span& &span class=&kt&&MonadPlus&/span& &span class=&kt&&Parser&/span& &span class=&kr&&where&/span&
&span class=&n&&mzero&/span&
&span class=&ow&&=&/span& &span class=&kt&&Parser&/span& &span class=&o&&$&/span& &span class=&n&&const&/span& &span class=&kt&&[]&/span&
&span class=&n&&mplus&/span& &span class=&n&&p&/span& &span class=&n&&q&/span& &span class=&ow&&=&/span& &span class=&kt&&Parser&/span& &span class=&o&&$&/span& &span class=&nf&&\&/span&&span class=&n&&s&/span& &span class=&ow&&-&&/span& &span class=&n&&parse&/span& &span class=&n&&p&/span& &span class=&n&&s&/span& &span class=&o&&++&/span& &span class=&n&&parse&/span& &span class=&n&&q&/span& &span class=&n&&s&/span&
&span class=&c1&&--&/span&
&span class=&kr&&instance&/span& &span class=&kt&&Alternative&/span& &span class=&kt&&Parser&/span& &span class=&kr&&where&/span&
&span class=&n&&empty&/span&
&span class=&ow&&=&/span& &span class=&n&&mzero&/span&
&span class=&n&&p&/span& &span class=&o&&&|&&/span& &span class=&n&&q&/span& &span class=&ow&&=&/span& &span class=&kt&&Parser&/span& &span class=&o&&$&/span& &span class=&nf&&\&/span&&span class=&n&&s&/span& &span class=&ow&&-&&/span& &span class=&kr&&case&/span& &span class=&n&&parse&/span& &span class=&n&&p&/span& &span class=&n&&s&/span& &span class=&kr&&of&/span&
&span class=&kt&&[]&/span& &span class=&ow&&-&&/span& &span class=&n&&parse&/span& &span class=&n&&q&/span& &span class=&n&&s&/span&
&span class=&n&&rs&/span& &span class=&ow&&-&&/span& &span class=&n&&rs&/span&
&span class=&c1&&--&/span&
&span class=&nf&&item&/span& &span class=&ow&&::&/span& &span class=&kt&&Parser&/span& &span class=&kt&&Char&/span&
&span class=&nf&&item&/span& &span class=&ow&&=&/span& &span class=&kt&&Parser&/span& &span class=&o&&$&/span& &span class=&nf&&\&/span&&span class=&n&&s&/span& &span class=&ow&&-&&/span& &span class=&kr&&case&/span& &span class=&n&&s&/span& &span class=&kr&&of&/span&
&span class=&p&&[&/span&
&span class=&p&&]&/span& &span class=&ow&&-&&/span& &span class=&kt&&[]&/span&
&span class=&p&&(&/span&&span class=&n&&h&/span& &span class=&kt&&:&/span& &span class=&n&&t&/span&&span class=&p&&)&/span& &span class=&ow&&-&&/span& &span class=&p&&[(&/span&&span class=&n&&h&/span&&span class=&p&&,&/span& &span class=&n&&t&/span&&span class=&p&&)]&/span&
&span class=&c1&&--&/span&
&span class=&nf&&satisfy&/span& &span class=&ow&&::&/span& &span class=&p&&(&/span&&span class=&kt&&Char&/span& &span class=&ow&&-&&/span& &span class=&kt&&Bool&/span&&span class=&p&&)&/span& &span class=&ow&&-&&/span& &span class=&kt&&Parser&/span& &span class=&kt&&Char&/span&
&span class=&nf&&satisfy&/span& &span class=&n&&p&/span& &span class=&ow&&=&/span& &span class=&n&&item&/span& &span class=&o&&&&=&/span& &span class=&nf&&\&/span&&span class=&n&&c&/span& &span class=&ow&&-&&/span& &span class=&kr&&if&/span& &span class=&n&&p&/span& &span class=&n&&c&/span& &span class=&kr&&then&/span& &span class=&n&&return&/span& &span class=&n&&c&/span& &span class=&kr&&else&/span& &span class=&n&&empty&/span&
&/code&&/pre&&/div&&p&&/p&
为什么我会想到去用 Haskell 写 Parser 呢？因为 Haskell 的 do notation 对这种 Monad 组合子真的太友好了。另一个原因是因为最近在
上做了不少 Parser 题，刷分巨快(因为 Parser 题都是紫色的)，很快把我推上了 1kyu 。全文代码如有误欢迎指出，…
Michael Snoyman 写过 yesod 做 Haskell web 开发的书，比较系统，可以免费在线看。yesod 在 Haskell web framework 里的定位跟 Django 在 Python 那边的类似，历史久，配套设施多（模板引擎、ORM 之类的都有），可供参考。&br&&br&选择其他的框架然后参考文档也行：&br&web 框架：轻量级的可以看看 scotty，另外用到 type level 编程比较多的框架 servant 也很不错&br&数据库：传统来说 Haskell 对 mysql 支持度远不如 postgres。。不过寒冬写过 pure Haskell 的 mysql driver。。以前都是 persistent 那一套用得比较多，现在的话不妨看看 selda。对于非 SQL 的数据库的话，redis/mongodb/elasticsearch 都有不错的绑定&br&模板：可以看看 yesod 的那几个模板语言。我个人倒是比较喜欢 mustache。。另外记得 jinja2 也有移植版。渲染 HTML 的话一般用 blaze 或者 lucid
Michael Snoyman 写过 yesod 做 Haskell web 开发的书，比较系统，可以免费在线看。yesod 在 Haskell web framework 里的定位跟 Django 在 Python 那边的类似，历史久，配套设施多（模板引擎、ORM 之类的都有），可供参考。 选择其他的框架然后参考文档也行…
如果是用 Haskell 的话，三篇文章足矣。&br&&br&prerequisite: 懂 state monad就行了&br&&br&&u&&b&第一篇&/b&&/u&，《How to build a monadic interpreter in one day》&a href=&///?target=http%3A//citeseerx.ist.psu.edu/viewdoc/summary%3Fdoi%3D10.1.1.368.2522& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://&/span&&span class=&visible&&citeseerx.ist.psu.edu/v&/span&&span class=&invisible&&iewdoc/summary?doi=10.1.1.368.2522&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&br&&br&跟着做，可以完成一个简单的backend， 也就是架构基本的AST 并执行的步骤。&br&&br&然后到frontend， 也就是parser的部分你就会发现你看不懂了， 这个时候看第二篇。（因为该文的 parser
部分其实是 第二篇 的一个浓缩版，所以不看第二篇基本很难看懂这个部分）&br&&br&&br&&br&&u&&b&第二篇&/b&&/u&，《Monadic Parser Combinator》 ，&a href=&///?target=http%3A//www.cs.nott.ac.uk/%7Epszgmh/monparsing.pdf& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://www.&/span&&span class=&visible&&cs.nott.ac.uk/~pszgmh/m&/span&&span class=&invisible&&onparsing.pdf&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&br&&br&看了也就能对照第一篇，把 parser 写出来了， 然后就能和之前的backend 组合，完成一个基本的，完全由自己手写的，monadic的解释器（parser 和 backend 分别由一个自定义的 state monad 实现）。顺便加深对 monad 的理解。&br&&br&看第二篇的时候，回过头对照第一篇看效果会更高，虽然逻辑一样，但第二篇是用 monad comprehension 的形式来写， 第一篇是用 do notation 来写。有的复杂的地方你两种方式对照看一下，会有茅塞顿开的效果。&br&&br&然后再看第三篇&br&&br&&br&&u&&b&第三篇&/b&&/u&，llvm的haskell 教程， &a href=&///?target=http%3A///llvm/%23code-generation-setup& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Implementing a JIT Compiler with Haskell and LLVM ( Stephen Diehl )&i class=&icon-external&&&/i&&/a&
， 把你的backend 换成llvm. （注：事先对 llvm 不熟的话，可以和 hackage 上面 llvm-general, llvm-general-pure 这两个库的 wiki, 以及 &a href=&///?target=http%3A//llvm.org/docs/LangRef.html%23module-structure& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&LLVM Language Reference Manual&i class=&icon-external&&&/i&&/a&对照着看）&br&&br&至于frontend， 可以换成Parsec之类，但也可以就不断扩充之前自己写的版本。&br&&br&齐活儿~&br&&br&------&br&&br&今天闲着没事儿，撸了一个 swift 的版本，&a href=&///?target=https%3A///aaaron7/swift_monadic_parser& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&GitHub - aaaron7/swift_monadic_parser: A simple haskell-style monadic combinator-based parser written in Swift.&i class=&icon-external&&&/i&&/a&
仅包含最基本的 parser 和 interpreter 的功能，写法完全按照前面两篇文章的思路实现，有兴趣可以看看。
如果是用 Haskell 的话，三篇文章足矣。 prerequisite: 懂 state monad就行了 第一篇，《How to build a monadic interpreter in one day》 跟着做，可以完成一个简单的backend， 也就是架构基本的AST 并执行的步骤。 然后到frontend，…
就在今天，我终于想起了自己的知乎密码(雾)&p&过段时间需要做一个关于FP的分享。在准备的时候我不小心加入了这个例子：&/p&&blockquote&用foldr来定义foldl&br&&/blockquote&&p&然而我悲剧地发现我自己竟然做不出来(??_?`)&/p&&p&搜索了一波，轻松找到答案：&/p&&div class=&highlight&&&pre&&code class=&language-haskell&&&span&&/span&&span class=&nf&&foldl&/span& &span class=&ow&&::&/span& &span class=&p&&(&/span&&span class=&n&&a&/span& &span class=&ow&&-&&/span& &span class=&n&&b&/span& &span class=&ow&&-&&/span& &span class=&n&&a&/span&&span class=&p&&)&/span& &span class=&ow&&-&&/span& &span class=&n&&a&/span& &span class=&ow&&-&&/span& &span class=&p&&[&/span&&span class=&n&&b&/span&&span class=&p&&]&/span& &span class=&ow&&-&&/span& &span class=&n&&a&/span&
&span class=&nf&&foldl&/span& &span class=&n&&f&/span& &span class=&n&&a&/span& &span class=&n&&bs&/span& &span class=&ow&&=&/span& &span class=&n&&foldr&/span& &span class=&p&&(&/span&&span class=&nf&&\&/span&&span class=&n&&b&/span& &span class=&n&&g&/span& &span class=&n&&x&/span& &span class=&ow&&-&&/span& &span class=&n&&g&/span& &span class=&p&&(&/span&&span class=&n&&f&/span& &span class=&n&&x&/span& &span class=&n&&b&/span&&span class=&p&&))&/span& &span class=&n&&id&/span& &span class=&n&&bs&/span& &span class=&n&&a&/span&
&/code&&/pre&&/div&&p&为了防止下次仍然无法解决这个问题，今晚特意探索了一下其中最关键的那个&/p&&div class=&highlight&&&pre&&code class=&language-haskell&&&span&&/span&&span class=&nf&&\&/span&&span class=&n&&b&/span& &span class=&n&&g&/span& &span class=&n&&x&/span& &span class=&ow&&-&&/span& &span class=&n&&g&/span& &span class=&p&&(&/span&&span class=&n&&f&/span& &span class=&n&&x&/span& &span class=&n&&b&/span&&span class=&p&&)&/span&
&/code&&/pre&&/div&&p&是怎么弄出来的。毕竟这样的一坨东西，记住是不大可能的，只能靠搞懂它的generator来掌握问题的解法了/(/ / /ω/ / /)/&/p&&h2&瞎试&/h2&&p&首先找个简单的 观察一下，看能不能发现一些规律：&/p&&div class=&highlight&&&pre&&code class=&language-haskell&&&span&&/span&&span class=&nf&&foldl&/span& &span class=&n&&plus&/span& &span class=&mi&&0&/span& &span class=&p&&[&/span&&span class=&mi&&1&/span&&span class=&p&&,&/span& &span class=&mi&&2&/span&&span class=&p&&]&/span& &span class=&ow&&=&/span& &span class=&n&&plus&/span& &span class=&p&&(&/span&&span class=&n&&plus&/span& &span class=&mi&&0&/span& &span class=&mi&&1&/span&&span class=&p&&)&/span& &span class=&mi&&2&/span&
&/code&&/pre&&/div&&p&让我们先试着用各种方法拿foldr来表示一下。&/p&&p&假设存在一个f: Int -& Int使得foldr f 0 [1, 2]可以展开成plus (plus 0 1) 2，那就会这样：&/p&&div class=&highlight&&&pre&&code class=&language-haskell&&&span&&/span&&span class=&nf&&foldr&/span& &span class=&n&&f&/span& &span class=&mi&&0&/span& &span class=&p&&[&/span&&span class=&mi&&1&/span&&span class=&p&&,&/span& &span class=&mi&&2&/span&&span class=&p&&]&/span& &span class=&ow&&=&/span& &span class=&n&&f&/span& &span class=&mi&&1&/span& &span class=&p&&(&/span&&span class=&n&&f&/span& &span class=&mi&&2&/span& &span class=&mi&&0&/span&&span class=&p&&)&/span& &span class=&ow&&=&/span& &span class=&n&&plus&/span& &span class=&p&&(&/span&&span class=&n&&plus&/span& &span class=&mi&&0&/span& &span class=&mi&&1&/span&&span class=&p&&)&/span& &span class=&mi&&2&/span&
&/code&&/pre&&/div&&p&这里需要注意，我们要求的f并不是简单地让f 1 (f 2 0)的值等于plus (plus 0 1) 2就可以，而是需要严格的保证两边的term是一模一样的（就像coq的reflexivity一样）。如果不这样的话，对于整数范围上的加法这样满足交换律和结合律的运算来说倒是无所谓，但对不满足交换律或者不满足结合律的运算来说就不行了。&/p&&p&试着求几个f出来，可以发现几乎不可能找到一个靠谱的f使得它对任意Int List都有效。这其中，最关键的问题在于参数应用的顺序不同。foldl中，我们需要初始值和List中第一个元素先进行运算，然后结果和第二个元素进行运算；但foldr中却是最后一个元素和初始值先运算，然后依次向前。&/p&&p&那么有没有办法改变一下参数应用的顺序呢？我的第一反应就是把输入的List做一个reverse。这当然是一个可行的解：&/p&&div class=&highlight&&&pre&&code class=&language-haskell&&&span&&/span&&span class=&nf&&foldl&/span& &span class=&ow&&::&/span& &span class=&p&&(&/span&&span class=&n&&a&/span& &span class=&ow&&-&&/span& &span class=&n&&b&/span& &span class=&ow&&-&&/span& &span class=&n&&a&/span&&span class=&p&&)&/span& &span class=&ow&&-&&/span& &span class=&n&&a&/span& &span class=&ow&&-&&/span& &span class=&p&&[&/span&&span class=&n&&b&/span&&span class=&p&&]&/span& &span class=&ow&&-&&/span& &span class=&n&&a&/span&
&span class=&nf&&foldl&/span& &span class=&n&&f&/span& &span class=&n&&a&/span& &span class=&n&&bs&/span& &span class=&ow&&=&/span& &span class=&n&&foldr&/span& &span class=&p&&(&/span&&span class=&nf&&\&/span&&span class=&n&&x&/span& &span class=&n&&y&/span& &span class=&ow&&-&&/span& &span class=&n&&f&/span& &span class=&n&&y&/span& &span class=&n&&x&/span&&span class=&p&&)&/span& &span class=&n&&a&/span& &span class=&p&&(&/span&&span class=&n&&reverse&/span& &span class=&n&&bs&/span&&span class=&p&&)&/span&
&/code&&/pre&&/div&&p&这样的问题在于需要额外遍历一遍bs，比较低效。&/p&&p&那我们能不能用闭包来变相实现倒序功能来避免reverse的开销呢？&/p&&h2&闭包&/h2&&p&现在的目标是找出一个foldr中使用的g，让它在fold过程中把喂给它的元素都偷偷记下来，然后在fold结束后倒着把那这些元素进行操作。 如此一来问题就具体成了两个子问题：&/p&&ul&&li&如何把元素记下来？&br&&/li&&li&如何知道fold结束了？&br&&/li&&/ul&&p&把元素记在闭包里是已经钦定的，因此g必须可以操作函数。考虑到foldr的类型标记：&/p&&div class=&highlight&&&pre&&code class=&language-haskell&&&span&&/span&&span class=&nf&&foldr&/span& &span class=&ow&&::&/span& &span class=&p&&(&/span&&span class=&n&&b&/span& &span class=&ow&&-&&/span& &span class=&n&&a&/span& &span class=&ow&&-&&/span& &span class=&n&&a&/span&&span class=&p&&)&/span& &span class=&ow&&-&&/span& &span class=&n&&a&/span& &span class=&ow&&-&&/span& &span class=&p&&[&/span&&span class=&n&&b&/span&&span class=&p&&]&/span& &span class=&ow&&-&&/span& &span class=&n&&a&/span&
&/code&&/pre&&/div&&p&不难判断g的第一个参数类型为b，第二个参数类型为某个函数类型。&/p&&p&在这个前提下，fold结束时得到的是一个函数。此时我们只要给这个函数以参数就可以使它启动，然后对闭包中存储的元素倒着来一遍操作。&/p&&p&再结合foldr的类型以及g的类型，我们发现此时foldr需要的初始值是一个函数，而foldl给出的初始值却无处可放。因此我们可以把这个初始值作为启动最终操作的信号，一举两得解决了两个麻烦嘛(≧?≦)&/p&&p&接下来开始求解g。&/p&&p&根据前面的分析，可以知道g最终生成的函数至少会接受foldl中的初始值，而这个函数的运行结果和这个初始值的类型相同。为了求解省事，我们先尝试这个函数仅有一个参数的情况，不行再加嘛。这样一来，这个函数的类型也就可以确定了。&/p&&p&让我们来梳理一下目前的已知条件：&/p&&div class=&highlight&&&pre&&code class=&language-haskell&&&span&&/span&&span class=&nf&&foldl&/span& &span class=&ow&&::&/span& &span class=&p&&(&/span&&span class=&n&&a&/span& &span class=&ow&&-&&/span& &span class=&n&&b&/span& &span class=&ow&&-&&/span& &span class=&n&&a&/span&&span class=&p&&)&/span& &span class=&ow&&-&&/span& &span class=&n&&a&/span& &span class=&ow&&-&&/span& &span class=&p&&[&/span&&span class=&n&&b&/span&&span class=&p&&]&/span& &span class=&ow&&-&&/span& &span class=&n&&a&/span&
&span class=&nf&&foldr&/span& &span class=&ow&&::&/span& &span class=&p&&(&/span&&span class=&n&&b&/span& &span class=&ow&&-&&/span& &span class=&n&&a&/span& &span class=&ow&&-&&/span& &span class=&n&&a&/span&&span class=&p&&)&/span& &span class=&ow&&-&&/span& &span class=&n&&a&/span& &span class=&ow&&-&&/span& &span class=&p&&[&/span&&span class=&n&&b&/span&&span class=&p&&]&/span& &span class=&ow&&-&&/span& &span class=&n&&a&/span&
&span class=&nf&&g&/span& &span class=&ow&&::&/span& &span class=&n&&b&/span& &span class=&ow&&-&&/span& &span class=&p&&(&/span&&span class=&n&&a&/span& &span class=&ow&&-&&/span& &span class=&n&&a&/span&&span class=&p&&)&/span& &span class=&ow&&-&&/span& &span class=&p&&(&/span&&span class=&n&&a&/span& &span class=&ow&&-&&/span& &span class=&n&&a&/span&&span class=&p&&)&/span&
&span class=&nf&&z'&/span& &span class=&ow&&::&/span& &span class=&n&&a&/span& &span class=&ow&&-&&/span& &span class=&n&&a&/span&
&span class=&nf&&foldl&/span& &span class=&n&&f&/span& &span class=&n&&z&/span& &span class=&n&&bs&/span& &span class=&ow&&=&/span& &span class=&n&&foldr&/span& &span class=&n&&g&/span& &span class=&n&&z'&/span& &span class=&n&&bs&/span& &span class=&n&&z&/span&
&/code&&/pre&&/div&&p&然后带入一个bs试一下：&/p&&div class=&highlight&&&pre&&code class=&language-haskell&&&span&&/span&&span class=&kr&&let&/span& &span class=&n&&bs&/span& &span class=&ow&&=&/span& &span class=&p&&[&/span&&span class=&n&&b0&/span&&span class=&p&&,&/span& &span class=&n&&b1&/span&&span class=&p&&]&/span&
&span class=&nf&&foldl&/span& &span class=&n&&f&/span& &span class=&n&&z&/span& &span class=&n&&bs&/span& &span class=&ow&&=&/span& &span class=&n&&f&/span& &span class=&p&&(&/span&&span class=&n&&f&/span& &span class=&n&&z&/span& &span class=&n&&b0&/span&&span class=&p&&)&/span& &span class=&n&&b1&/span&
&span class=&nf&&foldr&/span& &span class=&n&&g&/span& &span class=&n&&z'&/span& &span class=&n&&bs&/span& &span class=&n&&z&/span& &span class=&ow&&=&/span& &span class=&n&&g&/span& &span class=&n&&b0&/span& &span class=&p&&(&/span&&span class=&n&&g&/span& &span class=&n&&b1&/span& &span class=&n&&z'&/span&&span class=&p&&)&/span& &span class=&n&&z&/span&
&/code&&/pre&&/div&&p&此时在foldl中需要先求值f z b0，而在foldr中我们惊喜的发现b0和z被拿出来放一起先求值，然后尝试解出g&/p&&div class=&highlight&&&pre&&code class=&language-haskell&&&span&&/span&&span class=&nf&&g&/span& &span class=&ow&&::&/span& &span class=&n&&b&/span& &span class=&ow&&-&&/span& &span class=&p&&(&/span&&span class=&n&&a&/span& &span class=&ow&&-&&/span& &span class=&n&&a&/span&&span class=&p&&)&/span& &span class=&ow&&-&&/span& &span class=&n&&a&/span& &span class=&ow&&-&&/span& &span class=&n&&a&/span&
&span class=&nf&&g&/span& &span class=&n&&b0&/span& &span class=&p&&(&/span&&span class=&n&&g&/span& &span class=&n&&b1&/span& &span class=&n&&z'&/span&&span class=&p&&)&/span& &span class=&n&&z&/span& &sp}