58853867
原haskell交流群
Tag Archive for 'haskell'
Page 2 of 4
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:测试的数据貌似不是很好（按说该用个随机数列），不过知道有这回事就行了~
学习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。不过我觉得应该辩证地讨论它。
标题党了，阿门。其实更像C++，java之类语言中的引用。这就是Data.IORef中的IORef，使用它可以创建真正mutable的变量。
在do-notation中可以写这样的代码：
do { … x< - return x+1; }
很像变量，但其实不是真正的mutable，因为它本质上就是(\x -> ..) x+1 ，两个x不在同一个scope，内存中没有值发生改变。
而Data.IORef则是在内存中搞一块地方，提供对这一块内存中输入输出的函数，并通过IO monad将它隔离开，这样就有点真正的变量的意思啦。大致就这几个函数：
newIORef :: a -> IO (IORef a) --创建一个新的IORef（废话～，不过有时也觉得haskell挺”面向对象”的…） readIORef :: IORef a -> IO a writeIORef :: IORef a -> a -> IO ()
太直白了，一个读一个写，都是IO操作，只不过操作的对象不是标准输入输出，而是内存里的一个值。值得一提的是，haskell的惰性求值让它只有在必要的时候才会读取，这样一来在传递参数的时候就不会访问值所在的内存，就像C中传递一个指针那样节约。唉，发明haskell的那个委员会真是一群天才。
Ps：学习haskell到熟悉基本的语法之后，强烈推荐那个《make yourselves a scheme in 48 hours》的教程！通过用haskell实现一个完整的scheme，对于monad，类型系统的理解绝对会大有好处!
FeedBurner
Comment