为他人惠

最近业余在翻译一篇教程“Understanding Haskell Monads”，取得了原作者的同意后准备将其译为中文，现在是用xelatex排版的，放在了github里。对于没有TeX环境的同学，可以直接阅读生成的PDF文档(会不定期更新)。

本人对于翻译没有什么经验，特别是对于一些专业术语，踟蹰良久，自己重读的时候有些地方也感觉多少有点拗口。如果有表达不清楚或者不准确的地方，欢迎拍砖。

Code Jam

做了Google Code Jam 2010的Qualification Round的三道题，开始都是用 Haskell 写的，第三道在处理大数据集时总是堆栈溢出，无奈之下改用了 Python，修改了一下算法，加入一个哈希表，避免重复运算，果然一下就搞定了。心里有了底之后修改了 Haskell 程序里面的代码，也加入一个 IntMap，也搞定了。

昨天在 reddit 上看见一位大牛，解决三道题用了六种语言 (每道题有小数据集、大数据集)，实在强悍。我的实现在Hg仓库里，链接。

几点体会：

1. 用 Haskell 处理状态的时候还是比较不习惯，尤其涉及改动函数接口或者临时调试；


2. 在处理大规模时算法的性能远比语言本身的性能重要；


3. 掌握一门瑞士军刀语言（可以用它快速的做任何事）。

很久没有如此专注过。程序设计涉及语言特性、算法、计算机体系结构，其实，短了任意一个都是缺憾。

Case Classes

Scala 里有个叫做 "case classes" 的东西，这个应该是从 ML 家族的语言特性启发而来，习惯于 C/C++ 的程序员可能较少看到这个名词。比如，我们要写一个算术表达式解析器，比如下面就是一些合法的表达式：

• 5


• -5


• 2+3


• foo


• 4 + foo

这在ML家族语言比如Haskell中非常容易表达。如下，这也是迄今为止我看到的最简洁的表达方式（看起来直接就是EBNF的描述方法）：

> data Expr =
>     Number Int
>   | Var String
>   | UnOp String Expr
>   | BinOp String Expr Expr
> deriving (Show)


Scala 中用 "case classes" 来描述，如下：

abstract class Expr
case class Var(name: String) extends Expr
case class Number(num: Double) extends Expr
case class UnOp(operator: String, arg: Expr) extends Expr
case class BinOp(operator: String, left: Expr, right: Expr) extends Expr

看起来没有 Haskell 那么简单直接，但远远聊胜于无了：

scala> val op = BinOp("+", Number(1), Var("x"))
op: BinOp = BinOp(+,Number(1.0),Var(x))

Haskell中类似，

ghci> let op = BinOp "+" (Number 1) (Var "x")
ghci> op
BinOp "+" (Number 1) (Var "x")

countdown problem

"Programming in Haskell" 的第十一章讲的是countdown problem，就是说给定一系列操作，比如加减乘除，和一系列自然数，比如2,5,9,17，求出可能的组合方法使得表达式的结果为给定数值，比如24。在这个简单的例子中，我们找到两种解法：

1. (5-2)*(17-9)


2. (5+9)/2+17

大家都知道，这就是在文曲星中常见的24点游戏。用Haskell写一道程序做这个工作只需近一百行代码。有兴趣的话，则可以去Channel9看视频，这一课的讲授者是Graham Hutton博士，也就是"Programming in Haskell"的作者。从问题的表述到求解，看着很清晰自然。（我后来花了点时间想自己写，一时之间却也写不出来，知易行难！）

最有趣的还是优化工作，给定六个数的时侯回比较慢一点。但Dr. Graham介绍了一些技巧使得原本需要45秒的计算最终降为1秒以内。Awesome!

CPS & Y-combinator

周末看了一篇"The Evolution of a Haskell Programmer"，里面列举了Haskell程序员写阶乘函数fac的各种实现方法，可以用两个成语来形容：琳琅满目、叹为观止。虽然感觉上有点类似孔乙己在纠缠茴香豆的茴字有几种写法，不过内容还真的挺有意思。其中有两个实现方法可以稍微聊一聊：1. CPS；2.利用Y combinator。

