Haskell教程 (转载)

by rufi  2003.3.21 -- 2003.4.2

一.序

1．什么是Haskell?

     Haskell是一种函数编程语言. 1980年代以前对函数编程有很多研究, 但不同的研究者使用各自不同的语法记号, 一起交流时造成一些不便. 后来1987年的时候, 在FPCA'87会议上制定了统一的Haskell语言. Haskell吸收了各家的长处, 是一种纯粹的函数编程语言,并根据科学家Haskell B.Curry的名字命名. Haskell经过多年的发展完善, 目前使用的版本是Haskell 98.
     
2．Haskell有什么特点?

    相对Haskell来说,传统的Basic,Pascal,C++,C#,Java,Python等都是命令(imperative)编程语言, 程序语句有一定的执行次序. 函数(functional)编程语言则给出执行的内容, 关注于更高层次的"做什么"而不是"怎么做", 这就是二者最明显的一个区别。函数编程语言的语法功能非常强，使编程的效率大幅提高。
    Haskell是世界上公认的语法最优美最简洁的一种语言。的确，Haskell语言是写给人看的，而不是写给机器看的。另一方面，这也使得的Haskell的编译技术成为一个难点。从以人为本的角度来看，程序员的时间比机器的时间更宝贵，所以Haskell是明智的选择。

3．如何获得Haskell?

     Haskell是一个公共的语言定义, 任何人都可以编写它的实现(implementation), 因而Haskell有很多解释器(比如Hugs)和编译器(比如GHC), 它们都可以在www.haskell.org上得到. 解释器的优点是便于学习和开发,程序写好后不需要编译直接就可以运行,编译器则可以将程序编译可独立执行的文件,便于发布. Haskell既能解释执行, 也能槐槐嘁? 这也是优于其他语言的一个地方.

附：Hugs使用指南

    本文中的示例程序都将在Hugs中运行, 在这里简要介绍一下Hugs的使用方法。Hugs可以在http://www.haskell.org/hugs/下载，安装文件只有2.8M， 是学Haskell的必备工具.

使用方法:

1.用你自己喜欢的文本编辑器将源程序写好, 保存到文件中, 文件以扩展名 hs 结尾.

2.运行Hugs, 出现提示符: Prelude> ,表示Prelude库已经装载.

3.输入:? 可以查看可供使用的一些命令的说明

4. 先输入:!, 然后就可以输入DOS命令并执行. 比如输入:!dir查看当前的工作目录

5. 输入:cd directory_name 将工作目录改为你保存源文件的目录

6. 输入:l file_name 将源程序载入, 提示符变为Main>

现在就可以在提示符后输入各种表达式以检验所定义的函数的功能, 执行所需的运算.

注意: 在提示符后不可以定义新的函数, 因为Haskell中各语句不是顺序执行的, 而把整个源文件当作一个整体来处理, 在编辑器中修改源程序并保存后, 只要输入:r就重新载入, 改动就生效了.


二.语法概要

1.注释有两种: 一种以"--"开始到行尾结束, 一种以"{-"开始,以"-}"结束,可以延续多行.

2.表达式和函数都有类型,但类型声明不是必需的,有一套类型推断系统可以推断出所涉及的类型.

3.函数的定义多使用模式(pattern)匹配的方法, 两个标识符(identifier)邻接就表示函数调用.

4.函数变量和类型变量的标识符以小写字母开头, 类型构造和模块的标识符以大写字母开头.

5.语句块以缩进区分, 从同一列开始的语句属于同一个块.

6.保留字: case class data default deriving do else if import in infix infixl infixr instance let module newtype of then type where _

7.运算符可以自定义,由以下符号进行组合:
       : # $ % & * + - = . / \ < > ? ! @ ^ |
 预定义的运算符有:
       +  -  *  /  ^  $  ++  .  &&  ||  ==  /= <=  >=  <  >
       : //  =  @  ->  =>  ..  ::  <-  !!
       
8.数字: 123  12.3  1.23e5  0o67  0x3A

 字符: 'a' 'A' '\n'
 
 字符串: "character string"
 
 
