[PRL] Accumulator for container capacity

Karl Lieberherr lieber at ccs.neu.edu
Fri Sep 23 09:39:24 EDT 2005


Hi Will and PRL:

I have rewritten the code combining Matthias' and Mitch'
approaches and trying to achieve what Will calls "better separation of
concerns".
A question to Will: where is the best place to read about fold and
linearlizable data types and functional visitors?

Temporarily I achieve better separation of concerns by duplicating Matthias'
code and using the set-*! to store the function results in the Container
structure:

(define-struct Container (contents capacity tweight tviol)) 

In tweight I store the total weight and in tviol I store the total number of
violations.

I define two functions, store-weights and store-viols that leave the results
of their work in the containers. Because both are summing functions,
store-weights and store-viols are very similar and in a later step we will
apply abstraction to eliminate the differences and factor out the common
part.

Of course, this solution also runs fold twice over a structure as big as the
original container. In that sense it is similar to Mitch's: He computes a
pair in one method and I compute the two elements of the pair with two
separate but very similar functions.

I like my approach because store-weights is useful in its own right.
store-viols depends on store-weights running first.

In my solution, the weight-adding-concern is coded in function
store-weights, the violation-adding-concern is coded in function
store-viols.
There is a second concern that I call concern X for lack of a better name
and that is about what is common to store-weights and store-viols.
We will factor that out later.

Does this satisfy the good separation of concerns principle that Will
brought up?

-- Karl

;; store weights and violations
(define-struct Container (contents capacity tweight tviol)) 
(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.

;; --- MF added ---
;; A Container is (make-Container (Listof Item) Number).
;;
;; An Item is one of:
;;  -- (make-Simple Symbol Number)
;;  -- Container
;; --- end added ---

;; Test object c1 in Scheme

;; --- MF changed ---
(define c-1
   (make-Container (list (make-Simple "apple" 1))
                   1 0 0))

(define c0
   (make-Container (list (make-Simple "pencil" 1)
                         c-1
                         (make-Simple "orange" 1))
                   1 0 0))

(define c1
   (make-Container (list (make-Simple "apple" 1)
                         c0
                         (make-Simple "orange" 1)
                         (make-Simple "kiwi" 1))
                   5 0 0))
;; --- end changed ---

;; store-weights adds the total weight to each container;
;; store-viols adds the total number of capacity violations  to each
container 

(define (store-weights ac)
   (local (;; Container -> Number
           ;; the weight of a container
           ;; effect: the number of capacity violations in a container
           (define (weight-container ac)
             (local ([define witems (weight-loi (Container-contents ac))])
;;              Matthias
;;               (when (> witems (Container-capacity ac))
;;                 (set! violations (+ 1 violations))) witems))
               (set-Container-tweight! ac witems)
               witems
               ))
           ;; (Listof Item) -> Number
           ;; the weight of a list of items
           (define (weight-loi l)
             (foldr + 0 (map weight-item l)))
           ;; Item -> Number
           ;; the weight of an item
           (define (weight-item l)
             (cond
               [(Simple? l) (Simple-weight l)]
               [(Container? l) (weight-container l)]))
           ;; Number
           ;; the number of violations detected
;;           (define violations 0)
           )
     (weight-container ac)
     (Container-tweight ac)))

;; store-weights copied and modified
;; BAD, but we can eliminate the duplication later
(define (store-viols ac)
   (local (;; Container -> Number
           ;; effect: the number of capacity violations in a container
           (define (viol-container ac)
             (local ([define vitems (viol-loi (Container-contents ac))]
                     [define vitems-mod 
                       (if (> (Container-tweight ac) (Container-capacity
ac))
                          (+ 1 vitems) vitems)])            
               (set-Container-tviol! ac vitems-mod)
               vitems-mod
               ))
           ;; (Listof Item) -> Number
           ;; the violations of a list of items
           (define (viol-loi l)
             (foldr + 0 (map viol-item l)))
           ;; Item -> Number
           ;; the violations of an item
           (define (viol-item l)
             (cond
               [(Simple? l) 0]
               [(Container? l) (viol-container l)])))
           ;; Matthias
           ;; the number of violations detected
;;           (define violations 0))
     (viol-container ac)
     (Container-tviol ac)))
;; test
(store-weights c1)
;; (store-viols c1)
(= (store-viols c1) 2)

-----Original Message-----
From: William D Clinger [mailto:will at ccs.neu.edu] 
Sent: Thursday, September 22, 2005 4:09 PM
To: ethan.aubin at pobox.com; lieber at ccs.neu.edu
Cc: PRL at lists.ccs.neu.edu; will at ccs.neu.edu
Subject: Re: [PRL] Accumulator for container capacity

> Hi PRL, If you interested here's the code I sent to Karl. The 3 folds
> from Mitch's check function (counting map) are fused together and the
> intermediate lists are removed. Cheers -- ethan.aubin at pobox.com

I vote for Ethan's version.

The visitor pattern would have been even better, though.

Will





More information about the PRL mailing list