How to convert recursion to a foldr

foldtut.scm

;; How to convert a recursive procedure to a fold
;; (see also "a tutorial on the universality and expressiveness of fold"
;; by Hutton, which will generalise this a bit to even show you how to
;; express "foldl" as a "foldr", though it uses haskell rather than scheme)

(define (fold-right func base l)
  (if (null? l)
      base
      (func (car l)
            (fold-right func base (cdr l)))))

;;;; Easy example
(define (filter p? l)
  (cond ((null? l) '())
        ((p? (car l))
         (cons (car l) (filter p? (cdr l))))
        (else
         (filter p? (cdr l)))))

;;; How to rewrite

;; 1. Identify the two cases

((null? l) '()) ; null case

(cond  ; recursion on cdr
 ((p? (car l))
  (cons (car l) (filter p? (cdr l))))
 (else
  (filter p? (cdr l))))

;; 2. In the recursive case, pull out the recursion and any reference
;; to the car l
(let ((x (car l))
      (xs (filter p? (cdr l))))
  (cond
   ((p? x) (cons x xs))
   (else xs)))

;; 3. Turn the let into a lambda + application
((lambda (x xs)
   (cond
    ((p? x) (cons x xs))
    (else xs)))
 (car l)
 (filter p? (cdr l)))

;; 4. Plug in that function, and your earlier base case
(define (filter p? l)
  (fold-right (lambda (x xs)
                (cond
                 ((p? x) (cons x xs))
                 (else xs)))
              '()
              l))




;; A more complex example. Hope you like higher order functions :)
(define (list->number ls)
  (define (loop number ls)
    (if (null? ls)
        number
        (loop (+ (* 10 number) (car ls))
              (cdr ls))))
  (loop 0 ls))

;; Pull out the number argument, as it is not constant, but changes
;; every recursion
(define (list->number ls)
  (define (loop ls)
    (lambda (number)
      (if (null? ls)
          number
          ((loop (cdr ls))
           (+ (* 10 number) (car ls))))))
  ((loop ls) 0))

;; Push that function down into the branches of the if
(define (list->number ls)
  (define (loop ls)
    (if (null? ls)
        (lambda (number) number)
        (lambda (number)
          ((loop (cdr ls))
           (+ (* 10 number) (car ls))))))
  ((loop ls) 0))

;; proceed as before

; null case
(null? ls) -> (lambda (number) number)

; recursive case
(lambda (number)
  ((loop (cdr ls))
   (+ (* 10 number) (car ls))))

;; pull out recursive call on cdr, and reference to car
(let ((x (car ls))
      (xs (loop (cdr ls))))
  (lambda (number)
    (xs
     (+ (* 10 number) x))))

;; change to immediate application
((lambda (x xs)
   (lambda (number)
     (xs
      (+ (* 10 number) x))))
 (car ls)
 (loop (cdr ls)))

;; take that function, and your base case, and plug it in to foldr
(define (list->number ls)
  (define (loop ls)
    (fold-right (lambda (x xs)
                  (lambda (number)
                    (xs
                     (+ (* 10 number) x))))
                (lambda (number) number)
                ls))
  ((loop ls) 0))