Learn You a Haskell for Great Good

Posted on 2013-05-15 | In Haskell

本文为”Learn You a Haskell for Great Good”读书笔记

递归

haskell用递归代替for/while循环

递归求最大值

maximumVal :: (Ord a)=>[a]->a
maximumVal [] = error "error"
maximumVal [x] = x
maximumVal (x:xs) 
	| x > maxTail = x 
	| otherwise = maxTail
	where maxTail = maximumVal xs

我们取个 List [2,5,1] 做例子来看看它的工作原理。当调用 maximum’ 处理它时，前两个模式不会被匹配，而第三个模式匹配了它并将其分为 2 与 [5,1]。 where 子句再取 [5,1] 的最大值。于是再次与第三个模式匹配，并将 [5,1] 分割为 5 和 [1]。继续，where 子句取 [1] 的最大值，这时终于到了边缘条件！回传 1。进一步，将 5 与 [1] 中的最大值做比较，易得 5，现在我们就得到了 [5,1] 的最大值。再进一步，将 2 与 [5,1] 中的最大值相比较，可得 5 更大，最终得 5。

改用 max 函数会使代码更加清晰。如果你还记得，max 函数取两个值做参数并回传其中较大的值。如下便是用 max 函数重写的 maximun’

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

实现take

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

实现reverse

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

实现zip

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

快速排序

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

高阶函数

其实理解高阶函数从数学的角度比较好理解

f(x) = x^2
g(x) = 2x+1
f(g(x)) = (2x+1)^2 = 4x^2+4x+1

这种就是高阶函数

currying:

把一个函数的多个参数分解成多个函数然后把函数多层封装起来，每层函数都返回一个函数去接收下一个参数这样，可以简化函数的多个参数。

以max为例

getMaxValue x  = max 4 5

把空格放到两个东西之间，称作函数调用。它有点像个运算符，并拥有最高的优先级。

这个等价于：

getMaxValue2 x = (max 4) 5

理解:

根据currying，(max 4)会拿4和内部的一个变量比较，这个变量值可能是0，比较后这个变量的值为4 然后它返回一个函数，这个函数接受一个参数，并且内部已经有了一个值了，这个值可能为4 最后将参数5传入这个函数，这个函数拿5和内部的变量4比较，则返回5

再看一个乘法：

multThree :: (Num a) => a -> a -> a -> a 
multThree x y z = x * y * z

假设输入为multThree 3 5 9，根据空格，它的执行过程为：

(((multThree 3)5)9)

比较大小的函数：

compareWithHundred :: (Num a,Ord a) => a -> Ordering 
compareWithHundred x = compare 100 x 

这个函数也可以忽略掉参数

compareWithHundredWithoutX :: (Num a,Ord a) => a -> Ordering 
compareWithHundredWithoutX = compare 100 

applyTwice :: (a -> a) -> a -> a   
applyTwice f x = f (f x)

首先注意这类型声明。在此之前我们很少用到括号，因为 (->) 是自然的右结合，不过在这里括号是必须的。它标明了首个参数是个参数与回传值类型都是a的函数，第二个参数与回传值的类型也都是a 我们姑且直接把它看作是取两个参数回传一个值，其首个参数是个类型为 (a->a) 的函数,第二个参数是个 a

例如：

ghci> applyTwice (+3) 10   

这里第一个参数为fx = x+3，x省略了，第二个参数为10 计算时是： f(10)= 13 13+3 = 16 数学模型为：f(f(x)) = (x+3)+3 = x+6

实现zipwith,求两个数组的 f 操作

zipWith' :: (a -> b -> c) -> [a] -> [b] -> [c]   
zipWith' _ [] _ = []   
zipWith' _ _ [] = []   
zipWith' f (x:xs) (y:ys) = f x y : zipWith' f xs ys

例如求和

ghci> zipWith' (+) [4,2,5,6] [2,6,2,3]   
[6,8,7,9]

首先f是一个接受两个参数，返回一个参数的函数 f x y 返回的就是 x+y

各种花样

ghci> zipWith' max [6,3,2,1] [7,3,1,5]   
[7,3,2,5]   
ghci> zipWith' (++) ["foo "，"bar "，"baz "] ["fighters"，"hoppers"，"aldrin"]   
["foo fighters","bar hoppers","baz aldrin"]   
ghci> zipWith' (*) (replicate 5 2) [1..]   
[2,4,6,8,10]   
ghci> zipWith' (zipWith' (*)) [[1,2,3],[3,5,6],[2,3,4]] [[3,2,2],[3,4,5],[5,4,3]]   
[[3,4,6],[9,20,30],[10,12,12]]

map：取一个函数和 List 做参数，遍历该 List 的每个元素来调用该函数产生一个新的 List。看下它的类型声明和实现:

