Fleurer.Lee

上个星期翻的那篇文章里貌似提了下parsec，照着文档试玩了下。之前貌似玩过ruby的那个代码生成工具racc，它的名气不是很大而且文档不怎么全，感觉不是很爽。写了个helloworld就再也没碰。再写个parsec的helloworld。

语法分析的helloword就是表达式计算了。parsec跟*acc貌似不怎么像。不过无非都是上下文无关文法嘛，这个有名的ebnf：

expr     ::=   expr  ’+’   term  |  term
term     ::=   term  ’*’   factor   |  factor
factor   ::=   ’(’  expr   ’)’  |  digit+
 
digit    ::=   ’0’  |  ’1’  |  ...  |  ’9’

葫芦画瓢地写出parsec版：

import Text.ParserCombinators.Parsec
import qualified Text.ParserCombinators.Parsec.Token as P
import Text.ParserCombinators.Parsec.Language (haskellDef)
 
do_parse p input
	= case (parse p "" input) of
		Left err -> do {
			putStr "parse error at:";
			print err;
		}
		Right x -> do {
			print x;
		}
 
expr :: Parser Int
expr = do {
	a < - expr;
	char '+';
	b <- term;
	return (a + b);
} <|> term
 
term :: Parser Int
term = do {
	a < - term;
	char '*';
	b <- factor;
	return (a*b);
}
 
factor :: Parser Int
factor = do {
	char '(';
	a <- expr;
	char ')';
	return a;
} <|> number
 
number = do {
	a < - many1 digit;
	return (read a);
}

parsec， Parser Combinators嘛。当然跟*acc那套不一样了。函数在这里就都是个组合子，可以像零件那样方便地组合。

do_parse这个函数取两个参数，一个是parser，一个是表示表达式的字符串。haskell的do-notation除了允许像python那样的缩进风格之外，还有这里用的c-style。parsec就用monad来表示sequence，< |>来表示choice，某种意义上讲，貌似只要它俩就足够构造出复杂的parser了。咋一看可能要比*acc那伪bnf的观感麻烦得多，但别忘了组合子的优势：可以方便地组合。用几个简单的组合子可以方便地构造出复杂的组合子，复杂的组合子继续组合成更复杂的组合子，而使用起来可是极为简洁。

嗯，废话真多。
进ghci测试一下

*Main> do_parse expr "1+1"
*** Exception: stack overflow

查手册，发现这么一句“Unfortunately, left-recursive grammars can not be specified directly in a combinator library. If you accidently write a left recursive program, the parser will go into an infinite loop! ”

哑然。
组合子还是函数嘛，想想在c中要是定义这样的函数会怎样。

Paser expr(){
	a = expr();
	...
}

不过“However, every left-recursive grammar can be rewritten to a non-left- recursive grammar. The library provides combinators which do this automatically for you (chainl and chainl1). ”

嗯。手册里貌似写了个表达式计算的例子，就直接用了Parsec内置的ParsecExpr：

import   ParsecExpr
 
expr      ::  Parser   Integer
expr      =  buildExpressionParser      table   factor
          < ?>  "expression"
 
table     =  [[op  "*"  (*)  AssocLeft ,   op  "/"  div  AssocLeft]
             ,[op  "+"  (+)  AssocLeft,    op  "-"  (-)  AssocLeft]
             ]
          where
             op  s f  assoc
                =  Infix   (do{  string   s;  return  f})   assoc
 
factor    =  do{  char  ’(’
                ; x  < - expr
                ; char  ’)’
                ; return   x
               }
          <|>  number
          < ?>  "simple   expression"
 
number    ::  Parser   Integer
number    =  do{  ds < -  many1   digit
                ; return   (read   ds)
               }
          <?>  "number"

呃，运算符的优先级，左结合都考虑了。不过这样也太没意思了，该我写的都让它给内置了，不过那句话不是提到有个chainl1么，就用chainl1重写：

module Main where
 
import Text.ParserCombinators.Parsec
import qualified Text.ParserCombinators.Parsec.Token as P
import Text.ParserCombinators.Parsec.Language (haskellDef)
 
main = do {
	input < - getLine;
	do_parse expr input;
}
 
