# [Haskell] 学习笔记3

### Recursion

(1) Recursion on list

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
product1 :: Num a => [a] -> a product1 [] = 1 product1 (n:ns) = n * product1 ns length1 :: [a] -> Int length1 [] = 0 length1 (_:xs) = 1 + length1 xs reverse1 :: [a] -> [a] reverse1 [] = [] reverse1 (x:xs) = reverse1 xs ++ [x] (<++>) :: [a] -> [a] -> [a] [] <++> ys = ys (x:xs) <++> ys = x : (xs <++> ys) insert1 :: Ord a => a -> [a] -> [a] insert1 x [] = [x] insert1 x (y:ys) | x <= y = x : y : ys | otherwise = y : insert1 x ys |

(2) multiple arguments

1 2 3 4 5 6 7 8 9 |
zip1 :: [a] -> [b] -> [(a,b)] zip1 [] _ = [] zip1 _ [] = [] zip1 (x:xs) (y:ys) = (x,y) : zip1 xs ys drop1 :: Int -> [a] -> [a] drop1 0 xs = xs drop1 _ [] = [] drop1 n (_:xs) = drop1 (n - 1) xs |

(3) multiple recursion

1 2 3 4 5 6 7 8 9 10 11 |
fib1 :: Int -> Int fib1 0 = 0 fib1 1 = 1 fib1 n = fib1 (n - 2) + fib1 (n - 1) qsort :: Ord a => [a] -> [a] qsort [] = [] qsort (x:xs) = qsort smaller ++ [x] ++ qsort larger where smaller = [a | a <- xs, a <= x] larger = [b | b <- xs, b > x] |

### Higher-order functions

Functions are usually using curring

1 2 |
add :: Int -> Int -> Int add x y = x + y |

means

1 2 |
add :: Int -> (Int -> Int) add = \x -> (\y -> x + y) |

add is a function that takes an integer x and returns a function, which in turn takes another integer y and returns their sum x + y.

In Haskell, it is also permissible to define functions that take *functions* as arguments

1 2 |
twice :: (a -> a) -> a -> a twice f x = f (f x) |

Formally speaking, a function that takes a function as an argument or returns a function as a result is called a *higher-order function*

(1) map

The function map applies a function to all elements of a list

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

1 2 3 4 5 6 |
Prelude> map (+1) [1,2,3,4] [2,3,4,5] Prelude> map even [1,2,3,4] [False,True,False,True] Prelude> map (map (+1)) [[1,2,3],[4,5]] [[2,3,4],[5,6]] |

map can also be defined using *recursion*

1 2 3 |
map :: (a -> b) -> [a] -> [b] map f []= [] map f (x:xs) = f x : map f xs |

(2) filter

Selects all elements of a list that satisfy a predicate

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

1 2 |
Prelude> filter (>3) [1,2,3,4,5] [4,5] |

filter can also be defined using *recursion*

1 2 3 4 5 |
filter :: (a -> Bool) -> [a] -> [a] filter p [] = [] filter p (x:xs) | p x = x : filter p xs | otherwise = filter p xs |

(3) foldr

foldr(fold right) uses of operators associate to right a + (b + (c + d))

variant of pattern :

1 2 |
f []= v f (x:xs) = x # f xs |

1 2 3 4 5 6 7 8 9 10 11 12 |
sum [] = 0 sum (x:xs) = x + sum xs -- is same as sum :: Num a => [a] -> a sum = foldr (+) 0 -- is same as sum1 :: Num a => [a] -> a sum1 = foldr (\a b -> a + b) 0 |

1 2 3 4 5 6 7 8 9 10 11 12 |
product [] = 1 product (x:xs) = x * product xs -- is same as product :: Num a => [a] -> a product = foldr (*) 1 -- is same as (using lambda function) product :: Num a => [a] -> a product = foldr (\a b -> a * b) 1 |

1 2 3 4 5 6 7 8 9 10 11 12 |
or [] = False or (x:xs) = x || or xs -- is same as or :: [Bool] -> Bool or = foldr (||) False -- is same as (using lambda function) or :: [Bool] -> Bool or = foldr (\a b -> a || b) False |

1 2 3 |
myElem :: Eq a => a -> [a] -> Bool myElem that myList = foldr(\a b -> (that == a) || b) False myList |

The

*foldr*function itself can be defined using recursion:

1 2 3 |
foldr :: (a -> b -> b) -> b -> [a] -> b foldr f v [] = v foldr f v (x:xs) = f x (foldr f v xs) |

Applying the function

*foldr (+) 0*to 1 : (2 : (3 : [])) give the result 1 + (2 + (3 + 0)), g(1 g(2 g(3 0))) in which : and [ ] have been replaced by + and 0, respectively

For *length* function, ‘a’ : (‘b’ : (‘c’ : [ ])) should give the result 1 + (1 + (1 + 0))

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

For *reverse *function, 1 : (2 : (3 : [ ])) should give the result (([ ] ++ [3]) ++ [2]) ++ [1]

1 2 |
reverse1 :: [a] -> [a] reverse1 = foldr(\x xs -> xs ++ [x]) [] |

(4) foldl

foldl(fold left) uses of operators associate to left ((a + b) + c) + d

variant of pattern :

1 2 |
f v []= v f v (x:xs) = f (v # x) xs |

That is, the function maps the empty list to the accumulator value v, and any non- empty list to the result of recursively processing the tail using a new accumulator value obtained by applying an operator # to the current value and the head of the list.

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

1 2 |
length :: [a] -> Int length = foldl(\n _ -> n + 1) 0 |

For *reverse *function, 1 : (2 : (3 : [ ])) should give the result [3] : ([2] : ([1] : [ ]))

1 2 |
reverse :: [a] -> [a] reverse = foldl (\xs x ->[x] ++ xs) [] |

The foldl function itself can be defined using recursion:

1 2 3 |
foldl :: (a -> b -> a) -> a -> [b] -> a foldl f v [] = v foldl f v (x:xs) = f (f v x) xs |