[PRL] Accumulator for container capacity

[Karl Lieberherr]

Hi Mitch:

your solution is violating the constraint of doing the traversal only once.

I think that Matthias wanted to avoid code like:

(define (process-loi l)
(local ((define w (foldr + 0 (map tweight-item l)))
(define v (foldr + 0 (map tviol-item l))))
(cons w v)))

which traverses the contents of the container twice.

But, I would like to have a programming language that allows me to program
just the way you described it. Here is my favorite program:

1. Container // Simple (recursive descent of tree, in XPath)
2. Enhance 1. with summing weights that computes tweight (uses Container //
Simple)
3. Enhance 2. with summing violations that computes tviol (uses Container //
Container)

2. and 3. have the flavor of a super fold over the structure

I think that our goal is not avoiding traversals and avoiding !, it is about
having more intelligible programs.

-- Karl
==================================
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


On 9/21/05, Mitchell Wand <wand at ccs.neu.edu> wrote:
>
> 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