三.常数

    在函数编程语言中, 函数是一个中心概念, 常数也可看作是常函数. 如下语句:
    
     f = 3
     
    定义了一个常数. f 被定义为3后就不能重复定义 f=5 ,任何时候调用f, 它都返回3. 这就消除了一些边际效应,减少了出错的可能性. 以下代码在函数编程和命令编程中具有完全不同的含义:
    
    a = 2
    b = 4
    c = a + b
    
    在函数编程中解释为: 定义常数a为2, 定义b为4, 定义c为a,b之和.  
    在命令编程中解释为: 给变量a赋值2, 给b赋值4, 求a,b之和赋给c.
    
    定义和赋值的区别在于, 定义不分次序, 赋值有次序, 以上程序在Haskell中完全可以倒过来写:
    
    c = a + b
    a = 2
    b = 4
    
    另外, 定义并不计算, 比如:
    
    d = 3*5
    e = 1/0
    
    在命令程序中, e=1/0会引发一个错误, 在Haskell中只有当计算e时才引发错误.
    
    Haskell的思维更像是人脑的思维而不是机器的思维.
    
    也可以给常数加以类型说明, 比如:
    
    b :: Int
    
    如果没有这一类型说明, 系统自动根据 b=4 推断b的类型为: Integer
    
    Int和Integer区别是Int的取值范围是有限的, Integer的大小是无限的. 因为Integer比Int更普遍,所以在没有明显说明b的类型为Int时, 就自动推断b的类型为: Integer
    
    再举几个例子,在Haskell标准库Prelude中定义的常数中,有两个是:
    
    pi = 4 * atan 1
    otherwise = True
    
    
四.单变量函数
    
    如下语句:
    
    f     (x)=x+2
    double(x)=2*x
    
    就定义了两个简单的函数, 函数的类型由自变量的类型和返回值在类型决定, 用运算符"->"连接.
    
    比如可以用以下语句说明它们的类型:
    
    f      :: Int -> Int
    double :: Float -> Float
    
    表示f是从Int变量到Int变量的映射. 如果没有明显说明, 系统根据函数定义中所涉及到的运算(+),(*)推断这两个函数的类型为:    
    
    Num a => a -> a
  
    这里a是一个类型变量, 属于一个独立的名字空间, Num是一个类, Num a => 表示类型a属于Num类. Num类中定义了(+)和(*)的运算, 继承此类的类型也支持这两种运算. 这样使用类来限定函数的类型, 使函数具有的普遍性. 把类型归为一些类, 实现了类型的多态, 也简化了编程的任务.
    
    在Haskell中函数非常频繁地用到, 通常在函数的定义和使用中省去括号, 直接用两个标识符邻接表示函数作用. 所以f和double的定义可写为:
    
    f x      = x + 2
    double x = 2 * x
    
    调用函数的格式和定义函数的格式基本是相同的, 比如定义函数g如下:
    
    g x = 2 * f x
    
    函数作用的优先极高于其他所有的运算符, 所以2 * f x等价于2 * (f x), 也等价于2 * (f(x)).
    
    函数作用的次序是从左向右的, 所以可以等价地定义g为:
    
    g x = double (f x)
    
    Prelude有一个运算符$的定义如下:
    infixr 0  $
    ($)            :: (a -> b) -> a -> b
    f $ x           = f x
    
    可见, $也是表示函数作用的, 但它的优先级最低, 而且作用次序是从右向左的.所以还可以等价地定义g为:
    
    g x = double $ f x
    
    引入$, 避免了括号的使用, 尤其当$后的表达式很长有多行时使用$是很方便的.
    
    
