Having some fun with Scheme by implementing sequence operations in various ways. All tests are done on my computer using the very primitive method of wrapping the call with (time).

collection_api.scm

;; ======================================================================================
;; # Uses the Berkeley simple stk package for the `bf` and `se`.
;; ======================================================================================

(define (reduce-berk f start coll)
  (define (iter rest ret)
    (if (empty? rest)
      ret
      (iter (bf rest) (f ret (first rest)))))
  (iter coll start))

(define (map-berk f coll)
  (reduce-berk (lambda (r x) (se r (f x))) '() coll))

(define (filter-berk pred coll)
  (map-berk (lambda (v) (if (pred v) v '())) coll))

(define (reverse-berk coll)
  (reduce-berk (lambda (r v) (se v r)) '() coll))

(define (remove-berk pred coll)
  (filter-berk (lambda (x) (not (pred x))) coll))

(define (count-berk coll)
  (reduce-berk (lambda (s n) (+ s 1)) 0 coll))

(define (sum-berk coll)
  (reduce-berk (lambda (s n) (+ s n)) 0 coll))


;; ======================================================================================
;; # Implementations that don't use Berkeley's helpers.
;; ======================================================================================

; ----------------------------------------------------------------------------------------
; # Reduce
; ----------------------------------------------------------------------------------------

; Uses slightly less memory than reduce-recur. Sometimes it's a bit faster and sometimes
; it's a bit slower. Both use tail-call optimization so they have good perf, but this one
; tends to win because it's allocating less memory.
(define (reduce-iter f start coll)
  (define (iter rest ret)
    (if (null? rest)
      ret
      (iter (cdr rest) (f ret (car rest)))))
  (iter coll start))

; Runs nearly as fast as the reduce-iter, but uses slightly more memory.
(define (reduce-recur f start coll)
  (if (null? coll)
    start
    (reduce-recur f (f start (car coll)) (cdr coll))))


; Example uses of reduce
(define (count-iter coll)
  (reduce-iter (lambda (s n) (+ s 1)) 0 coll))

(define (sum-iter coll)
  (reduce-iter (lambda (s n) (+ s n)) 0 coll))


; ----------------------------------------------------------------------------------------
; # Reverse
; ----------------------------------------------------------------------------------------
; Uses slightly more memory than the native implmentation and is close in speed. Best to
; go with native for all cases.
; ----------------------------------------------------------------------------------------

(define (reverse-iter coll)
  (define (iter a acc)
    (if (null? a)
      acc
      (iter (cdr a) (cons (car a) acc))))
  (iter coll '()))

(define (reverse-recur coll)
  (if (null? coll)
    coll
    (append (reverse-recur (cdr coll))
            (list (car coll)))))

;; # Reduce-based implementations

(define (reduce-reverse-recur coll)
  (reduce-recur (lambda (r v) (cons v r)) '() coll))

(define (reduce-reverse-iter coll)
  (reduce-iter (lambda (r v) (cons v r)) '() coll))


; ----------------------------------------------------------------------------------------
; # Map
; ----------------------------------------------------------------------------------------

(define (recuce-map-iter f coll)
  (reverse (reduce-iter (lambda (r x) (cons (f x) r)) '() coll)))

(define (recuce-map-recur f coll)
  (reverse (reduce-recur (lambda (r x) (cons (f x) r)) '() coll)))

; TODO: add a non-reduce map


; ----------------------------------------------------------------------------------------
; # Filter/Remove
; ----------------------------------------------------------------------------------------

; Performs well but seg faults around 50k items in coll.
(define (filter-recur pred coll)
  (cond ((null? coll) nil)
        ((pred (car coll))
         (cons (car coll)
               (filter-recur pred (cdr coll))))
        (else (filter-recur pred (cdr coll)))))

(define (remove-recur pred coll)
  (filter-recur (lambda (x) (not (pred x))) coll))

; Performs significantly better than filter-recur
(define (filter-iter pred coll)
  (define (iter rest acc)
    (if (null? rest)
      (reverse acc) ; Best perf with native reverse.
      (iter (cdr rest)
            (if (pred (car rest))
              (cons (car rest) acc)
              acc))))
  (iter coll '()))

(define (remove-iter pred coll)
  (filter-iter (lambda (x) (not (pred x))) coll))

;; # Reduce-based implementations

; Uses more memory than the filter-recur (reduce-independent) implementation below
; for small collections, but can work with large datasets. The recursive implementation
; seg faults when filtering a collection of 50k items (maybe even less).
(define (reduce-filter-iter pred coll)
  (reverse (reduce-iter (lambda (r x) (if (pred x) (cons x r) r)) '() coll)))

(define (reduce-remove-iter pred coll)
  (recuce-filter-iter (lambda (x) (not (pred x))) coll))

; TODO: test
(define (reduce-filter-recur pred coll)
  (reverse (reduce-recur (lambda (r x) (if (pred x) (cons x r) r)) '() coll)))

(define (reduce-remove-recur pred coll)
  (recuce-filter-recur (lambda (x) (not (pred x))) coll))