[Haskell] 学习笔记3

[Haskell] 学习笔记3

Recursion

(1) Recursion on list

(2) multiple arguments

(3) multiple recursion

Higher-order functions

Functions are usually using curring

means

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

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

map can also be defined using recursion

(2) filter

Selects all elements of a list that satisfy a predicate

filter can also be defined using recursion

(3) foldr

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

variant of pattern :




The foldr function itself can be defined using recursion:

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))

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

(4) foldl

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

variant of pattern :

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)

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

The foldl function itself can be defined using recursion: