Haskell 中沒有 for 和 while 循環(huán)，而使用遞歸解決循環(huán)問題。

所謂遞歸，就是將一個(gè)大問題分解為兩部分

• 先取出容易解決的一小部分進(jìn)行處理
• 剩余部分作為同樣的問題處理，但是規(guī)模變小了一點(diǎn)
• 問題的規(guī)模越來越小，直到遇到退出條件

這里的重點(diǎn)是，將剩余部分作為同樣問題處理的時(shí)候，在語義上我們認(rèn)為他已經(jīng)解決了，可以將其當(dāng)做一個(gè)確定的值參與到運(yùn)算中

實(shí)作 Maximum

遞歸配合模式匹配和解構(gòu)，非常容易實(shí)現(xiàn)

• 第一個(gè)模式是錯(cuò)誤參數(shù)
• 第二個(gè)模式是退出條件
• 第三個(gè)模式將問題進(jìn)行了分解

maximum' :: (Ord a) => [a] -> a  
maximum' [] = error "maximum of empty list"  
maximum' [x] = x  
maximum' (x:xs)   
    | x > maxTail = x  
    | otherwise = maxTail  
    where maxTail = maximum' xs

上面的代碼用 where 定義了一個(gè)局部函數(shù)來比較當(dāng)前值和剩余部分的大小，使用 max 函數(shù)可以進(jìn)一步簡(jiǎn)化代碼。

這里可以看出： max 函數(shù)將剩余問題當(dāng)做了一個(gè)值參與了運(yùn)算

maximum' :: (Ord a) => [a] -> a  
maximum' [] = error "maximum of empty list"  
maximum' [x] = x  
maximum' (x:xs) = max x (maximum' xs)

幾個(gè)常用遞歸函數(shù)

replicate

返回一個(gè)包含多個(gè)重復(fù)元素的列表, 如 replicate 3 5 回傳 [5,5,5]

同樣可以看到：剩余部分的遞歸同樣被當(dāng)做了一個(gè)值傳遞給了 : 函數(shù)參與運(yùn)算

replicate' :: (Num i, Ord i) => i -> a -> [a]  
replicate' n x  
    | n <= 0    = []  
    | otherwise = x:replicate' (n-1) x

take 函數(shù)

從一個(gè)列表中取出一定數(shù)量的元素。 如 take 3 [5,4,3,2,1], 得 [5,4,3]

take' :: (Num i, Ord i) => i -> [a] -> [a]  
take' n _  
    | n <= 0   = []  
take' _ []     = []  
take' n (x:xs) = x : take' (n-1) xs

reverse 函數(shù)

反轉(zhuǎn)一個(gè) List

reverse' :: [a] -> [a]  
reverse' [] = []  
reverse' (x:xs) = reverse' xs ++ [x]

repeat 函數(shù)

取一個(gè)元素作參數(shù), 回傳一個(gè)僅包含該元素的無限 List

repeat' :: a -> [a]  
repeat' x = x:repeat' x

zip 函數(shù)

取兩個(gè) List 作參數(shù)，將他們組合成一個(gè)序?qū)Φ牧斜怼?code>zip [1,2,3] [2,3] 回傳 [(1,2),(2,3)]

• 它會(huì)把較長(zhǎng)的 List 從中間斷開, 以匹配較短的 List
• 用 zip 處理一個(gè) List 與空 List 會(huì)得一個(gè)空 List，這是退出條件

zip' :: [a] -> [b] -> [(a,b)]  
zip' _ [] = []  
zip' [] _ = []  
zip' (x:xs) (y:ys) = (x,y):zip' xs ys

elem 函數(shù)

它檢測(cè)一個(gè)元素是否在一個(gè) List 中

elem' :: (Eq a) => a -> [a] -> Bool  
elem' a [] = False  
elem' a (x:xs)  
    | a == x    = True  
    | otherwise = a `elem'` xs

快速排序

快速排序是一個(gè)經(jīng)典排序算法，非常快，其算法描述也非?！斑f歸”

算法描述：

• 取出頭部項(xiàng)（已解決的一小部分）
• 將所有小于等于頭的項(xiàng)放在一組，并將其快速排序（即作為剩余問題解決）
• 將所有大于頭的項(xiàng)放在一組，并將其快速排序（即作為剩余問題解決）
• 將小組、頭、大組組合起來即可（即將各個(gè)部分看做已解決的值參與運(yùn)算）

quicksort :: (Ord a) => [a] -> [a]  
quicksort [] = []  
quicksort (x:xs) =  
  let smallerSorted = quicksort [a | a <- xs, a <= x] 
      biggerSorted = quicksort [a | a <- xs, a > x]  
  in smallerSorted ++ [x] ++ biggerSorted