五. 多变量函数


  严格说来, 一个函数只能接收一个参数, 返回一个值. 但有两种方法可以实现多变量函数.
  
  1.Curried函数
  
  函数接受一个参数后, 返回的也是一个函数, 这个函数对可以接受别的参数. 比如:
  
  add :: Int -> Int -> Int
  add x y = x + y
  
  从add类型可以看出, 有两个"->", 而"->"的结合次序是从右向左, 所以add的类型是:
  
  Int -> ( Int -> Int )
  
  即add接受一个Int参数, 返回一个( Int -> Int )的函数, 这个函数再接受一个Int返回一个Int.
  
  这样的函数就叫curried函数.
  
  2.使用数组
  
  数组就是把几个变量放到一起看成是一个变量, 从而使函数可以输入和输出多个变量. 比如:
  
  add :: (Int,Int) -> Int
  add (x,y) = x+y
  
  数组是Haskell中的一种数据结构, 数组中可以放不同类型的变量, 数目不限但长度固定, 数组的类型就是数组内各元素的类型组合起来构成一种类型.
  
  这两种函数在使用中各有特色, 而且可以用Prelude中定义的curry和uncurry互相转换.
  
  curry          :: ((a,b) -> c) -> (a -> b -> c)
  curry f x y     = f (x,y)

  uncurry        :: (a -> b -> c) -> ((a,b) -> c)
  uncurry f p     = f (fst p) (snd p)
  
  稍作一点解释:类型说明中出现的小写a,b,c等叫类型变量, 表示任意一种类型. f (x,y)表示f接受数组为参数, curry f x y就是(curry f) x y 表示curry f可以接受两个变量为参数. 令 g=curry f, 则 g x y = f (x,y). 可见curry的转换作用, curry的类型表达更清楚和说明了这一点. uncurry也是一样的道理, 其中的fst和snd分别表示取二元数组的第一个和第二个元素.定义如下:
  
   fst            :: (a,b) -> a
   fst (x,_)       = x
   
   snd            :: (a,b) -> b
   snd (_,y)       = y
   
   "_"叫匿名变量, 匹配指定类型任意的输入值, 该值在"="后的表达式中不会用到.
  
    
六. 离散函数
  
   有些函数的参变量只有有限个取值, 比如Prelude中not的定义如下:
   
   not         :: Bool -> Bool
   not True     = False
   not False    = True
   
   not对逻辑变量取反.

   离散的变量可以使用保留字data定义, 比如:
   
   data Direction = Left|Up|Right|Down
   
   这就定义了一种Direction类型的变量, 这种变量的取值只有四个值:Left,Up,Right,Down.
   
   data定义了一个新的类型, type则可以给一个已有的类型取一个别名.比如:
   
   type Point = (Float, Float)
   
   (Float, Float)是容纳两个Float变量的数组的类型, 取别名后既简化了书写, 也附加了含义.
   
   现在看针对离散变量的函数如何定义:
   
   move :: Direction -> Point -> Point
   move Left  (x,y) = (x-1,y)        
   move Up    (x,y) = (x,y-1)
   move Right (x,y) = (x+1,y)
   move Down  (x,y) = (x,y+1)
   
   即分别对应离散变量的每一个取值对函数作相应的定义. 以(x,y)表示位置, 给move输入移动的方向和当前的位置, 就输出了移动后的位置.
   
   再看一个例子:
   
   data Thing = Paper | Stone | Scissors   deriving Show

   beat :: Thing -> Thing
   beat Paper    = Scissors
   beat Stone    = Paper
   beat Scissors = Stone
   
   定义Thing类型有三个取值, deriving Show表示Thing类型继承Show类, 从而拥有的Show的method, Show类的作用是将取值转化为字符串在屏幕上显示. beat定义了三种物品,纸,石头,剪刀之间的输赢关系.
 

   自然数是离散的也是无限的, 以自然数为变量的函数通常用迭代的方法定义, 即函数自己调用自己.举个例子:
   
   fac 0 = 1
   fac n = n * fac (n-1)
   
   这样计算fac n时, 先去计算fac (n-1),有fac n = n * fac (n-1)=n * (n-1) * fac (n-2),如此类推, 一直算到fac 0, 最后的结果是把从1到n的自然数全部连乘起来.
   
   再比如:     
   increment,fib :: Int -> Int
   
   increment x=x+1
   
   fib 1 = 1
   fib 2 = 2
   fib n = fib (n-1) + fib (n-2)
   
   当计算函数时, 按照输入的参数逐一匹配所给的模式, 如果无法匹配时给出错误中断. 对于自然数模式匹配还允许用如下方式定义函数:
   foo (n+1) = n-1
   
   Haskell中预定义的针对字符的函数有:
   isAscii, isLatin1, isControl, isPrint, isSpace, isUpper, isLower,
   isAlpha, isDigit, isOctDigit, isHexDigit, isAlphaNum,
   digitToInt, intToDigit,
   toUpper, toLower,
   ord, chr,等
   
   ord将字母转换为数字, chr反之.
   
   
   
