[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