haskell搞并行还是挺方便的。纯函数式没状态嘛，这儿锁啊钥匙啊什么的都不用管了。有个Control.Parallel，里貌似只有两个函数，一个par，表示两个并行计算；一个pseq，表示连续计算。参数都是两个名字。像处理个分治算法啥的，就再合适不过了。于是再次膜拜惰性求值，写起来真的太奇特了。
module Main where
import Control.Parallel
--the classic one
qsort :: (Ord a) => [a] -> [a]
qsort [] = []
qsort (x:xs) =
(qsort lt) ++ [x] ++ (qsort gt)
where
lt = filter (<x) xs
gt = filter (>=x) xs
--the parallel one
psort :: (Ord a) => [a] -> [a]
psort [] = []
psort (x:xs) =
sorted_lt `par` sorted_gt `pseq` (sorted_lt ++ [x] ++ sorted_gt) ----unbelieveable,isn't it? :>
where
sorted_lt = psort $ filter (<) xs
sorted_gt = psort $ filter (>=x) xs
main = do {
list <- return [5000,4999..1];
print $ qsort list;
print $ psort list;
}profile下，给ghc添加一个编译选项 -prof -O：
ghc --make -prof -O -auto-all quicksort.hs
执行程序，加一个选项 +RTS -p，它会在本目录下生成一个quicksort.prof文件
quicksort +RTS -p
quicksort.prof文件的部分内容：
Mon Jul 20 16:40 2009 Time and Allocation Profiling Report (Final)
quicksort +RTS -p -RTS
total time = 6.86 secs (343 ticks @ 20 ms)
total alloc = 1,401,627,416 bytes (excludes profiling overheads)
COST CENTRE MODULE %time %alloc
qsort Main 69.1 49.9
psort Main 30.9 49.9
可见在这台双核的机器上，性能提高了一半多 :)
ps:测试的数据貌似不是很好（按说该用个随机数列），不过知道有这回事就行了~
Published on
2009年07月20日 in
笔记.
Tags: FP, monad.
Feather 2009-07-19 21:46:08
世事恰如迷局, 寻人, 失散, 流落, 皈依, 纷乱无绪, 及至谜底解开, 那人却已站立在你面前.
Continue reading ‘王猫猫谈Monad’
学习haskell一段时间了，关于monad等等东西仍停留在理论上的理解而不了解其应用，练下手总是好的。于是参考这个有名的《Write Yourself a Scheme in 48 Hours》和parsec的手册，实现了个简单的语言。只是简单的递归解析语法树，也没有中间编译，也没有垃圾收集，实现起来还是比较简单的。某天天气不错，晴天，就叫它Fineday。
Fineday的语法比较接近javascript（其实一开始是打算搞成basic-style的，可是不会写bnf…囧），有基本的控制流程if，while,for，有匿名函数，有闭包，有数组，有hash—当然，是忽略了许许多多细节的实现，例如没有求数组length的函数，只有puts而没有gets，没有Int类型（开始的时候为了方便一切都是double），没有像样子的错误提示…呵，but it runs.
像下面这段可以算是一个猥琐的oo实现了:
function makeCounter(init){
var this={
'n':init,
'add':function(n){
this['n']=this['n']+n;
return this['n'];
}
};
return this;
}
var counter=makeCounter(1);
puts((counter['add'])(2)); --3
puts(counter['add'](3)); --6前几天又翻了下姐姐送的那本《the ruby way》的序，matz谈及ruby语言的设计时提到了“道”，以及编写ruby时的信条：语言应该为人类服务，而不是相反。于是认识到，语言的设计绝非信手拈来的活计，设计中有太多需要斟酌的地方，有太多需要用心思考的地方。我等玩代码的，还是差的太远了。
项目地址：http://code.google.com/p/fineday/
呵，空白的，懒得再写字了。可以用svn获得源代码及编译的exe文件。
作者：Neil
翻译：ssword
原文：http://neilbartlett.name/blog/2007/04/11/haskell-an-imperative-language-with-mutable-state/
Haskell是一门惰性的纯函数式语言，也就意味着其中没有可变的变量。呃，有，没有？看下这个Factorial的haskell实现吧：
fact n = runST (do
r < - newSTRef 1
for (1,n) (\x -> do
val < - readSTRef r
writeSTRef r (val * x))
readSTRef r)嗯，我可没说这样写好。实际上，这样写很糟糕，一行纯函数式代码就可以漂亮的搞定同样的工作。不过请注意下这代码与命令式语言是如何的相像，如对“可变变量”r的破坏性更新。再贴一下，与同等的C代码做个对比：
fact n = runST (do | int fact(int n) {
r < - newSTRef 1 | int r = 1;
| int i;
for (1,n) (\x -> do | for(i=1;i< =n;i++) {
val <- readSTRef r |
writeSTRef r (val * x)) | r = r * i;
| }
readSTRef r) | return r;
| }瞧，你几乎可以把C的代码一对一地翻译成haskell。不过得承认，haskell的语法要猥琐些。
这一切是如何做到的呢？答案就是ST monad，有了它就可以写出有内部状态更新而对外仍保持纯粹的算法。runST函数是亮点，它创建了个初始的空状态，然后执行一系列的状态转换，到最后再销毁它。fact依然是Int->Int的纯函数，依然保留了引用透明。
另一个亮点是那个“for”，看起来跟个关键字一般，不过它本质就是一普通函数，定义如下：
for :: (Int,Int) -> (Int -> ST s ()) -> ST s ()
for (i,j) k = sequence_ (map k [i..j])
同理，我们也可以定义出foreach，if，while等等。有haskell这般强大的表达力，没必要再将控制流的操作定义为语言的关键字；我们甚至可以根据自己的需求来发明新的控制流程。
不过你看出来了没？没人会正二八经地像上面那样实现factorial。而且，我们真的希望如这般曲解haskell，以取悦从C过来的老程序员么？
是的，问题就在这里。有这项技巧，是为那些已知难以使用函数式风格或递归搞定的算法提供的折衷。同样，很多算法需要用到数组—–有限的内存和固定的访问时间—–使其更易于处理。在ST monad中实现数组很容易，但在传统的纯函数式代码中就要困难多了。（UPDATE：Cale说，纯代码中实现不可变的数组还是很容易的，只有可变的数组实现其来才困难）。
恩，ST monad和STRef表示了外部不可见的局部状态，那么全局的可变状态呢？我们可以用IO monad和IORef做到。当然，在用IO的时候就没有像runST那样回到纯代码的函数了[1]。
对我，这引发的思考就是：haskell是真正的纯函数式语言吗？我觉得不是—–它超越了纯函数式。它是既允许命令式编程，又使用强大类型系统来把有副作用的代码与纯代码分离。这一点，令它强大无比。
[1] 这不是绝对…其实有个方法：unsafePerformIO。不过我觉得应该辩证地讨论它。
当时小，不懂事，初学函数式编程时一头就扎的就是continuation和monad，一直搞不明白就一直放着。上个星期在ShiningRay老师的这篇《简介延续“Continuation”》里看到：
貌似很泪流满面的样子，没想到这东西有这么简单。之后在图书馆里写了一个小时的伪代码，貌似搞明白了。按照Continuation Passing Style(cps)的设定，函数没有返回值，而是用函数的运算结果调用函数最后一个参数，很简单吧。不过那些特性又是从何而来呢，像保存状态尾递归优化之类？现在想想，之前之所以不理解，大概就是因为不会写cps的递归吧，其实动手写的话也就那回事。国父孙先生不是说么，知难行易。
如下伪代码，求前n个自然数的和：
def sum(n):
if (n==0): 0
else :
n+sum(n-1)换成等价的前缀形式(if就懒得改了，知道这回事就好)：
def sum(n):
if (n==0): return 0
else
return add(n, sum(sub(n,1)))好，换成cps：
def sum(n,c):
if (n==0): c(0) #“延续”下去，而不是返回
else:
sub n, 1, (\x1 -> #一个lambda，匿名函数
sum x1, (\x2 -> #递归在这里
add x2 ,n ,c))再一个迭代的例子：
def iter_sum(n, r):
if (n==0) : return r
else : iter_sum(n-1, r+n)换成前缀：
def iter_sum(n,r):
if (n==0): return r
else : iter_sum(sub(n, 1), add(r,n))cps:
def c_iter_sum(n,r,c):
if (n==0): c(r)
else:
sub n, 1, (\x1 ->
add r, n, (\x2 ->
c_iter_sum(x1, x2, c))) #尾递归可以看出，cps中引入了些自由变量，把函数求值的结果放在堆里而非栈中，于是就可以实现不限深度的递归。不过这样貌似增加了垃圾收集的负担，没有银弹哇。
contiuation中只有“延续”而没有“返回”，每一步“延续”都是对后面函数的调用，通过一条函数与函数的链构成了顺序结构。ShiningRay老师貌似说过，一个函数调用就是一个状态。callcc貌似就是把“延续”的下一个函数保存，从而保存了状态。Smalltalk的那个Seaside框架貌似就是把contiuation作为对象持久化，在下次访问时找到这个持久化的contiuation将状态还原，从而模拟出仿桌面程序开发的效果。貌似要比asp.net那WebForm的实现更加自然些。
FeedBurner
Comment