profile photo

函数式三板斧(map,filter,fold)

2021-08-02 21:27:02

什么是 map,filter,fold

map

map 接受一个函数和一个列表,并将函数作用在列表中的每个元素上,最后返回函数作用后的列表。

haskell 中map的类型签名
map :: (a -> b) -> [a] -> [b]

racket 代码
(define (mymap function mylist)
  (cond
     ((null? mylist) '())
     (else (cons (function (car mylist)) (mymap function (cdr mylist)) ))
  )
)
(define (add2 x) (+ 2 x))
(mymap add2 '(1 2 3 4 5 6 7 8))

=> (3 4 5 6 7 8 9 10)

filter

顾名思义,将列表中符合条件的值提取出来

haskell 中filter的类型签名
filter :: (a -> Bool) -> [a] -> [a]

racket代码
(define (myfilter condition? mylist)
  (cond
    ((null? mylist) '())
    ((condition? (car mylist)) (cons (car mylist) (myfilter condition? (cdr mylist))))
    (else (myfilter condition? (cdr mylist)))
  )
)

(define (odd? a)
  (eq? (modulo a 2) 1)
)

(myfilter odd? '(-1 -2 -3 -4 -5 -6 -7 -8 -9 -10))
=> (-1 -3 -5 -7 -9)

fold

fold 就是折叠的含义,一般来讲可以分为左折叠和右折叠

我们以左折叠(foldl)为例

haskell 中foldl的类型签名
foldl :: (a -> b -> a) -> a -> [b] -> a

racket代码
(define (myfoldl base function mylist)
  (cond
     ((null? mylist) base)
     (else (myfoldl (function base (car mylist)) function (cdr mylist)))
  )
)

(define (add x y)
  (+ x y)
)

(myfoldl 0 add '(1 2 3 4 5 6 7 8 9))
=> 45