递归#
简介#
递归：在表达式内部定义表达式自己；
备注
斐波那契的数学定义即为一种递归：
\[\begin{split}\begin{equation} F(n) = \left \{ \begin{aligned} &0 &n = 0 \\ &1 &n = 1 \\ &F(n-1) + F(n-2) &n \ge 2 \end{aligned} \right. \end{equation}\end{split}\]在 Haskell 中，递归十分重要，因为 Haskell 通过声明表达式来计算，所以 Haskell 中没有命令式语言中的
for或while循环结构，而递归可以用于声明表达式，实现遍历等操作；quicksort :: Ord a => [a] -> [a] quicksort [] = [] quicksort (x : xs) = let smallerSorted = quicksort [ a | a <- xs, a <= x ] biggerSorted = quicksort [ b | b <- xs, b > x ] in smallerSorted ++ [x] ++ biggerSorted
递归模式#
map模式#
map模式可实现列表的遍历，对列表中的每个元素进行相同的操作；思路：
对列表每个元素进行加一：
addOne :: Num a => [a] -> [a] addOne [] = [] addOne (x : xs) = x + 1 : addOne xs exp1 = addOne [1, 2, 3] -- [2,3,4]
对列表每个元素进行平方：
squareAll :: Num a => [a] -> [a] squareAll [] = [] squareAll (x : xs) = x ^ 2 : squareAll xs exp2 = squareAll [1, 2, 3] -- [1,4,9]
两函数在结构上重复，为避免重复，可以定义函数
mapList，对两个函数进行抽象：mapList :: Num a => (a -> a) -> [a] -> [a] mapList f [] = [] mapList f (x : xs) = f x : mapList f xs exp3 = mapList (+ 1) [1, 2, 3] -- [2,3,4] exp4 = mapList (^ 2) [1, 2, 3] -- [1,4,9]
map函数即为该模式的实现；
filter模式#
filter模式可实现列表的筛选；思路：
保留列表中大于三的元素：
gt3 :: (Num a, Ord a) => [a] -> [a] gt3 [] = [] gt3 (x : xs) | x > 3 = x : gt3 xs | otherwise = gt3 xs exp1 = gt3 [1, 5, 2, 7, 3, 6] -- [5,7,6]
保留列表中平方值小于十的元素：
sqLt10 :: (Num a, Ord a) => [a] -> [a] sqLt10 [] = [] sqLt10 (x : xs) | x ^ 2 < 10 = x : sqLt10 xs | otherwise = sqLt10 xs exp2 = sqLt10 [1, 5, 2, 7, 3, 6] -- [1,2,3]
两函数在结构上重复，为避免重复，可定义函数
filterList，对两个函数进行抽象：filterList :: (Num a, Ord a) => (a -> Bool) -> [a] -> [a] filterList f [] = [] filterList f (x : xs) | f x = x : filterList f xs | otherwise = filterList f xs exp3 = filterList (> 3) [1, 5, 2, 7, 3, 6] -- [5,7,6] exp4 = filterList (\x -> x ^ 2 < 10) [1, 5, 2, 7, 3, 6] -- [1,2,3]
filter函数即为该模式的实现；
fold模式#
fold模式可根据前一个元素计算后的状态对当前元素进行相应计算；思路：
求列表所有元素和起始值的和：
addAll :: Num a => a -> [a] -> a addAll a [] = a addAll a (x : xs) = addAll (a + x) xs exp1 = addAll 5 [1, 2, 3] -- 11
求列表所有元素和起始值的积：
multiAll :: Num a => a -> [a] -> a multiAll a [] = a multiAll a (x : xs) = addAll (a * x) xs exp2 = multiAll 2 [1, 2, 3] -- 12
两函数在结构上重复，为避免重复，可定义函数
foldList，对两个函数进行抽象：foldList :: (Num a, Num b) => (b -> a -> b) -> b -> [a] -> b foldList f z [] = z foldList f z (x : xs) = foldList f (f z x) xs exp3 = foldList (+) 5 [1, 2, 3] -- 11 exp4 = foldList (*) 2 [1, 2, 3] -- 12
fold*函数即为该模式的实现；
fold*函数#
fold*函数：用起始值和运算函数，将序列反复“折叠”，直至最后剩下唯一一个值；流程：
接受一个二目运算函数、一个起始值和一个序列作为参数；
从起始值和序列的第一个值或最后一个值开始，用运算函数进行计算，得到新的起始值；
res = foldl f s [a, b, c, d] -- 等价于 ((((s `f` a) `f` b) `f` c) `f` d)
重复上一步，直到将序列“折叠”至一个值；
返回该值；
1res = foldl (+) 2 [1, 2, 3, 4] 2-- 2 + 1 3-- [1,2,3,4] 4-- 3 + 2 5-- [2,3,4] 6-- 5 + 3 7-- [3,4] 8-- 8 + 4 9-- [4] 10-- 12
fold*函数在 Haskell 中十分重要，许多内置函数都是在fold*函数的基础上定义的，如sum函数、product函数、length函数等；1sum' :: Num a => [a] -> a 2sum' = foldl (+) 0 3 4product' :: Num a => [a] -> a 5product' = foldl (*) 1 6 7elem' :: Eq a => a -> [a] -> Bool 8elem' y = foldl (\acc x -> (x == y) || acc) False 9-- elem' 2 [1,2,3,4] 10-- (2 == 1) || False -> False (new starting value) 11-- [1,2,3,4] 12-- (2 == 2) || False -> True 13-- [2,3,4] 14-- (2 == 3) || True -> True 15-- [3,4] 16-- (2 == 4) || True -> True 17-- [4]
函数
-
Data.Foldable.foldl:: Foldable t => (b -> a -> b) -> b -> t a -> b# 从序列左侧开始“折叠”。
-
Data.Foldable.foldr:: Foldable t => (a -> b -> b) -> b -> t a -> b# 从序列右侧开始“折叠”。
注意
以上四个fold*函数是惰性的，在“折叠”过程中并不进行计算，而是将计算要求缓存，因此在处理大规模列表时，容易出现栈溢出的问题。
-
Data.Foldable.foldMap:: (Foldable t, Monoid m) => (a -> m) -> t a -> m# 接受一个函数和一个可折叠序列，该函数接受一个值并返回一个单位半群成员类型的值，对序列中每个元素应用该函数并将结果通过
mappend函数缩减为一个单位半群值。
1-- | 解析逆波兰式（Reverse Polish Notation）。
2--
3-- ==== __例子:__
4-- >>> solveRPN "10 20 + 3 *"
5-- 90.0
6--
7-- >>> solveRPN "10 20 1 sum ln"
8-- 3.4339871
9solveRPN :: String -> Float
10solveRPN = head . foldl foldingFunction [] . words
11 where
12 foldingFunction (x : y : zs) "+" = (y + x) : zs
13 foldingFunction (x : y : zs) "-" = (y - x) : zs
14 foldingFunction (x : y : zs) "*" = (y * x) : zs
15 foldingFunction (x : y : zs) "/" = (y / x) : zs
16 foldingFunction (x : y : zs) "^" = (y ** x) : zs
17 foldingFunction (x : ys) "ln" = log x : ys
18 foldingFunction xs "sum" = [sum xs]
19 foldingFunction xs num = read num : xs
scan*函数#
scan*函数与fold*函数类似，但以列表方式返回所有中间起始值（包括最初起始值）；exp1 = scanl (+) 1 [1, 2, 3, 4] -- [1,2,4,7,11] exp2 = scanl (\acc y -> (2 == y) || acc) False [1, 2, 3, 4] -- [False,False,True,True,True]
函数