Haskell的遞歸

遞歸是Haskell中極其重要的一環，輔以模式匹配、Guards、List Comprehension、Let、Lambads等，可以高效寫出舒適的Haskell遞歸程序來。

看到《Haskell趣學指南》 的「遞歸」章節，先不看書中實現，自己根據題目要求先把這些遞歸功能寫一遍，因此，可能跟書中代碼有所不同。閑話不說，上代碼才是最實惠的：

-- 實現maximum函數。n-- 取一組可排序的List（屬於Ord Typeclass）做參數，並回傳其中的最大值。nmaximum :: (Ord a) => [a] -> anmaximum [] = error "Invalid, empty list..."nmaximum [x] = xnmaximum (x:xs)n | x > maxValue = xn | otherwise = maxValuen where maxValue = maximum xsnn-- 實現下replicate函數。n-- 它取一個Int值和一個元素做參數，回傳一個包含多個重複元素的List，n-- 如：replicate 3 5回傳[5,5,5]。nreplicate :: Int -> a -> [a]nreplicate n xn | n <= 0 = []n | otherwise = x : replicate (n - 1) xnn-- 實現take函數。n-- 它可以從一個List取出一定數量的元素，如：take 3 [5,4,3,2,1]，得[5,4,3]。ntake :: Int -> [a] -> [a]ntake _ [] = []ntake n (x:xs)n | n <= 0 = []n | otherwise = x : take (n - 1) xsnn-- 實現reverse函數。函數簡單地反轉一個List。nreverse :: [a] -> [a]nreverse [] = []nreverse (x:xs) = reverse xs ++ [x]nn-- repeat函數取一個元素作參數, 回傳一個僅包含該元素的無限List。nrepeat :: a -> [a]nrepeat x = x : repeat xnn-- 實現zip函數。n-- 取兩個List作參數並將其捆在一起。如：zip [1,2,3] [2,3] 回傳 [(1,2),(2,3)]。nzip :: [a] -> [b] -> [(a, b)]nzip [] _ = []nzip _ [] = []nzip (x:xs) (y:ys) = (x, y) : zip xs ysnn-- 實現函數elem。它取一個元素、一個List作參數, 並檢測該元素是否包含於此List。返回True或False。nelem :: (Eq a) => a -> [a] -> Boolnelem _ [] = Falsenelem e (x:xs)n | e == x = Truen | otherwise = e `elem` xsn

在ghci中運行看看Haskell有多Geek吧！

Prelude> :l hello2.hsn*Main> maximum [1, 300, 57, 89, 98]n300 n*Main> replicate 8 9n[9,9,9,9,9,9,9,9]n*Main> take 5 "Hi"n"Hi"n*Main> take 5 "Hello, World!"n"Hello"n*Main> reverse "Hello!"n"!olleH"n*Main> repeat 8n[8,8,8,8,8,8,8,8,...] -- 無限循環了{{{(>_< )}}} n*Main> zip [1, 2, 3] ["Haha", "{{{(>_< )}}}"]n[(1,"Haha"),(2,"{{{(>_< )}}}")]n*Main> l `elem` "Hello, World!"nTruen

另外，常用到在字元串或列表中查找給定值的位置，趁熱打鐵來實現一個：

-- lookup，找出列表中所有指定值，並給出其下標。nlookup :: (Eq a) => a -> [a] -> [Int]nlookup _ [] = []nlookup e xs =n let z = zip [0..] xsn in [x | (x, y) <- z, y == e]n

運行結果：

*Main> lookup l "Hello, World!"n[2,3,10]n*Main> lookup 10 [1, 11, 10, 20 ,30 ,10 ,60,80, 90, 1000]n[2,5]n

嗯，還有快排，我用到了filter函數，Haskell的表述能力超強，真的非常簡潔：

-- quicksort：快排函數。n-- 所有小於等於頭部的元素在先(它們已排過序), 後跟大於頭部的元素(它們同樣排過序)。nquicksort :: (Ord a) => [a] -> [a]nquicksort [] = []nquicksort (x:xs) =n let front = quicksort (filter (<= x) xs)n end = quicksort (filter (> x) xs)n in front ++ [x] ++ endn

運行結果：

*Main> quicksort [6, 4, 5, 6, 20, 7, 8, 9, 9, 10, 13, 11, 12]n[4,5,6,6,7,8,9,9,10,11,12,13,20]n

如果想在快排的同時也把重複的值剔除該怎麼做呢？很簡單，把小於等於改為小於就好：

-- quicksort：快排函數，但是剔除重複值。nquicksort :: (Ord a) => [a] -> [a]nquicksort [] = []nquicksort (x:xs) =n let front = quicksort (filter (< x) xs)n end = quicksort (filter (> x) xs)n in front ++ [x] ++ endn

運行結果：

*Main> quicksort [6, 4, 5, 6, 20, 7, 8, 9, 9, 10, 13, 11, 12]n[4,5,6,7,8,9,10,11,12,13,20]n

Haskell用起來的感覺真的非常好，但要掌握好也極具挑戰性。作為自己的愛好技術，非常合適。但要在項目中應用，確實還不太切合實際。

最後贊一下Sublime Text，寫Haskell程序非常舒適。比如，我只這麼一選，就可以一次性地給quicksort函數名統一添加『單引號：

推薦閱讀：