map :: (a -> b) -> [a] -> [b]   
map _ [] = []   
map f (x:xs) = f x : map f xs

从这类型声明中可以看出，它取一个取 a 回传 b 的函数和一组 a 的 List，并回传一组 b。这就是 Haskell 的有趣之处：有时只看类型声明就能对函数的行为猜个大致。 map 函数多才多艺，有一百万种用法。如下是其中一小部分:

ghci> map (+3) [1,5,3,1,6]   
[4,8,6,4,9]

这个和list comprehension相同[x+3 | x <- [1,3,2,3,5]] map多个条件也仅仅遍历一遍数组

filter：函数取一个限制条件和一个 List，回传该 List 中所有符合该条件的元素

filter :: (a -> Bool) -> [a] -> [a]   
filter _ [] = []   
filter p (x:xs)    
    | p x       = x : filter p xs   
    | otherwise = filter p xs


ghci> filter (>3) [1,5,3,2,1,6,4,3,2,1]   
[5,6,4]   

takeWhile 函数，它取一个限制条件和 List 作参数，然后从头开始遍历这一 List，并回传符合限制条件的元素

所有小于 10000 的奇数的平方和 ghci> sum (takeWhile (<10000) (filter odd (map (^2) [1..])))

lambda:就是匿名函数。有些时候我们需要传给高阶函数一个函数，而这函数我们只会用这一次，这就弄个特定功能的 lambda

编写 lambda，就写个 \ (因为它看起来像是希腊字母的 lambda 如果你斜视的厉害) 后面是用空格分隔的参数，-> 后面就是函数体。通常我们都是用括号将其括起，要不然它就会占据整个右边部分。

例如，表达式:

map (+3) [1,6,3,2] 与 map (\x -> x+3) [1,6,3,2]

对于多个参数：

ghci> zipWith (\a b -> (a * 30 + 3) / b) [5,4,3,2,1] [1,2,3,4,5] 

fold : fold 取一个二元函数，一个初始值(我喜欢管它叫累加值)和一个需要折叠的 List。这个二元函数有两个参数，即累加值和 List 的首项(或尾项)，回传值是新的累加值。然后，以新的累加值和新的 List 首项调用该函数，如是继续。到 List 遍历完毕时，只剩下一个累加值，也就是最终的结果。

首先看下 foldl 函数，也叫做左折叠。它从 List 的左端开始折叠，用初始值和 List 的头部调用这二元函数，得一新的累加值，并用新的累加值与 List 的下一个元素调用二元函数。如是继续。

我们再实现下 sum，这次用 fold 替代那复杂的递归：

sum' :: (Num a) => [a] -> a   
sum' xs = foldl (\acc x -> acc + x) 0 xs

acc是累加值由于使用foldl，那么x是数组的第一个元素 0 是起始值计算过程是拿数组的x和acc相加，作为新的x，然后递归

这条语句等于foldl (+) [1,2,3]

实现’elem’

elem' :: (Eq a) => a -> [a] -> Bool   
elem' y ys = foldl (\acc x -> if x == y then True else acc) False ys

所有遍历 List 中元素并据此回传一个值的操作都可以交给 fold 实现。 {!无论何时需要遍历 List 并回传某值，都可以尝试下 fold!}。因此，fold的地位可以说与 map和 filter并驾齐驱，同为函数式编程中最常用的函数之一。

foldl1是fold的简化版，初始值默认为数组的第一个元素上面求和的函数用foldl1实现如下：

sum1 xs = foldl1 (\acc x -> acc + x) xs

这条语句等于:

foldl1 (+) [1,2,3]

scanl 和 scanr 与 foldl 和 foldr 相似，只是它们会记录下累加值的所有状态到一个 List。也有 scanl1 和 scanr1。

ghci> scanl (+) 0 [3,5,2,1]   
[0,3,8,10,11]   
ghci> scanr (+) 0 [3,5,2,1]   
[11,8,3,1,0]  

Function composition:函数的迭代：f(g(x)) 在haskell中的表示

先看一个map函数

val = map (\x -> negate (abs x)) [5,-3,-6,7,-3,2,-19,24]   
[-5,-3,-6,-7,-3,-2,-19,-24]

先求绝对值再求反也可以合并执行：

val2 = map (negate . abs) [5,-3,-6,7,-3,2,-19,24]   

oddSquareSum :: Integer   
oddSquareSum = sum (takeWhile (<10000) (filter odd (map (^2) [1..])))

oddSquareSum :: Integer   
oddSquareSum = sum . takeWhile (<10000) . filter odd . map (^2) $ [1..]

oddSquareSum :: Integer   
oddSquareSum =    
    let oddSquares = filter odd $ map (^2) [1..]   
        belowLimit = takeWhile (<10000) oddSquares   
    in  sum belowLimit

Learn You a Haskell for Great Good

递归

高阶函数

Resources