;;; File:
;;; sum.scm
;;; Author:
;;; Samuel A. Rebelsky
;;; Version:
;;; 1.0 of February 2004
;;; Contents:
;;; (sumr numbers) - Sum a non-empty list of numbers.
;;; (suml numbers) - Sum a non-empty list of numbers.
;;; Summary:
;;; Two ways of summing a list, intended primarily as an example
;;; for introducing tail recursion.
;;; Procedures:
;;; suml
;;; sumr
;;; Parameters
;;; numbers, a list of numbers of the form (n1 n2 ... nk)
;;; Purpose:
;;; Sum the values in numbers.
;;; Produces:
;;; result, a number
;;; Preconditions:
;;; numbers is nonempty.
;;; Postconditions:
;;; result = n1 + n2 + ... + nk
;;; If any of n1 ... nk is inexact, result is inexact.
;;; If all of n1 ... nk are exact, result is exact.
(define sumr
(lambda (lst)
(if (null? (cdr lst))
(car lst)
(+ (car lst) (sumr (cdr lst))))))
(define suml
(lambda (lst)
(let kernel ((remaining (cdr lst)) (result (car lst)))
(if (null? remaining)
result
(kernel (cdr remaining) (+ result (car remaining)))))))
; What are the key differences you observe between these two versions?
; "sumr" seems to use less memory because it doesn't have result
; Do different orders of operations: sumr is right associative, suml is
; left associative
; suml does the computation at each step, sumr "delays" the computation
; (sumr (list 1 2 3 4))
; => (+ 1 (sumr (list 2 3 4)))
; => (+ 1 (+ 2 (sumr (list 3 4))))
; => (+ 1 (+ 2 (+ 3 (sumr (list 4)))))
; => (+ 1 (+ 2 (+ 3 4)))
; => (+ 1 (+ 2 7)
; ...
; (suml (list 1 2 3 4))
; => (kernel (list 2 3 4) 1)
; => (kernel (list 3 4) 3)
; => (kernel (list 4) 6)
; => (kernel null 10)
; => 10
(define suml-report
(lambda (lst)
(let kernel ((remaining (cdr lst)) (result (car lst)))
(display (list 'suml-kernel remaining result))
(newline)
(if (null? remaining)
result
(kernel (cdr remaining ) (+ result (car remaining)))))))