Haskell 笔记 (五) 递归

haskell 递归

递归就是将问题展开为同样的子问题，并不断的对子问题展开，直到抵达问题的基准条件为止。

递归2个要点：

1. 问题如何展开为子问题
2. 定义基准条件

在程序上，问题的展开表现就是函数调用函数自己。基准条件就是结束展开的条件。

求列表最大值

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

递归练习

使用递归实现几个haskell已有的函数

replicate

生成一个列表有n个元素的列表，列表个数为第一参数，列表元素为第二参数。

Prelude> replicate 3 5
[5,5,5]

实现

replicate' :: Int -> a -> [a]
replicate' n x
    | n <= 0 = []
    | otherwise = x:replicate' (n-1) x

take

从列表中去一定数量的元素， 第一个参数为元素个数，第二个参数为列表

Prelude> take 3 [9,8,7,6,5,4,3]
[9,8,7]

实现

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

reverse

反转列表

Prelude> reverse [9,8,7,6,5,4,3]
[3,4,5,6,7,8,9]

实现

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

注意：在列表头插入用":", 在尾部拼接用"++", 列表大的情况下，使用"++"效率不高。

repreat

返回一个包含元素的无限列表，第一个参数为元素。

Prelude> repeat 3
[3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,Interrupted.

实现

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

zip

将2个列表作为输入，返回捆绑了2个列表元素的列表。会截断长列表，以短列表为准。

Prelude> zip [1, 2, 3] [4, 5, 6]
[(1,4),(2,5),(3,6)]

实现

*Main> zip' [1, 2, 3] [4, 5, 6]
[(1,4),(2,5),(3,6)]

elem

判断元素是否在列表中

Prelude> elem 6 [6, 7, 8, 9]
True
Prelude> elem 5 [6, 7, 8, 9]
False

实现

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

快速排序的实现

quickSort :: (Ord a) => [a] -> [a] 
quickSort [] = []
quickSort (x:xs) =                                           --以x为基准
    let smallerOrEqual = [a | a <- xs, a <=x]                --小于等于x的序列
        larger = [a | a <- xs, a > x]                        --大于x的序列     
    in quickSort smallerOrEqual ++ [x] ++ quickSort larger   --组合拼接列表

执行

*Main> quickSort [1, 3, 6, 8, 9, 5, 4, 2]
[1,2,3,4,5,6,8,9]

递归总结

递归函数有固定的模式

1. 先定义基准， 也就是特殊输入的简单非递归解。
2. 分解问题，递归调用自身，基于子问题的结果，组合为最终解。