七. 连续函数


   Haskell中整数可以用Int和Integer表示, 实数可以用Float(单精度)和Double(双精度)来表示. 有理数还可用Rational表示, 相当于无限精度的浮点数.
   Prelude中定义了两个在数学上较基本的函数:
   
   1. 常数函数
   
   const          :: a -> b -> a
   const k _       = k
   
   2. 单位函数
   
   id             :: a -> a
   id    x         = x
   
   当函数针对变量的不同取值范围有不同的行为时, 就要用到选择结构. 比如:
   
   3. 绝对值函数
   abs' x = if x>=0 then x else -x    
   
   if ... then ... else ...的结构也可以用"|"(guard)来表达, 上述abs'也可写成:
   
   abs' x |x>=0      = x
          |otherwise = -x  
   
   "|"还可用于更多的分支选择, 比如:
   4. 符号函数
   
   sign x |x>0  = 1
          |x==0 = 0
          |x<0  = -1
          
   绝对值函数和符号函数在Prelude中分别为abs和signum, 其定义是用prime函数实现的.
   下面再举几例子,以熟悉函数的定义方法.                
   
   5. 二次方程求根函数:
   
   root (a,b,c) = (x1,x2) where        
       x1=(-b+d)/(2*a)
       x2=(-b-d)/(2*a)
       dd = b*b-4*a*c
       d | dd>=0 =sqrt dd
         | dd<0  =error "No real root"
   这里where引入一个内嵌的语句块, 在其中定义的函数在外部是看不到的. error函数用来提示出错的信息.
   
   6. 求导函数
   
   diff :: (Float->Float) -> (Float->Float)
   diff f = f’
      where f’ x = (f (x+h) - f x) / h
            h = 0.0001
  为了h的取值可调, 也可以把h包括在参数中:
   flexDiff h f x = (f(x+h)-f(x))/h
    
  把flexDiff h sin 1的取值和cos 1的取值在h=0.001,0.0001,0.00001下比较, 取0.0001的接近程度最好.
  
  7. 方程求根
  利用牛顿法可定义函数为:
  zero :: (Float->Float) -> Float
  zero f = until goodEnough improve 1.0
       where improve b = b - f b / diff f b
             goodEnough b = f b ~= 0.0
             
  其中until是Prelude中定义的执行循环的一个函数, 其定义如下:
  
  until          :: (a -> Bool) -> (a -> a) -> a -> a
  until p f x    = if p x then x else until p f (f x)
  
  until的作用是看条件p x是否成立, 不成立就用f作用x, 返回值替代原来的x, 直到条件p x成立为止.
     
  表示约等于的运算符~=则需要自己定义.
  
  8. 求逆函数
  利用方程求根的结果就可以求逆:
  inverse :: (Float->Float) -> Float -> Float
  inverse g a = zero f
      where f x = g x - a    
      
      
