# 高阶函数 Higher-order Functions

## Note:​

import Data.Char

## 基本概念​

There is also a video on this section.

twice :: (a -> a) -> a -> atwice f x = f (f x)

For example:

> twice (*2) 312> twice (+10) 525> twice (\ x -> x ^ 2) 381> twice reverse [1,2,3][1,2,3]

## 处理清单​

There is also a video on this section.

### The Map Function​

map :: (a -> b) -> [a] -> [b]

For example:

> map (+1) [1,3,5,7][2,4,6,8]> map (^3) [1,3,5,7][1,27,125,343]> map reverse ["conversation", "talking", "discussion"]["noitasrevnoc","gniklat","noissucsid"]

map 函数可以用一个特别简单的方式来定义，使用列表理解：

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

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

### The Filter Function​

filter :: (a -> Bool) -> [a] -> [a]

For example:

> filter even [1..10][2,4,6,8,10]

filter :: (a -> Bool) -> [a] -> [a]filter p xs = [x | x <- xs, p x]

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

## The Foldr Function​

There is also a video on this section.

f :: Num a => [a] -> af []     = vf (x:xs) = x # f xs

For example:

sum :: Num a => [a] -> asum []     = 0sum (x:xs) = x + sum xsproduct :: Num a => [a] -> aproduct []     = 1product (x:xs) = x * product xsand :: [Bool] -> Booland []     = Trueand (x:xs) = x && and xs

For example:

sum = foldr (+) 0product = foldr (*) 1or = foldr (||) Falseand = foldr (&&) True

foldr 本身可以用递归来定义：

foldr :: (a -> b -> b) -> b -> [a] -> bfoldr f v []     = vfoldr f v (x:xs) = f x (foldr f v xs)

