haskell教程.txt

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

   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