八. 数列和数组

   数列中元素的类型一致, 元素数目可变; 数组中元素的类型任意, 元素数目固定. 可以说数列和数组对数据的抽象做到了性能与灵活性的恰到好处, 有些语言中只提供一种容器, 元素数目可变, 类型也任意, 其结果是无法满足类型完全的需要, 也将低了运算的效率.
   
   数组的使用比较简单, 对于数列来说则大有文章.
   
   1. 数列的构造
   
   数列是用[]和(:)构造的, []是一个空的数列, x:xs的含义是元素x附加到数列xs的前面组成一个更长的数列. 比如, 1:[] 等于[1], 2:3:1:[]等于[2,3,1], 运算符(:)是从右向左运算的. 所有的数列都可以看作是从[]开始, 将各元素用(:)附到上面形成的. 在实际编程中有一些简记法可以快速地构造数列.
   
   a. 列举法
   
   将数列的元素一一列举, 比如: [1,2,3], ['A','B','d'], [[1,2], [4,5,6]]等等, 数列的类型用"[元素类型]"来表示, 这几个例子的类型依次为: [Int], [Char], [[Int]].
   
   b. 给出变化范围
   
   适用于构造等差数列, 比如: [1..5]等于[1,2,3,4,5], ['a'..'d']等于['a','b','c','d']等于"abcd"因为type String=[Char]. 默认的等差为1, 也可以给出前两个元素指定等差, 比如: [2,4..8]等于[2,4,6,8], [2,4..7]等于[2,4,6], [2.5,4..9.5]等于[2.5,4.0,5.5,7.0,8.5,10.0].
   
   c. 描述法
   
   描述法给出数列中元素取值的范围以及所满足的条件, 与数学中集合的描述法是一样的. 例如:
   
   [3*x+2| x<-[3,6,9]] --记号"<-"表示属于,x依次取3,6,9,代入3*x+2,得到数列[11,20,29]
   [x*x| x<-[1..9], x `rem` 3==1] --给出x的范围,还限定x除3余1
   [(x,y)|x<-[1,2,3],y<-[x..3]] --等于 [(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)]
   
   2. 从数列中选取元素
   
   head --数列的第一个元素
   tail --除去第一个元素剩余的数列
   last --最后一个元素
   init --除去最后一个元素剩余的数列
   take n --数列前n个元素
   drop n --除去数列前n个元素剩余的数列
   (!!)n  --第n个元素, 索引指标从0开始
   
   3. 从数列中筛选元素
   
   filter p    --把数列中所有满足条件p的元素取出来组成一个数列
   takeWhile p --从第0个元素起, 取满足p的元素, 遇到不满足条件的元素时停止
   dropWhile p --从第0个元素起, 去掉满足p的元素, 遇到不满足条件的元素时停止
   
   条件p是一个以数列元素为自变量, 返回值为逻辑值的函数. 比如预定义的even,odd判断奇偶性.
   
   4. 常用数列函数
   
   length lst --求数列的元素数目
   reverse lst --将数列中元素次序反过来
   lst1 ++ lst2 --将两个数列连成一个数列
   concat lst  --lst是数列的数列,concat将各子数列一个数列
   
   sum lst  --对lst中的元素求和
   product lst  --lst中的元素连乘
   elem e lst --判断e是否为lst中的元素
   
   or lst    --对类型为[Bool]的lst中所有元素求或
   and lst   --对类型为[Bool]的lst中所有元素求与
   
   zip
   
   5. 高阶函数
   
   map f lst --将lst按照函数f映射得到一个新的数列
   map :: (a->b) -> [a] ->
   map f [] = []
   map f (x:xs) = f x : map f xs
   
   foldr,foldl --给定一种运算和一个初值,将初值和数列中所有元素由此运算连起来计算
   foldr :: (a->b->b) -> b -> [a] -> b
   foldr op e [] = e
   foldr op e (x:xs) = x ‘op‘ foldr op e xs
   
   foldl op e [] = e
   foldl op e (x:xs) = foldl op (e‘op‘x) xs      
   
   示例:
   
   rate   :: [Float]->[Float]                  
   rate ls = map (/s) ls where s=sum ls   
   
   --(/s)是将运算符"/"偏参化,并括起来当作函数使用   
   
   numDigits [] = 0
   numDigits (c:cs) = (if (c >= '0') && (c <= '9') then 1 else 0) + numDigits cs
   
   --典型的以模式匹配和迭代的方法定义数列函数, numDigits 计算字符串中数字的个数
   
   
