haskell教程.txt

Haskell教程(by rufi) 传统的Basic,Pascal,C++,C#,Java,Python等都是命令(imperative)编程语言, 程序语句有一定的执行次序. 函数(functi

    
   qsort7 []=[] 
   qsort7 (x:xs)=qsort7 xl ++ [x] ++ qsort7 xr 
         where (xl,xr)=split x xs 
               split _ [] = ([],[]) 
               split e (x:xs) | x<e   = (x:l,r) 
                              | True  = (l,x:r) 
                              where (l,r) = split e xs 
                               
                               
   qsort8 []=[] 
   qsort8 (x:xs)=qsort8 xl ++ (x: qsort8 xr) 
         where (xl,xr)=split x xs 
               split _ [] = ([],[]) 
               split e (x:xs) | x<e   = (x:l,r) 
                              | True  = (l,x:r) 
                              where (l,r) = split e xs                            
                               
                               
                               
   qsort9 ls  = qsort' ls [] 
       where  qsort' []     acc = acc 
              qsort' (x:xs) acc = qsort' xl (x:qsort' xr acc) 
                 where (xl,xr) = split x xs 
                       split _ [] = ([],[]) 
                       split e (x:xs) | x<e   = (x:l,r) 
                                      | True  = (l,x:r) 
                                      where (l,r) = split e xs                            
                               
                               
   qsort10 ls = qsort' ls [] 
       where  qsort' []     acc = acc 
              qsort' (x:xs) acc = split x xs [] [] acc 
                 where split e [] l r acc = qsort' l (e:qsort' r acc) 
                       split e (x:xs) l r acc | x<e  = split e xs (x:l) r acc 
                                              | True = split e xs l (x:r) acc     
                                               

   qsort6 对算法的体现最直接, 最容易理解. 以后每一次改动都是为了提高程序运算的效率. 
    
   尽管qsort10已经排得很快了, 但 merge sort 可以排得更快. 
    
   msort:: Ord a => [a] -> [a] 
   msort = treefold merge [] . map (:[]) 
    
   merge:: Ord a => [a] -> [a] -> [a] 
   merge [] b = b 
   merge a [] = a 
   merge (a:a's) (b:b's) 
        | a < b = a: merge a's (b:b's) 
        | otherwise = b: merge (a:a's) b's 
    
   为了进行检验, 在源文件最开始加入: 
    
   import Random 
   gen=mkStdGen 60 
   lst=take 100 (randomRs (1,100) gen ::[Int])   
    
   生成一个包含100个随机数的数列lst.      
    
    
十一. 排列组合 

   排列是把数列的元素的所有可能的排列次序都找出来. 
    
   perms :: [a] -> [[a]] 
   perms [] = [ [] ] 
   perms (x:xs) = concat (map (between x) (perms xs)) 
       where between e [] = [ [e] ] 
             between e (y:ys) = (e:y:ys) : map (y:) (between e ys)   
              
   组合是从数列中取若干个元素所有可能的取法. 
                                                                                    
   combs :: Int -> [a] -> [[a]] 
   combs 0 xs = [ [] ] 
   combs (n+1) [] = [ ] 
   combs (n+1) (x:xs) = map (x:) (combs n xs) ++ combs (n+1) xs 
    
   这两个算法都是从书上找的. 以下的程序是我自己写的: 
    
   maps :: [a->b]-> a -> 
   maps [] x = [] 
   maps (f:fs) x = f x : maps fs x 
    
   split :: Int -> [a] -> ([a],[a]) 
   split 0 ls = ([],ls) 
   split _ [] = ([],[]) 
   split n (x:xs) = (x:xl,xr) 
      where (xl,xr)=split (n-1) xs    
    
   perm :: [a]->[[a]] 
   perm [] = [[]] 
   perm lst = concat $ maps fs lst 
      where fs = map f [0..length lst-1] 
            f i lst = map (x:) (perm (xl++xs) ) 
                where (xl,xr)=split i lst 
                      (x:xs)=xr 
                       
                       
   maps和map的定义非常类似, 执行类似其他语言中for循环的功能, 而until执行while循环的功能. 
    
   split将数列分成两个部分, 前半部分包括n个元素, 后半部分为剩余的元素. 
    
   perm计算的效率虽不太高, 但是 
    
   perm [1,2,3] 
    
   输出的结果为:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] 
   跟自己手工排的结果是一样的. 而 
    
   perms [1,2,3] 
    
   输出的结果为:[[1,2,3],[2,1,3],[2,3,1],[1,3,2],[3,1,2],[3,2,1]] 
   看起来有点乱. 
    
   后来对perm改进得: 
    
   sp xl [x] = [(xl,x,[])]   
   sp xl (x:xr) = (xl,x,xr):sp (xl++[x]) xr 
    
                       
   perm' [x]=[[x]] 
   perm' ls= [x:xs|(xl,x,xr)<-sp [] ls, xs<-perm'(xl++xr) ]   
    
   perm'同perm所用的算法和思路是一样的, 但效率已大大提高了. 
    
                        
                       
                       