1. CPS - Continuation-passing style
   CPS是Gerald Jay Sussman和Guy L. Steele在1975年创建Scheme语言时提出的，其大意是处理的结果并不是像平时习惯的那样直接给出，而是给出一个临时结果。比如，写parser时，假设输入很复杂，我们不必一下给出解析的结果，而是步步为营。我们可以写出许多很简单，容易测试的小parser，比如parseNumber, parseString, 等等。每一步尝试一种解析，直到剩下的输入都不能被解析的为止。下面是个CPS风格的fac函数：
   > facCps k 0 = k 1
   > facCps k n = facCps (k . (n*)) (n - 1)
   > fac = facCps id
   
   
   
   • `.'在Haskell中是个函数组合算子，比如f (g x) = (f . g) x
   
   
   • (*) 在Haskell中是个函数，有两个参数，求得乘积。(n*)也是个函数，只有一个参数，如果给定m，则返回n*m -- 这叫做currying，Haskell中所有函数都是currying的。
   
   
   • 函数id直接返回输入参数本身，比如id 3 = 3, id fac = fac
   
   
   
   


2. Y combinator
   Y combinator是递归函数理论中的重要概念，说它是计算机科学的奠基性基础理论也不为过 -- MIT的计算机科学系的系徽就是它。它的数学形式是Y(f )= f (Y (f))，也就是说给定一个函数f，Y会求出该函数的不动点。有很多教程教你怎样一步步推导出Y函数，然而在Haskell中几乎直接原样照搬就行：
   > y f = f (y f)
   > fac = y (\f n -> if  n == 0 then 1 else n * f (n-1))
   
   
   
   • Haskell是lazy的，所以上面的递归定义没问题；
   
   
   • Haskell中函数名不能用大写字母开头，大写字母开头的是类名，类型名及其构造方法。
   
   
   
   

我以上帝的名义发誓，昨天我人品爆发居然写了个求平方根函数sqr = y (\f x -> x / f x)，因为y = x/y的不动点y'就是x的平方根，我敲了个sqr 3，居然得到1.732050... 精确到小数点后十几位 -- 后来不能重现，每次都stack overflow -- 而用稍微瞄一眼就知道这是应该的，因为这次没有递归结束条件，会无穷无尽递归下去。我确信没有误敲sqrt，从而调用了系统内置的平方根函数。莫非那是上帝开的小玩笑？:-)

mini-mini-compiler

源代码来自：http://www.cs.nott.ac.uk/~gmh/compiler.lhs

> data Expr                 =  Val Int | Add Expr Expr
>
> eval                      :: Expr -> Int
> eval (Val n)              =  n
> eval (Add x y)            =  eval x + eval y
>
> type Stack                =  [Int]
>
> type Code                 =  [Op]
>
> data Op                   =  PUSH Int | ADD
>
> exec                      :: Code -> Stack -> Stack
> exec []           s       =  s
> exec (PUSH n : c) s       =  exec c (n:s)
> exec (ADD    : c) (m:n:s) =  exec c (n+m:s)
>
> comp'                 :: Expr -> Code -> Code
> comp' (Val n)   c     =  PUSH n : c
> comp' (Add x y) c     =  comp' x (comp' y (ADD : c))
>
> comp                      :: Expr -> Code
> comp e                    =  comp' e []

它只支持整型和求和，表达式转换成指令的列表后在堆栈上执行，结果放在栈顶。假设expr为 Add (Val 1) (Val 2)，则 comp expr 会得到 [PUSH 1,PUSH 2,ADD]，把这个结果丢给exec 则得到[3]。

*Main> let e = Add (Val 1) (Val 2)
*Main> exec (comp e) []
[3]

区区23行代码，代码之美，莫过于此！

map/filter with foldr

第七课的小练习：http://www.cs.nott.ac.uk/~gmh/chapter7.ppt

> map' :: (a -> b) -> [a] -> [b]
> map' f = foldr (\a b -> (f a) : b) []
>
> filter' :: (a -> Bool) -> [a] -> [a]
> filter' f = foldr f' [] where
>     f' a b = if f a then a:b else b

用Haskell写个JSON解析器

本想自力更生试着用Haskell写个JSON解析器，一不小心网上一搜一大把，并且忍不住瞄了几眼。那就做个简单的修改加翻译吧，原文链接：http://snippets.dzone.com/posts/show/3660

> import Text.ParserCombinators.Parsec
> import System
> import qualified Data.Map as Map

引入一些必要的库，比如Parsec，祭起我们的利器哈！

> mainParser = do {
>               val <- valueParser
>             ; skipMany space
>             ; eof
>             ; return val
>             }

解析器的主函数，该函数以典型的Monad风格对输入数据调用valueParser函数进行解析，do中的操作是序列华的，每一个行都是一次匹配，这三行的意思是，它期待的输入的格式是JSON数据、可能的一些空字符、文件尾巴，如果解析成功就返回解析后的数据val。

> main :: IO ()
> main = do {
>         args <- getArgs
>       ; val <- parseFromFile mainParser $ args !! 0
>       ; print val
>       }

main函数先得到命令行参数存在列表args中，列表的第一个元素(args !! 0)作为文件名，parserFromFile是Parsec里的一个函数，它调用mainParser对命令行指定的文件进行解析，最后在打印出解析结果val。

> data JSON = ListValue [JSON]
>           | LiteralString String
>           | LiteralInt Integer
>           | LiteralBoolean Bool
>           | RecordValue (Map.Map String JSON)
>             deriving Show


上面的这些玩意儿叫做ADT，它的意思是：我们有JSON这样一种数据结构，它有五个构造函数ListValue, LiteralString, LiteralInt, LiteralBoolean和RecordValue，每个构造函数后面跟着的都是一种类型。最后，该数据结构继承所有Show类具有的行为 -- 这使得JSON类型的数据可以用print显示出来。

有了上面的定义后，我们可以方便的构造出一些JSON类型的数据，比如：

LiteralString "abc"
LiteralInt 123

在GHC或者Hugs中可以用:t来显示给定输入的类型：

:t LiteralString "abc"
LiteralString "abc" :: JSON

这是说LiteralString "abc"是个JSON类型。好了，接下来写几个简单的parser，我们可以dive & conquer。第一个Parser用来识别字符串 -- 字符串以'"'开头，中间是一个或者多个字符，最后有个'"'收尾。解析成功后会返回一个JSON类型的字符串。
> literalString :: Parser JSON
> literalString = do {
>     char '"'
>     ; val <- many1 letter
>     ; char '"'
>     ; return $ LiteralString val
>     }

接下来雷同的便是解析整型、布尔型：
> literalInt :: Parser JSON
> literalInt = do {
>     ; val <- many1 digit
>     ; return $ LiteralInt (read val)
>     }
>
> literalBoolean :: Parser JSON
> literalBoolean =
>         do {
>           string "true"
>         ; return $ LiteralBoolean True
>         }
>     <|> do {
>         string "false"
>         ; return $ LiteralBoolean False
>         }

这里'<|>'是个combinator，它用来连接两个parser，如果前一个解析不成功，就用下一个来解析。用'<|>'可以把整个JSON的解析写成如下形式：
> valueParser :: Parser JSON
> valueParser =
>      literalString
>  <|> literalInt
>  <|> literalBoolean
>  <|> recordParser
>  <|> listParser

其中还有两个parser没有实现：recordParser和listParser，分别用来解析object和array。list以'['打头，']'结尾，其中的数据以','分割：
> listParser :: Parser JSON
> listParser = do {
>     char '['
>     ; words <- sepBy1 valueParser listSeparator
>     ; char ']'
>     ; return $ ListValue words
>     }
>
> listSeparator :: Parser ()
> listSeparator = do {
>     skipMany space
>     ; char ','
>     ; skipMany space
>     }

最后就是解析object啦，打完收功！
> recordParser :: Parser JSON
> recordParser = do {
>     char '{'
>     ; defs <- endBy definitionParser listSeparator
>     ; char '}'
>     ; return $ RecordValue $ Map.fromList defs
>     }
>
> definitionParser :: Parser (String, JSON)
> definitionParser = do {
>     skipMany space
>     ; key <- many1 letter
>     ; char ':'
>     ; skipMany space
>     ; val <- valueParser
>     ; return (key, val)
>     }
>
> definitionSeparator :: Parser ()
> definitionSeparator = do {
>     skipMany space
>     ; char ','
>     ; skipMany space
>     ; return ()
>     }

似已登堂，尚未入室

曾经立志成为Linux内核高手，并为此努力研究了几年，后来无论是实习、还是现在的第一份工作都与此有所背离，于是就希望在compiler方面有所建树 -- 想要成为一个有功力、有底气的非内核程序员，这个应该是一个有意义的方向。于是就先读了SICP(当然其中还有老大的影响)，学了Scheme -- 记得当时在某个邮件列表上看见说Scheme很适合用来模拟别的语言。读SICP还是相当令人愉悦的，从中学到了很多有益的思想并有了一点函数式编程思维。

SICP中有一章是用Scheme写个Scheme解释器，比较好玩。后来看见网上有份详细的教程，用Haskell写个Scheme解释器 -- 因此顺便学了点Haskell，中间因为工作需要，学了Ruby。Ruby很适合用来实现DSL，而Scheme(包括其他Lisp方言)的macro系统也及其牛b。Haskell的ADT比较酷，加上Parsec，还有酷酷的pattern matching，使得它写parser相当轻松。

嗯，我要把Haskell学学好。:-)

Pure v.s Impure - 2

前一篇文章中缺乏示例，一眼看下去可能不太好理解。这次用几个简单的例子说明一下。

"Pure"总是和下面几个词联系在一起："referentially transparent"，"no side-effect"。基本上来说，它们表达的同一个意思。直观的意思就是：给定相同输入，一定会得到相同的输出结果。更正式一点的说法就是：给定一个函数f，把所有调用f的地方换成该调用的结果不会改变程序的意义。举个例子：假如f(3) = foo，把程序总所有调用f(3)的地方换成foo不会改变程序的结果，反之亦然。

更具体一点的例子，假设有个C函数，如下：
int add(int x, int y) { return x + y; }

显然，它是个没有side-effect的函数。好了，现在多了个需求：统计"add''函数的执行次数。这在允许side-effect的语言(如，C/C++等大多数主流语言)中简直是小菜一碟，加个全局变量就行：
static int count = 0;
int add(int x, int y) { count++; return x + y; }

注意：此时add函数已经是个具有side-effect的函数了。我们无法把程序中所有出现add(1,2)的地方都替换为3！作为一个side-effect，该函数还修改了count的值。做了替换之后，将使得我们统计执行次数的努力付诸东流。

那么，在Haskell之类的纯函数式语言中，如何做到这种统计功能呢？最先的add函数可以写出如下方式：
add x y = x + y

因为不允许side-effect[1]，那么最简单的方式就是引入一个额外的参数作为初始的调用次处，然后add每次都返回更新后的调用次数：
add x y cnt = (x + y,  cnt + 1)

郁闷的是，这样一来函数add的输入、输出都修改了，程序中所有调用到该函数的地方都要做相应修改。不过千万不要气馁，Haskell中提供了解决之道 - Monad。

[1] 对于习惯print调试大法的程序员来说，很可能会不习惯Haskell，因为向一个pure的函数中添加print语句是不允许的。Haskell用Monad来分隔pure/impure的行为。似乎这也是一些程序员选择OCaml/Standard ML而放弃Haskell的原因之一。但Pure的系统中，编译器有更多空间去做并发方面的优化。

Pure v.s Impure

在函数式编程领域有所谓Pure和Impure之分。简单来说，两者之间的区别就是Impure是有side-effect的，比如：赋值、异常和continuations；而Pure则意味着对于一个函数来说相同的输入一定会产生相同的输出，函数中也没有赋值操作这些用以改变某个状态的行为。Scheme和Standard ML是Impure的，而Miranda和Haskell则选择了Pure。

Pure有一个优点就是计算不依赖于执行顺序，因而可以容易的达到较好的并发性能、以及实现惰性求值(Lazy Evaluation)；而Impure则使得程序更直观、紧凑。比如，有个函数foo()，如果我们要修改它，得到整个程序中foo()的执行次数。在Impure系统中，这相当容易：添加一个变量记录foo()的执行次数即可。在Pure家族，这就不是如此简单了，我们可能需要修改foo的输入和输出：在输入中记录已经执行的次数，而输出中返回更新的次数 -- 而且糟糕的是，我们需要修改所有涉及到foo()调用的地方。

有人会想，我写个程序不就是为了得到某些输出吗？如果一个语言都不能改变状态（显然，输出涉及到屏幕状态的改变），那又有何用？如果读者以为Pure实在是没啥搞头，那就言之太早了。在Haskell中，程序员喜欢用Monad来模拟以上所有Impure的行为。

函数式编程初步

Dr. Erik Meijer 在MSDN Channel9上开设了Functional Programming Fundamentals，总共13次课，目前已经完成4课视频，并有各种格式可供免费下载。想了解函数式编程的同学不妨移步一观，课程基于Haskell，内容流畅且富有洞察，一定会有所获。

Erik提到了一个有趣的观点，那就是IDE的发展在OOP语言很成熟，而FP则相对较弱 -- 这和语法有很大关系。OOP的中心是object，而FP的重点则都在function。比如OOP中常有如下语法形式：

object.function(parameters)

而函数式编程中则有如下形式：

function(parameters)

IDE可以利用"."操作符去提示一个object里都有哪些函数。这是一个历史的偶然，却改变了很多人的编程习惯（如果习惯于IDE的话）。

Lambda the Ultimate

这几天在看Philip Wadler的名篇Monads for functional programming，三十页出头，挺享受。看着看着，不由自主的想到Scheme里面的continuation，总觉得它们两者之间本质上有某种相通之处，却因尚未深入理解所以无法言语 -- 一种奇怪的感觉。那个共通之处是什么呢？lambda，也就是函数。

Continuation用lambda封装控制流，而Monad则主要是Pure和Impure之间的桥梁，封装了side-effect。想不出什么一针见血的示例，去影院看了冰河世纪3，3D效果还行，暂时忘记monad/continuation，像周围放暑假的孩子们一样，开心的笑一把。

逆波兰表达式计算器

今天在learnyouahaskell.com上看见一段逆波兰表达式计算器的代码，挺美妙的。

solveRPN :: (Num a, Read a) => String -> a
solveRPN = head . foldl foldingFunction [] . words
    where foldingFunction (x:y:ys) "*" = (x * y):ys
          foldingFunction (x:y:ys) "+" = (x + y):ys
          foldingFunction (x:y:ys) "-" = (y - x):ys
          foldingFunction xs numberString = read numberString:xs

第一行是函数solveRPN的类型声明，略过。简单的流程解释一下就是：先用words将字符串tokenize，然后用上foldl扫描归纳之，最后将结果存在list的第一个节点，用head取出来。简单明了，一气呵成。比如，给定字符串"10 8 + 2 -"。下面是归纳步骤。

words "10 8 + 2 -" 得到 ["10", "8", "+", "2", "-"]，接下来便是：foldl [] ["10", "8", "+", "2", "-"]。应用传递给foldl的函数foldingFunction，得到运算过程：

1. fold1 [] "10" [""8", "+", "2", "-"]


2. foldl [10] [""8", "+", "2", "-"]


3. foldl [10, 8] ["+", "2", "-"]


4. foldl [18] ["2", "-"]


5. foldl [18, 2] ["-"]


6. foldl [20]

foldl结束后head [20]，便得到20。需要注意的是第六行，它的意思是(read numberString) : xs，而不是read (numberString:xs)。优先级问题哈。

不怕错误的猫

-- compile with: ghc --make cat.hs
import System.IO
import System.IO.Error
import System.Environment

cat :: String -> IO ()
cat fn = do
  contents <- readFile fn
  putStr contents

handler :: IOError -> IO ()
handler e
    | isDoesNotExistError e =
        case ioeGetFileName e of
          Just path -> putStrLn $ path ++ ": file not found"
          Nothing -> putStrLn "Oops! File unknown."
    | otherwise = ioError e

main = do args <- getArgs
          if null args
              then interact id
              else mapM_ (\fn -> cat fn `catch` handler) args

A Tale of Two Cats

每学一门语言首先想做的是用它写一个类UNIX下cat命令的东西，简单但至少涉及命令行处理和文件I/O。

Scheme版本：

(define (cat . arg)
  (let ((port (if (null? arg)
                  (current-input-port)
                  (car arg))))
    (let loop ((c (read-char port)))
      (if (not (eof-object? c))
          (begin
            (display c)
            (loop (read-char port)))))))

(define (main args)
  (if (null? (cdr args))
      (cat)
      (for-each (lambda (port) (cat port) (close-input-port port))
                (map open-input-file (cdr args)))))

Haskell版本：

import System.Environment

cat :: String -> IO ()
cat fn = do
  contents <- readFile fn
  putStr contents

main = do args <- getArgs
          if null args then interact id else mapM_ cat args

学了Haskell之后才知道Python里面的缩进、List Comprehension等似乎是从Haskell学来的。上面两个cat功能一样，区别是Haskell cat比较懒一点，那是因为Haskell是惰性求值的。勤快一点的版本只需要bytestring重新实现cat函数：

import qualified Data.ByteString.Lazy as B

cat :: String -> IO ()
cat fn = do
  bs <- B.readFile fn
  B.putStr bs

What is next?

我现在的状态大概可以用“带薪学习”来形容 -- 但老实说，这种状态下的学习效率多数都很低下。

终于仔细看完"Write Yourself a Scheme in 48 Hours"，为了理解里面的内容，顺便学了点Haskell。对于Monad的部分仍然似懂非懂，但整体思路还是非常清晰的，和SICP中的实现没有多少差别，只不过Haskell程序看起来像是一条条规则的堆砌。

Haskell中有我喜欢的特性，也有我不喜欢的 -- 或许是因为不习惯或者没有搞懂。对于程序员来说，语言只是最基础的东西。嗯，找个framework好好钻研钻研吧，顺便写点笔记啥的消磨消磨时间。

Haskell的天空 - 函数定义

Haskell是一门纯函数式语言。不同于C/C++等语言的是，函数式语言中的函数乃是语言中的一等公民，它们本身也可以作为函数参数或者返回值，就像整型、字符串一样。几乎所有函数式语言的教程中，第一个示例函数都是求阶乘。在Haskell中：
fac 0 = 1
fac n = n * fac(n-1)

这看起来和它的数学定义几无二致。理解它只需要明白一句话：Haskell的函数定义是基于逐行模式匹配的。将其载入ghci之类的解释器：
Prelude> :load "fac.hs"
[1 of 1] Compiling Main ( fac.hs, interpreted )
Ok, modules loaded: Main.
*Main> fac 4
24
*Main> fac 40
815915283247897734345611269596115894272000000000

有了上面的热身之后add函数的定义则很容易理解了：
add x y = x + y


这个简单的add函数可以用于演示所谓"curried functions"，由著名美国数学家、逻辑学家Haskell Brooks Curry提出，haskell语言、curry算子都是以其名、和姓命名。"curried functions"的意思是，函数可以部分求值，不必强制程序员提供所有的参数。"add 2 3"的求值结果是5，"add 2"的结果则是一个高阶函数，它对任何输入数值加二。
*Main> add 1 2
3
*Main> let add2 = add 2
*Main> add2 3
5

另外，Haskell还支持函数的composition，比如数学记法中(f · g)(x) = f(g(x))。Haskell中用点号(.)表示function composion。如下例，求值一个列表中所有数值的相对数：
Prelude> map (negate . abs) [5,-3,-6,7,-3,2,-19,24]
[-5,-3,-6,-7,-3,-2,-19,-24]