[PRL] Accumulator for container capacity

[Mitchell Wand]

Why not just do a single recursive descent of the tree, returning (#of 
violations, weight of items) ?  No accumulators, no state, not even an 
inherited attribute.

--Mitch

Matthias Felleisen wrote:

> Karl, this container problem is a _perfect_ illustration of when you 
> want state rather than accmulators because you would need to weave the 
> accumulator value through several functions. In other words, it is 
> both an inherited and a synthesized attribute. So here is the set! 
> code, convert it to store passing style is an exercise but beyond our 
> 711 students for now. -- Matthias
>
> (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.
>
> ;; --- 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))
>
> (define c0
>   (make-Container (list (make-Simple "pencil" 1)
>                         c-1
>                         (make-Simple "orange" 1))
>                   1))
>
> (define c1
>   (make-Container (list (make-Simple "apple" 1)
>                         c0
>                         (make-Simple "orange" 1)
>                         (make-Simple "kiwi" 1))
>                   5))
> ;; --- end changed ---
>
> ;; Karl's problem
> ;; check returns the total number of capacity violations in a container
> ;; check: Container -> int
>
> (define (check 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))])
>               (when (> witems (Container-capacity ac))
>                 (set! violations (+ 1 violations)))
>               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)
>     violations))
>
> ;; test
> (= (check c1) 2)
>
>
> _______________________________________________
> PRL mailing list
> PRL at lists.ccs.neu.edu
> https://lists.ccs.neu.edu/bin/listinfo/prl

-------------- next part --------------
HTML attachment scrubbed and removed