do_parse p input
	= case (parse p "" input) of
		Left err -> do {
			putStr "parse error at:";
			print err;
		}
		Right x -> do {
			print x;
		}
 
lexer = P.makeTokenParser haskellDef
parens = P.parens lexer
symbol = P.symbol lexer
naturalOrFloat = P.naturalOrFloat lexer
 
expr = term `chainl1` addop
term = factor `chainl1` mulop
factor = parens expr < |> number
number = do {
	norf < - naturalOrFloat;
   	case norf of
		Left n -> return (read $ show n);  --so sucks
	   	Right f	-> return f;
}
 
mulop = do { symbol "*" ; return (*); } < |> do { symbol "/" ; return (/); }
addop = do { symbol "+" ; return (+); } < |> do { symbol "-" ; return (-); }

用到了ParsecToken。它就直接使用了haskell的token定义，也就是说，你可以在这个程序里使用haskell的注释

*Main> do_parse expr "1+{-- it's a comment --}(1/2)"
1.5

作者：Dr. Syntaxfree
翻译：ssword
原文：http://syntaxfree.wordpress.com/2006/12/12/do-notation-considered-harmful/

16:20:11 [Botje] Monads可以算是_有史以来_被复述最多的特性了。
monads have to be the singly most tutorialized feature _EVER_
16:20:17 [monochrom] 为啥这样数学的抽象工具吸引了这么多科普作家，却少有数学的抽象方式讲解？
Why would such a mathematical, abstract tool attract so many popular science authors who do not explain the tool in its mathematical, abstract term?
(from #haskell@irc.freenode.net)

Monads无疑就是haskell中最显眼的特性了，作为处理这堆乌合之众（输入输出，并发，异常，以及跨语言调用）和产生一定副作用的标准工具，每个haskell程序员都得在一定程度上面对monad，而在许多人看来，monad无非就是一件以纯洁性和引用透明之名而套上的皮毛罢了。

谈起monads之难，诚然有无数的理由 — 它那邪恶并罕见的名字，深奥的范畴论，命令式世界（无处不在的副作用，脆弱的内置抽象机制）和函数世界（无处不在的抽象，副作用则须经深奥的数学机制）的文化冲突。不过我觉得还有一个大门槛阻碍我们理解monads：它那极致的语法糖。

Do-notation给monadic风格编程提供了一种伪命令式的观感。许多有名的教程都是直接拿Monadic风格的IO做开篇，这让人觉得它就是haskell为与外面有时序的世界交流而内置的一个命令风格模式。而do-notation — 在IO的上下文中引入 — 掩盖了monad在haskell中实现的本质就是一个简单的类型类，并让人忽略了它作为计算模型的存在。

显然，好东西都在Haddock文档中关于Control.Monad的那部分，但要发现它，我们得先放下do-notation才行。

关于函数定义从do到“bind”notation之间的转换有几条简单规则，它们讲解起来很容易，并且已经有了文档。不过在这里我对语法的转换规则不感兴趣，而要以bind-notation的方式重新讲解IO的基础 — 这样monad风格的结构就可以更清楚地显示出来了。

最重要的两个IO操作应该就是putStr和getLine了，它们差不多就相当于lisp/scheme中的print和read，Basic中的PRINT和INPUT之类。作为一门纯函数式、严格类型的语言，Haskell中的这些操作应该都是用可标明类型的函数来表示。

我们先看看putStr的类型：

putStr :: String -> IO ()

（我们假定读者已经有阅读类型声明的能力）显然，putStr是取一个字符串做参数，而它的返回结果可以读作“外部世界(Outside World)” — 实际上，要不是这个蹩脚的表达式，OutsideWorld完全可以看作是IO的别名。我们再看看getLine：

getLine :: IO String

getLine没有参数，只是从外部世界得到一个字符串。作为一个来自外界的字符串，在处理上有一定限制 — 这时就该monad出场了。通过monadic的结构来处理IO，我们可以使用几个简单的函数来没有引用透明地操作getLine所得的变量。

第一个函数是“bind” — 简单起见，由中缀运算符 >>= 表示。它的类型是：

(>>=) :: forall a b . m a -> (a -> m b) -> m b

“Bind”取一个monadic值（我们这里是一个IO String），一个将一个纯值（如String）转为一个monadic值的函数做参数，并返回一个monadic值。关于它用法的一个例子：

shout = getLine >>= (putStr . map toUpper)

Bind的第一个参数是一个IO String类型的monadic值，第二个参数是函数(putStr.toUpper)，它取一个字符串做参数并返回一个IO “coin”。如你所料，shout的类型就是个外部世界的值 — 即一个 IO “coin”。

shout :: IO ()

定义monad第二个基本函数是return。它的类型为：

return :: (Monad m) => a -> m a

例如，

superTwo = return "Two"

很简单。

superTwo :: (Monad m) => m String

有了这两个函数，就可以定义出一个完整的monad了。其他所有的monadic函数都是用它俩定义出来的。一个严格的monad必须满足以下的三个数学性质。

1. (return x) >>= f == f x
2. m >>= return == m
3. (m >>= f) >>= g == m >>= (\x -> f x >>= g)

由此看出，我们可以用haskell完整地定义出monad — 这就表明了它不是一个内置的特性，而是一个抽象的数学结构。就像rings，borelians，quaternions之类的抽象数学结构一样得以榨干haskell的表达能力：

class Monad m where
    (>>=) :: forall a b . m a -> (a -> m b) -> m b
    return :: a -> m a

在haskell的入门学习中，你可能已经用了几个monad的实例，如列表（[a]），Maybe还有，是的，IO。每个特定实例的“bind”和“return”实现都可以在一个monad教程中找到。免得再写另一个monad教程，从现在开始，我们就专注在IO monad上。

通过满足以上规则的(>>=)和return可以构造出许多有用的操作 — 这在Haddock文档中Control.Monad那部分里有很多讲解。我们这里还得研究另一个函数 — bind的一个变体，忽略了返回结果的第一个参数（传递给下一个计算），这样一来我们就可以简单地将不相干的操作连续起来。这个函数的类型是：

(>>) :: (Monad m) => m a -> m b -> m b

根据描述，(>>)实现起来非常的简单：

x >> y = x >>= (\_ -> y)

譬如，这就是连续两个putStr操作的方法（要知道putStr对前一个putStr返回的()并不感兴趣）。

example = putStr "Print me! \n" >> putStr "Print me too! \n"

现在我们可以写个monad风格IO的简单例子，用bind notation:

greet = getLine >>= (putStr . ("You're "++) . (++" years old! \n")) >> putStr "Congratulations! \n"

这样，IO String里的内容就应用在了这个函数里：

\x-> ((putStr . ("You're "++) . (++" years old! \n")) >> putStr "Congratulations! \n") x.

继续推导：

(\x-> ((putStr . ("You're "++) . (++" years old! \n")) x) >>= (\_ -> putStr "Congratulations! \n")

这就连续了两个print操作。通过这个数学结构描述连续行为时，haskell中的语法糖可以允许你在一个伪命令式（不是真的命令式）的风格中忽略掉那堆复杂的括号套括号、lambda抽象、point-free表达式和符号关联。

greet = do {
    age < - getLine;
    putStr (”You’re “++age++”years old! \n”);
    putStr (”Congratulations! \n”);
}

不管这命令式的外表，它并非命令式的变量赋值是毋庸置疑的：只不过是一个把monadic计算（这里是从“外部世界”读值）结果保存到一个符号中的便捷语法罢了，这样我们就可以在后面再处理它，而不必纠结那大块的lambda表达式。

到现在明智的读者已经认清了do-notation的肤浅本质，可以继续他basic haskell或monad的学习了。更重要的是，他会在以后面对monadic parser这样复杂的数学结构时理解到do-notation的真正含义。

实际上，出于智慧与理性，我建议大家在每个“toy”中都应该使用bind notation，善求知的haskell程序员的学习，都是按照自己的思路去理解，直到那大块的函数将大脑的栈塞满为止。理解简单的IO问题并不是很重要，而深入理解连续的副作用操作在传统的命令式语言与函数式语言中IO函数组合的不同才是学习haskell编程思想的重中之重，这对摒弃那种“查手册的机器人”的编程习惯也是大有好处的。

这是骆驼

这个待考

这个呢？

八皇后问题大家都已耳熟能详, 貌似没有赘述的必要.

看了lich_ray同学的这篇用 Python 秒掉八皇后问题!, 对list comprehension的表达能力有了新的认识. 他的楼下们几乎列出了所有语言的八皇后求解实现, 其中就有albertlee大牛的haskell版本:

import Control.Monad
import Control.Monad.Writer
import Data.List
 
diagonal (x1,y1) (x2,y2) = x1 + y1 == x2 + y2
                        || x1 - y1 == x2 - y2
 
nqueens n = execWriter $ f [1..n] 1 []
    where f [] _ ps = tell [ps]
          f cs r ps = forM_ cs $ \c ->;
                          unless (any (diagonal (r,c)) ps) $
                              f (delete c cs) (r + 1) ((r,c):ps)
main = print $ nqueens 4

我愚钝, 没看懂. 自己写一个吧, 解题思路无非都是大同小异, 直接把lich_ray同学的话copy过来:

归纳法定义：
　　什么是归纳法定义？回忆一下经典的求级数例程是怎么写出来的。我们根据数学归纳法得到：
　　f (0) = 1
　　f (n) = 1 + f (n – 1)
　　然后把这些抄成编程语言的形式。对于函数 queens 也是这样，我们要确定这个函数的递归下界和递推表示。
　　递归下界很好办，就是 queens(n,0) （此处 n 忽略，因为不影响结果）的输出结果。对于一个没有列数的棋盘，只有一个解，空解 []；同时，输出的解集也只有这一个元素，为 [[]]（下面的数学定义使用了集合表示代替列表）。
　　f (*,0) = {{}}
　　递推表示是什么呢？我们可以在纸上画画图，不难发现，对于一个解，你画出的最后一个位置就是在前面已画出的少一个棋子的格局的基础上再加一个位置安全的棋子。设这个“加”函数为 g (x,y)，“安全”函数为 s (x,y)。那么
　　f (n,m) = {g (x,y) | x ∈ [0, n], y ∈ f (n,m-1) s (x,y) = true}

我初学haskell, 写的很难看. 思路和lich_ray同学的貌似并不完全一致, 不过有一点是毋庸置疑的, 那就是归纳法. 一个m列n行的”皇后问题”可以看作是给一个已经放n个皇后的m列n行的棋盘加一个皇后, 到最后归纳到一行的棋盘, 那就有m种放法. 按照bonus的说法, 就是”Usually you define an edge case and then you define a function that does something between some element and the function applied to the rest.” , 这貌似就是递归求解的基本思路了.

求解的queue函数貌似需要两个参数, 两个Int值表示列数和行数, 皇后问题的一个解中只要能表示出所有皇后的所在的列就行了, 放在一个[Int]中, 而queue会有很多解, 所以queue的返回类型应该为[[Int]]. queue m (n-1)所得的结果中有的不能再放皇后了啊, 怎么办? filter之留下还能放的: filter putable $ queue m (n-1). 好了, 剩下的都是可以放皇后的, 都给它放上: concatMap put $ filter putable $ queue m (n-1) . 为什么concatMap呢? 因为put会有很多种结果啊. 好的, 就这么一句:

queue m n = concatMap put $ filter putable $ queue m (n-1)

接下来写出putable和put的实现就好了, 想一下, 什么能样的棋盘是putable的? 有安全的地方的棋盘就是putable的, 即(safe_places xs /= []). 该怎样put呢? 在现有的棋盘上所有安全的地方放一个皇后, 把每种情况都放在一个list里就行了: (map (:xs) $ safe_places xs). 两个函数都用了一个safe_places xs , 貌似有重复调用, 效率可能会低些? 呃, 不过据说haskell是有引用透明的, 以相同的参数调用同一函数时貌似会有相应的优化.

最后实现safe_places就行了, 不扯了, 上代码

module Main where
import Data.List
 
queue :: Int -> Int -> [[Int]]
queue m 1 = [ [x] | x  <- [1..m] ]
queue m n = concatMap put $ filter putable $ queue m (n-1)
    where
        putable xs = (safe_places xs /= [])
        put xs = map (:xs) $ safe_places xs
        safe_places xs = [1..m] \\ (concatMap (\(x,y) -> [x-y,x,x+y]) $ zip xs [1..])