CS 1101 - Lab 6

Accumulator-Style Programming

Acknowledgements

This lab is a modified version of a lab exercise designed by Felleisen, Proulx, et. al., 2008

Purpose

By the end of this lab, you should be able to:

Designing Programs with Accumulators

In the videos, you looked at two types of problems that use accumulators: context-preserving accumulators and designing tail-recursive functions using accumulators. In this lab, we'll look more closely at the tail-recursive use of accumulators. Accumulator-style programs of this type follow the same set of steps. First, create a helper function that calls the accumulator-style function. In the accumulator-style function, introduce an additional parameter that represents the accumulator. The type of the accumulator should be the same type as the result that you want the function to produce. Next, provide an initial value for the accumulator. This step happens in the call to the accumulator-style function. The initial value is the answer we would expect if we ran the function and no recursive calls occurred (for example, in class yesterday we designed an accumulator-style function that summed all the numbers in a list. If you ran the function on an empty list, you would expect the function to return the value 0. So you initialize the accumulator to 0.)

The templates for the calling function and the accumulator function look like this: 

;; rec-fcn: ListOfX -> Y
;; produce a value of the type Y from the given list of X
(define (rec-fcn alox) 
  (rec-fcn-acc alox initial-acc-value))

;; rec-fcn-acc: ListOfX Y -> Y
;; recur with updated accumulator, unless the end of list is reached
(define (rec-fcn-acc alox acc)
  (cond
    ;; at the end produce the accumulated value
    [(empty? alox) acc] 

    ;; otherwise invoke rec-fcn-acc with updated accumulator and the rest of the list    
    [(cons? alox)  (rec-fcn-acc (rest alox)
                               (update (first alox) acc))]))
where update represents the way you want to augment or alter the accumulator when you process the first element of alox.

Here is a set of problems for which you'll design accumulator-style solutions:

A radio show is represented by the following information: the name of the show, the total running time in minutes, and a list of ads to run during the show, where for each ad we are given its name, the running time in minutes, and the profit it generates in dollars.

Using the Design Recipe, here are the data definitions and programs that model a radio show: 

;; Data definitions

;; Radio Show  (RS) is a (make-rs String Number ListOfAd)
(define-struct rs (name minutes ads))

;; Ad is a (make-ad String Number Number)
(define-struct ad (name minutes profit))

;; a ListfAd is either
;; empty, or
;; (cons Ad ListOfAd)

;; Examples of data:

(define ipod-ad (make-ad "ipod" 2 100))
(define ms-ad (make-ad "ms" 1 500))
(define xbox-ad (make-ad "xbox" 2 300))

(define news-ads (list ipod-ad ms-ad ipod-ad xbox-ad))
(define game-ads (list ipod-ad ms-ad ipod-ad ms-ad xbox-ad ipod-ad))
(define bad-ads (list ipod-ad ms-ad ms-ad ipod-ad xbox-ad ipod-ad))

(define news (make-rs "news" 60 news-ads))
(define game (make-rs "game" 120 game-ads))
  
 

;; compute the total time for all ads in the given list
;; total-time: ListOfAd -> Number 
(define (total-time adlist)
  (cond
    [(empty? adlist) 0]
    [(cons? adlist) (+ (ad-minutes (first adlist))
                       (total-time (rest adlist)))]))

(check-expect (total-time news-ads) 7)
(check-expect (total-time game-ads) 10)

Problems

(If you prefer to use local to define your accumulator-style function in any of the following problems, you may.)
  1. Copy and paste the radio show code into your DrRacket definitions window. Convert the total-time function to total-time-acc that uses an accumulator.

  2. Compute the total profit generated by the ads for a radio show. Write your solution using accumulator-style programming. If you run into difficulty, try writing the solution the standard way by following the design recipe, then convert it into accumulator-style. (If you are running out of time, skip this problem, do it at home, and go on to the last problem.)

  3. The show producer wants to make sure that the list of ads does not repeat the same ad twice without having a different ad in between. So, a list of ads (list ipod-ad ms-ad ipod-ad xbox-ad) is OK, but the list of ads (list ipod-ad ms-ad ms-ad ipod-ad xbox-ad ipod-ad) is not acceptable, because two ms ads are run without a break in between.

    Design a function no-repeat that produces true if the list of ads is acceptable and produces false otherwise. (Hint: this is a context-preserving use of accumulators.)

    Do you need an accumulator here? Why? Can you write the function without one?

Using web-based turnin, turn in your work. Name your file lab6.

Make sure you signed the attendance sheet. See you next week!