九. 无限数列

   可以定义无限长的数列, 比如:
   from :: Int -> [Int]
   from n = n : from (n+1)
   
   from2 = from 2    
   
   from n得到的是一个从n开始的无限长的自然数列, 因为Haskell的lazy evaluate或non-strict的特性, 这个定义并不会引起无限次的计算. 对数列进行操作时, 有的函数要用到数列中所有的元素, 用这样的函数操作无限数列就会使计算机不停地计算, 直到内存或堆栈不够用为止; 而有的函数只用到数列的一部分元素, 这时无限数列就派上用场了. 比如:
   
   take 5 from2 => [2,3,4,5,6]
   from2(!!)9   => 11
   takeWhile (\x->x*x<100) from2 => [2,3,4,5,6,7,8,9]
   
   这里用"=>"表示计算结果, (\x->x*x<100) 是一个匿名函数,即用这样的格式表达了函数的输入与输出却不用给函数起名字另行定义.
   
   上述from函数其实可以用给出数列元素变化范围的方法直接得到数列, 比如: [2..], [1,3..]
   Prelude中定义用于生成无限数列的函数还有:
   repeat :: a -> [a]
   repeat x = x : repeat x    --对元素a无限重复
   
   iterate :: (a->a) -> a -> [a]
   iterate f x = x : iterate f (f x)
   {-
   iterate (+1) 3 is [3, 4, 5, 6, 7, 8, . . .
   iterate (*2) 1 is [1, 2, 4, 8, 16, 32, . . .
   iterate (/10) 5678 is [5678, 567, 56, 5, 0, 0, . . .
   -}
   下面再举几个无限数列的应用的例子:
   
   squares = [ x*x | x<-[0..]]
   isSquare n = elem n (takeWhile (<=n) squares)   --判断一个数是否为平方数
   
   fibs = fibgen 1 1   --Fibonacci 数列
   fibgen n1 n2 = n1 : fibgen n2 (n1+n2)
   
   primes = map head (iterate crossout [2..])      --用筛法求素数  
    where  crossout (x:xs)=filter (not.divisible x) xs
           divisible x y = y `rem` x == 0
   
  prime = sieve [2..]         ---改进后的素数数列
  sieve (x:xs) = x : sieve (filter (\y ->y `rem` x /= 0) xs)
  
  有了这些定义后, take 100 prime 就是取前100个素数, prime(!!)1000 就是取第1000个素数, 因为数列的定义是无限的, 数列的计算是有限, 这样就无须为不同的需要定义不同长度的数列, Hakell处理无限数列的能力实在是令人叹服.
  
  
十. 数列排序

    Qucik Sort是对数列元素快速排序的一种算法. 初次见到的版本是:
    
    qsort1 []     = []
    qsort1 (x:xs) = qsort1 elts_lt_x ++ [x] ++ qsort1 elts_greq_x
                where
                  elts_lt_x   = [y | y <- xs, y < x]
                  elts_greq_x = [y | y <- xs, y >= x]
                  
    后来又有人将其写为:
    
    qsort2 [] = []
    qsort2 (x:xs) = qsort2 less ++ [x] ++ qsort2 more
         where less = filter   (<x)  xs
               more = filter   (>=x) xs
 
    可以明显地看到在比较的过程中对数列扫描的两次, 所以我就想能不能扫描一次就把比x大的和比x小的分开, 这就是我的第一个实现这一想法的程序:
    
   qsort3 [] = []
   qsort3 (x:xs) = qsort3 xl ++ [x] ++ qsort3 xr
       where  (xl,xr,_) = until f g ([],[],xs)
              f (_,_,w)=w==[]
              g (l,g,y:ys) |y<=x =(y:l,g,ys)
                           |y> x =(l,y:g,ys)
                           
                           
    但这个程序的效率不高, 然后就逐渐改进:
    
   qsort4 []=[]
   qsort4 (x:xs)=qsort4 xl ++ [x] ++ qsort3 xr
          where (xl,xr)=split (<x) xs
                split f []=([],[])
                split f (y:ys) |f y  =(y:fst (split f ys),snd (split f ys))
                               |True =(fst (split f ys),y:snd (split f ys))    
                               
                                   
   qsort5 []=[]
   qsort5 (x:xs)=qsort5 xl ++ [x] ++ qsort5 xr
          where (xl,xr)=split (<x) xs
                split f []=([],[])
                split f (y:ys) |f y  =(y:l,r)
                               |True =(l,y:r)
                               where (l,r)=split f ys                                                            
                               
   qsort6 []=[]
   qsort6 (x:xs)=qsort6 xl ++ [x] ++ qsort6 xr
         where (xl,xr)=split x xs
               split _ [] = ([],[])
               split e (x:xs) | e>=x  = (x:l,r)
                              | e<x   = (l,x:r)
                              where (l,r) = split e xs
   
   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 加载包