Using racket structs for summing elements at even and odd positions

Question

In class we wrote an interpreter for a made up language (lanG) using the following racket structs.

(struct const (n))
(struct bool (b))
(struct join (e1 e2))
(struct if-then-else (b e1 e2)) 
(struct negate (e)) 
(struct add (e1 e2))
(struct multiply (e1 e2)) 
(struct head (e))   ;returns the head of the list
(struct tail (e))    ;returns the tail of the list 
(struct biggerThan (e1 e2))

Macros for this language are defined as racket functions. A simple example would be:

(define (threeTimes x)
   (add x (add x x)))

And using it would look like:

(lanG (threeTimes (const 3)))

which would produce an answer:

(const 9)

Now to my problem. There was a task on the exam where we had to write a macro sumAtEvenAndOdd, which would sum a list of lanG constants, made with the join struct and return a pair of values consisting of the sum of elements at even positions and the sum of elements at the odd positions.

An example of such a list would be:

(join (const 3) (join (const 2) (const 5))) ;lanG list with no null at the end

And its result would be:

(join (const 2) (const 8))

I tried solving this by converting the list into a racket list, ziping the positions with the elements, filtering the odd or even elements out of the list, and producing the pair using the sums of those lists. This works but I am overcomplicating. Professor said the solution is about 5 lines long.

I thank you in advance for all your help.

Yes, it is a procedure/interpreter, which parses the program written with the above structs. Sorry, but I would rather not post the source so I won't get in trouble. The main thing I'm interested in is, how would I loop through souch a list. Usually a list would end with null or something so one would know when to stop recursing on it. — TheAptKid

molbdnilo molbdnilo · Accepted Answer · 2014-08-25T12:17:16

I assume there are also predicates to identify a const and a join - let's call them const? and join?.

Supposing we had a function for adding up every other item of a list, sumAtEvenAndOdd could look like this:

(define (sumAtEvenAndOdd xs)
  (join (sumEveryOther (tail xs)) (sumEveryOther xs)))

and then sumEveryOther could be implemented like this:

(define (sumEveryOther x)
  (if-then-else (const? x)
                x
                (if-then-else (join? (tail x))
                              (add (head x) (sumEveryOther (tail (tail x))))
                              (head x))))

This is of course not optimal, since it traverses the list twice, but it's short ("exam-size") and implemented entirely within lanG.

A slightly longer solution that only traverses the list once, using accumulators:

(define (sumEvenOdd x evens odds odd?)
  (if-then-else (const? x)
                (if-then-else odd?
                              (join evens (add odds x))
                              (join (add evens x) odds))
                (if-then-else odd?
                              (sumEvenOdd (tail x) evens (add (head x) odds) (negate odd?))
                              (sumEvenOdd (tail x) (add (head x) evens) odds (negate odd?)))))


(define (sumAtEvenAndOdd xs)
  (sumEvenOdd xs 0 0 (bool #t)))

Using racket structs for summing elements at even and odd positions

3 Answers