十二. 运算符 

   定义一个运算符, 要说明它的结合性和优先级. 
    
   infixr 右结合 
   infixl 左结合 
   infix  不结合 
    
   左右都可结合的运算符如 +, * 定义为左结合即可. 
   优先级从0到9, 0最低, 9最高 
    
   已定义的运算符有: 
    
   level 9 . and !! 
   level 8 ^ 
   level 7 *, /, `div`, `rem` and `mod` 
   level 6 + and - 
   level 5 :, ++ and \ 
   level 4 ==, /=,<, <=, >, >=, `elem` and `notElem` 
   level 3 && 
   level 2 || 
   level 1 (not used in the prelude) 
    
   举例:     
                            
   infixr 3  &&                        
   (&&)  :: Bool -> Bool -> Bool 
   False && x   = False 
   True  && x   = x          

   先定义&&的结合性和优先级, 然后象定义函数一样定义它的功能. 
    
   运算符用括号括起来, 可以当作函数使用, 比如: 
    
   map (3+) [1,2,3] 
    
   map (+3) [1,2,3] 
    
   函数名用左引号`引起来, 也可以声明为运算符, 比如: 
    
   fac n = product [1..n] 
                      
   infix 5 !^!, `choose` 
   (!^!), choose :: Int->Int->Int                    
   n `choose` k = fac n `div` (fac k * fac (n-k)) 
   n !^! k = fac n `div` (fac k * fac (n-k))      
    
   有了这些定义后, 
    
   choose 5 2 
   (!^!)  5 2 
   5   !^!  2 
   5 `choose` 2 
    
   都给出答案10.   
    
    
十三. 复合函数 


   当一个函数的返回值的类型与另一个函数输入值的类型相同时, 这两个函数就可以复合. 在Haskell中两个函数复合用运算符(.)表示. 举几个例子: 
    
   f x = (x,2) 
   g (x,y)=(x+y)*(x-y) 
   h = g.f 
    
   sumaux []=[] 
   sumaux (x:xs)=x+sum xs : sumaux xs 
   sums =reverse.sumaux.reverse 
    
   函数复合也可以使用匿名函数, 比如: 
    
   foo=not.(\x->even x && x<100) 
    
   复合运算满足结合律: 
    
   f . (g . h) = (f . g) . h 
    
   下面看几个定理: 
    
   (map f . map g) xs = map (f.g) xs 即 map f . map g = map (f.g) 
    
   map f (xs++ys) = map f xs ++ map f ys 
    
   map f . concat = concat . map (map f) 
    
   map f . (x:) = (f x :) . map f 
    
   map f xs = foldr g [] ys where g x ys = f x : ys 
    
   concat xss = fold (++) [] xss 
    
   length . combs k = ( `choose` k) . length 
    
   sum (xs++ys) = sum xs + sum ys 
    
    
   这些定理都不难理解, 也很容易证明. 你也可以自己证明一些其他的定理. 

        
十四. 小结 

   从前面各节的标题来看, Haskell根本就是在搞数学, 不象是在编程. 其实这正体现了Haskell的一个突出的优点, 它对各种数学概念提供了完美的支持, 我说Haskell是数学家的乐园. 数学是一个基础, 我认为把数学做好的编程语言才有潜力把其他事情做好. 
    
   你在作数学题的时候, 从来也没有过把变量看作是存储器, 给变量赋值的概念, 也没有用到for,while循环语句, 而在Haskell中正好抛弃了这些概念. 用Haskell解决问题的思路与人思路非常接近, 比如相当一部分函数以数学归纳法的方式来定义, 对数据的描述性的定义等. 它掩盖了非常细节的问题, 在更高的层次上处理问题. 这样就提高了编程的效率, 提高了代码的可重用性. 
    
   Haskell是世界上公认的语法最优美最简洁的一种语言。Haskell语言是写给人看的，而不是写给机器看的。另一方面，这也使得的 Haskell的编译技术成为一个难点, 编译后的程序运行速度比C略慢一些。从以人为本的角度来看，程序员的时间比机器的时间更宝贵，所以Haskell是明智的选择。    
    
   以后各节将更多关注于Haskell编程方面的一些特性, 而不仅仅是做算术. Haskell的高效和强大将得到进一步的证实. 由于Haskell主要是在UNIX平台上发展起来的, 专门针对Windows的类库不是很多. 但Haskell的先进性是不容置疑的, 它的发展只是一个时间的问题. 
    
   我希望你们已经意识到为什么要学函数编程语言, 欢迎来到精彩的Haskell世界--一个更好的地方. 
    
    
十五. 输入输出 


   1.输出字符串: putChar, putStr, putStrLn, print, 
     输入字符串: getChar, getLine, getContents, interact, 
      
   2.文件操作: readFile, writeFile, appendFile, readIO, readLn   
    
        
GHC使用指南 

GHC可以把Haskell程序编译为可执行文件. 操作方法如下: 

1.到http://www.haskell.org/ghc/下载并安装GHC. 
2.用cmd打开一个命令窗口. 
3.输入ghc --make file.hs 回车. 
ghc为编译器, 必要时给出ghc.exe文件所在的目录, file.hs为被编译的文件, 必要时也 
给出它的目录. 
file.hs文件中要包含一个函数名为main的函数,运行可执行文件时这个函数被执行. 
4.输出文件的文件名为a.out, 将后缀名改为exe, 就可以运行了. 
5. 使用ghc -o foo file.hs 可以指定输出文件名, 在此例中将得到foo.exe 
  使用ghc -O file.hs     可以优化编译输出 
6. 当源程序中使用了某个或多个package时,使用 
       ghc -package p_name1 -package p_name2 --make file.hs 
  加载所需的包. 
7. 使用ghc --interactive 可以打开ghci, 在ghci中使用:set -package name 加载包 

- 作者： yeqiwei 访问统计：161　2005年09月23日, 星期五 11:00 加入博采