A bunch of implementations for map, filter and fold in Racket

map-filter-fold.rkt

;; map

;; simple definition
(define (map/simple f lst)
  (if (empty? lst) empty
      (cons (f (first lst))
            (map/simple f (rest lst)))))

(map/simple (λ (x) (* 2 x)) '(1 2 3 4))

;; with pattern matching
(define (map/match f lst)
  (match lst
    ['()            '()]
    [(cons hd tl)    (cons (f hd) (map/match f tl))]))

(map/match (λ (x) (* 2 x)) '(1 2 3 4))

;; parametrize both cons and the empty list, '()
(define (abstract-map kons nil f lst)
  (if (null? lst)
      nil
      (kons (f (car lst))
            (abstract-map kons nil f (cdr lst)))))

;; supply list constructor, the empty list and the identity, to return original list - yields '(1 2 3 4)
(abstract-map cons '() identity '(1 2 3 4))
 
;; supply addition, 0 and the identity, to sum the list - yields 10
(abstract-map + 0 identity '(1 2 3 4))

;; change the identity to square to calculate the vector norm of the list - yields 25
(abstract-map + 0 (λ (x) (* x x)) '(3 4)) 

;; filter

;; simple definition
(define (filter/simple select? lst)
  (if (empty? lst) empty
      (let ([elt (first lst)]
            [the-rest (rest lst)])
        (if (select? elt)
            (cons elt (filter/simple select? the-rest))
            (filter/simple select? the-rest)))))

(filter/simple (λ (x) (> x 0)) '(1 2 3 4))

;; conditional tests
(define (filter/test p? lst)
  (cond
    [(null? lst)      '()]
    [(p? (car lst))    (cons (car lst)
                             (filter/test p? (cdr lst)))]
    [else              (filter/test p? (cdr lst))]))

;; structural pattern matching
(define (filter/match p? lst)
  (match lst
    ['() '()]
    [(cons (? p?) tl)   (cons (car lst) (filter/match p? tl))]
    [(cons hd tl)       (filter/match p? tl)]))

;; fold

(define (foldl/simple f val lst)
  (if (empty? lst) val
      (fold/simple f
            (f val (first lst))
            (rest lst))))

;; foldr (:) [] [1,2,3,4] = 1:(2:(3:(4:[])))

(define (foldr/test kons nil lst)
  (if (null? lst)
      nil
      (kons (car lst)
            (foldr/test kons nil (cdr lst)))))

(foldr/test cons '() '(1 2 3 4)) ; yields '(1 2 3 4)
(foldr/test +     0  '(1 2 3 4)) ; yields 10

;; transforming using tail-recursion gives us foldl
;; foldl (:) [] [1,2,3,4] = 4:(3:(2:(1:[])))

(define (foldl/test kons nil lst)
  (if (null? lst)
      nil
      (foldl/test kons (kons (car lst) nil) (cdr lst))))

(foldl/test cons '() '(1 2 3 4)) ; yields '(4 3 2 1)

;; reduce is a special case of folding
(define (reduce op lst)
  (match lst
    ['()             (error "no elements in list")]
    [(list a)         a]
    [(cons hd tl)    (op hd (reduce op tl))]))

(reduce + '(1 2 3 4)) ; yields 10