[PRL] Accumulator for container capacity

[Karl Lieberherr]

About 10 years ago, Mitch proposed a version of the Container Capacity
problem
explained below. The "natural" recursive solution a la structural
programming
is inefficient and cries for an accumulator solution. What is the most
natural
accumulator solution that traverses the container exactly once?

I am asking because I teach accumulators in CSG 711 while Matthias is in
Germany.

-- Karl

Container Capacity problem:

Given a recursive container structure c, compute the total number of
capacity violations
in c.

Data definitions PL neutral:

;; Container = "(" 
;;   <contents> List(Item) <capacity> int ")" .
;; Item : Container | Simple.
;; List(S) ~ {S}.
;; Simple =  <name> Ident <weight> int.

and in Scheme:

(define-struct Container (contents capacity))
(define-struct Simple (name weight))

Each container has a capacity and contents which is a list 
of items that are either containers or simple objects.
Each simple object has a weight and the capacity constraint
is violated if the total sum of the weight of the items is greater 
than the capacity.

;; test object definition PL neutral

;; Container c1
;; ( //begin container 1: weight 6: over weight
;; apple 1 //item
;;   ( //begin container 2; weight 2: over weight
;;   pencil 1 //item
;;    ( //begin container 3: weight 1
;;    apple 1 //item
;;    1) //capacity
;;  orange 1
;;  1) //capacity
;; orange 1
;; kiwi 1
;; 5) //capacity


;; Test object c1 in Scheme
(define c1 (make-Container 
           (list (make-Simple "apple" 1)
                 (make-Container 
                  (list (make-Simple "pencil" 1)
                        (make-Container
                         (list (make-Simple "apple" 1))
                         1)
                        (make-Simple "orange" 1))
                  1)
                 (make-Simple "orange" 1)
                 (make-Simple "kiwi" 1))
           5))
c1

;; check returns the total number of capacity violations in a container
;; check: Container -> int

(define (check container)
  (local (
  (define s (sum_Container container)) 
  (define c (check_contents (Container-contents container))))
  (if (> s (Container-capacity container)) (+ 1 c) c)))

(define (sum_Container c) (sum_contents (Container-contents c)))
;; following incomplete
(define (sum_contents l) (foldr + 0 (list 1 3 1 1)))
(define (check_contents l) 100)
(check c1)

;; test
(= (check c1) 2)