foldr (#) v [x0,x1,...,xn] = x0 # (x1 # (... (xn # v) ...))

For example:

sum [1,2,3]= foldr (+) 0 [1,2,3]= foldr (+) 0 (1:(2:(3:[])))= 1+(2+(3+0))= 6

product [1,2,3]= foldr (*) 1 [1,2,3]= foldr (*) 1 (1:(2:(3:[])))= 1*(2*(3*1))= 6

### Other Foldr Examples​

length :: [a] -> Intlength []     = 0length (_:xs) = 1 + length xs

For example:

length [1,2,3]= length (1:(2:(3:[])))= 1+(1+(1+0))= 3

length :: [a] -> Intlength = foldr (\_ n -> 1+n) 0

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

For example:

reverse [1,2,3]= reverse (1:(2:(3:[])))= (([] ++ [3]) ++ [2]) ++ [1]= [3,2,1]

x xs -> xs ++ [x] 替换每个（:），用 [] 替换 []。因此，我们有：

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

(++ ys) = foldr (:) ys

(++) = foldr (:)

## The Foldl Function​

There is also a video on this section.

sum :: Num a => [a] -> asum = sum' 0      where         sum' v []     = v         sum' v (x:xs) = sum' (v+x) xs

For example

sum [1,2,3]= sum' 0 [1,2,3]= sum' (0+1) [2,3]= sum' ((0+1)+2) [3]= sum' (((0+1)+2)+3) []= (((0+1)+2)+3)= 6

f :: Num a => a -> [a] -> af v []     = vf v (x:xs) = f (v # x) xs

The above sum function can be re-written using the higher-order library function foldl (fold left) as:

sum :: Num a => [a] -> asum = foldl (+) 0

product :: Num a => [a] -> aproduct = foldl (*) 1or :: [Bool] -> Boolor = foldl (||) Falseand :: [Bool] -> Booland = foldl (&&) Truelength :: [a] -> Intlength = foldl (\n _ -> n+1) 0

foldl 函数可以用递归来定义：

foldl :: (a -> b -> a) -> a -> [b] -> afoldl f v []     = vfoldl f v (x:xs) = foldl f (f v x) xs

foldl (#) v [x0,x1,...,xn] = (... ((v # x0) # x1) ...) #xn

## The Composition Operator​

There is also a video on this section.

(.) :: (b -> c) -> (a -> b) -> (a -> c)f . g = \x -> f (g x)

For example:

odd :: Int -> Boolodd n = not (even n)

odd :: Int -> Boolodd = not . even

twice :: (a -> a) -> a -> atwice f x = f (f x)
sumsqreven :: Integral a => [a] -> asumsqreven ns = sum (map (^2) (filter even ns))

twice' :: (a -> a) -> a -> atwice' f = f . fsumsqreven' :: Integral a => [a] -> asumsqreven' = sum . map (^2) . filter even

### Other Library Functions​

all :: (a -> Bool) -> [a] -> Boolall p xs = and [p x | x <- xs]

For example:

> all even [2,4,6,8,10]True> all odd [1,3,7,9,10]False

any :: (a -> Bool) -> [a] -> Boolany p xs = or [p x | x <- xs]

For example:

> any (== ' ') "abc def"True> any (> 10) [1,5,4,8,7]False

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

For example:

> takeWhile (/= ' ') "abc def""abc"> takeWhile even [2,4,6,7,8][2,4,6]

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

For example:

> dropWhile (== 'a') "aaabcadef""bcadef"> dropWhile odd [1,3,5,6,7][6,7]

## Programming Example - Binary String Transmitter 二进制字符串发射器​

There is also a video on this section.

1101 = (8 * 1) + (4 * 1) + (2 * 0) + (1 * 1)

1011 = (1 * 1) + (2 * 0) + (4 * 1) + (8 * 1)

### 基地转换 Base Conversion​

import Data.Char
type Bit = Int

bin2int :: [Bit] -> Intbin2int bits = sum [w*b | (w,b) <- zip weights bits]               where weights = iterate (*2) 1

iterate f x = [x, f x, f (f x), f (f (f x)), ...]

> bin2int [1,0,1,1]13

(1 * a) + (2 * b) + (4 * c) + (8 * d)

(1 * a) + (2 * b) + (4 * c) + (8 * d)= a + (2 * b) + (4 * c) + (8 * d)= a + 2 * (b + (2 * c) + (4 * d))= a + 2 * (b + 2 * (c + (2 * d)))= a + 2 * (b + 2 * (c + 2 * (d + 2 * 0)))

bin2int' :: [Bit] -> Intbin2int' = foldr (\x y -> x + 2*y) 0

int2bin :: Int -> [Bit]int2bin 0 = []int2bin n = n mod 2 : int2bin (n div 2)

For example:

> int2bin 13[1,0,1,1]

make8 :: [Bit] -> [Bit]make8 bits = take 8 (bits ++ repeat 0)

For example:

> make8 [1,0,1,1][1,0,1,1,0,0,0,0]

### 传动装置 Transmission​

There is also a video on this section.

encode :: String -> [Bit]encode = concat . map (make8 . int2bin . ord)

For example:

> encode "abc"[1,0,0,0,0,1,1,0,0,1,0,0,0,1,1,0,1,1,0,0,0,1,1,0]

chop8 :: [Bit] -> [[Bit]]chop8 [] = []chop8 bits = take 8 bits : chop8 (drop 8 bits)

decode :: [Bit] -> Stringdecode = map (chr . bin2int) . chop8

For example:

> decode [1,0,0,0,0,1,1,0,0,1,0,0,0,1,1,0,1,1,0,0,0,1,1,0]"abc"

transmit :: String -> Stringtransmit = decode . channel . encodechannel :: [Bit] -> [Bit]channel = id

For example:

> transmit "higher-order functions are easy""higher-order functions are easy"

> encode "higher-order functions are easy"[0,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,1,1,1,0,0,1,1,0,0,0,0,1,0,1,1,0,1,0,1,0,0,1,1,0,0,1,0,0,1,1,1,0,1,0,1,1,0,1,0,0,1,1,1,1,0,1,1,0,0,1,0,0,1,1,1,0,0,0,1,0,0,1,1,0,1,0,1,0,0,1,1,0,0,1,0,0,1,1,1,0,0,0,0,0,0,1,0,0,0,1,1,0,0,1,1,0,1,0,1,0,1,1,1,0,0,1,1,1,0,1,1,0,1,1,0,0,0,1,1,0,0,0,1,0,1,1,1,0,1,0,0,1,0,1,1,0,1,1,1,1,0,1,1,0,0,1,1,1,0,1,1,0,1,1,0,0,1,1,1,0,0,0,0,0,0,1,0,0,1,0,0,0,0,1,1,0,0,1,0,0,1,1,1,0,1,0,1,0,0,1,1,0,0,0,0,0,0,1,0,0,1,0,1,0,0,1,1,0,1,0,0,0,0,1,1,0,1,1,0,0,1,1,1,0,1,0,0,1,1,1,1,0]> decode [0,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,1,1,1,0,0,1,1,0,0,0,0,1,0,1,1,0,1,0,1,0,0,1,1,0,0,1,0,0,1,1,1,0,1,0,1,1,0,1,0,0,1,1,1,1,0,1,1,0,0,1,0,0,1,1,1,0,0,0,1,0,0,1,1,0,1,0,1,0,0,1,1,0,0,1,0,0,1,1,1,0,0,0,0,0,0,1,0,0,0,1,1,0,0,1,1,0,1,0,1,0,1,1,1,0,0,1,1,1,0,1,1,0,1,1,0,0,0,1,1,0,0,0,1,0,1,1,1,0,1,0,0,1,0,1,1,0,1,1,1,1,0,1,1,0,0,1,1,1,0,1,1,0,1,1,0,0,1,1,1,0,0,0,0,0,0,1,0,0,1,0,0,0,0,1,1,0,0,1,0,0,1,1,1,0,1,0,1,0,0,1,1,0,0,0,0,0,0,1,0,0,1,0,1,0,0,1,1,0,1,0,0,0,0,1,1,0,1,1,0,0,1,1,1,0,1,0,0,1,1,1,1,0]"higher-order functions are easy"

## 练习​

(1) 将函数作为结果返回的高阶函数更被称为什么？

(2) Express the comprehension [f x | x <- xs, p x] using the functions map and filter. The function type is given as:

fun :: Num a => (a -> a) -> (a -> Bool) -> [a] -> [a]

For example:

> fun (^2) even [1..20][4,16,36,64,100,144,196,256,324,400]> fun (^2) odd [1..20][1,9,25,49,81,121,169,225,289,361]

(3) Redefine map f and filter p using foldr. For your reference, here are the definitions of map and filter from lecture notes.

map :: (a -> b) -> [a] -> [b]map f []     = []map f (x:xs) = f x : map f xsfilter :: (a -> Bool) -> [a] -> [a]filter p [] = []filter p (x:xs)   | p x       = x : filter p xs   | otherwise = filter p xs

(4) Define a function altMap :: (a -> b) -> (a -> b) -> [a] -> [b] that alternatively applies the two argument functions to successive elements in a list.

For example:

> altMap (+10) (+100) [0,1,2,3,4][10,101,12,103,14]