Need a hint on a homework question which asks to add numbers in a list in a particular way

Question

This is a homework question

The function takes in a list as the parameter, which may contain as many layers as sublists as needed For example, '(a (1 b 3)) or '((a 3 5) (b (3 1) 4)). The output has the same list structure of the input (meaning that sublists are maintained), but the car of each list is the sum of all numbers in the list. And all other non-numeric values are discarded. As an example output, consider '((a 3 5) (b (3 1) 4)), the output should be '(16 (8) (8 (4))). Also, only use basic scheme instructions/operations such as + - * /, car, cdr, cons, append, null?, number?, if/else, cond, etc.. Cannot Use a helper method.

So far this is the code I have, which sometimes partially does the job. But I'm having a really hard time figuring out how to get the sum from the sublists to add up at one spot at the car of the outmost list.

(define partialsums*
  (lambda (lis)
    (cond
      [(null? lis) '(0)]
      [(list? (car lis)) (cons (partialsums* (car lis)) (if (not (null? (cdr lis))) (partialsums* (cdr lis)) '()))]
      [(number? (car lis)) (cons (+ (car lis) (car (partialsums* (cdr lis)))) '())]
      [else (cons (+ 0 (car (partialsums* (cdr lis)))) '())])))

I've already spent several hours on this but couldn't quite grasp how to correctly approach the problem, probably because this is my first week using scheme :(. Any help is appreciated.

Also, I cannot use a helper method. Everything needs to be done inside one function in a recursive style. letrec is not allowed either.

A requirement that says "etc." isn't very useful. Is let "basic"? lambda? (IMHO, a requirement that you write code in the most verbose and least convenient way is not very good teaching, unless it's immediately followed by the opposite.) — molbdnilo
you say "all other non-numeric values are discarded" but then show the output where all numeric values are discarded as well, and only the sums remain. is this the output that you want? — Will Ness
Yes, once a number is added to the sum it should be removed. — Isaac

Atharva Shukla Atharva Shukla · Accepted Answer · 2020-01-29T22:36:55

To make life easy, you should model the data. Since there are no types, we can do this informally.

What is the structure of the input?

We can model it like "Data Definitions" from How to Design Programs. Read the "Intertwined Data" section because our data definition is similar to that of an S-expression.

; A NestedElem is one of:
; - Atom
; - NestedList

; An Atom is one of:
; - Number
; - Symbol

; A NestedList is one of
; - '()
; - (cons NestedElem NestedList)

We can define an atom? predicate to help us differentiate between clauses of the kinds of data in our program.

; Any -> Boolean
; is `a` an atom?
(define atom?
  (lambda (a)
    (or (number? a)
        (symbol? a))))

The structure of the program should match the structure of the Data.

So we define a "template" on our data. It distinguished and destructs each data into clauses. It further de-structures the rhs of a clause.

; NestedElem -> ...
(define nested-elem-template
  (lambda (ne)
    (cond
      [(atom? ne) ...]
      [else ...])))

; Atom -> ...
(define atom-template
  (lambda (atom)
    (cond [(number? atom) ...]
          [(symbol? atom) ...])))

; NestedList -> ...
(define nested-list-template
  (lambda (nl)
    (cond [(null? nl) ...]
          [else (... (car nl)... (cdr nl))])))

We definitely know more about the data. (car nl) in the nested-list-template is of type NestedElem. Therefore we can fill up some ...s with calls to templates that deal with that kind of data. In the same vein, we can wrap recursive calls around expressions of a datatype we know of.

; NestedElem -> ...
(define nested-elem-template
  (lambda (ne)
    (cond
      [(atom? ne) (atom-template ne)]
      [else (nested-list-template ne)])))

; Atom -> ...
(define atom-template
  (lambda (atom)
    (cond [(number? atom) ...]
          [(symbol? atom) ...])))

; NestedList -> ...
(define nested-list-template
  (lambda (nl)
    (cond [(null? nl) ...]
          [else (... (nested-elem-template (car nl))
                     ... (nested-list-template (cdr nl)))])))

Now we can "fill in the blanks".

We can "filter", "map", and "fold" over this data structure. All those can be defined using the template as a scaffold.

Note 1: Your HW asks you to do multiple tasks:

remove the symbols
sum up the numbers
cons the sum onto every list

Don't try to do everything in a single function. Delegate into multiple helper functions/traversals.

Note 2: I did not model the output type. It's the same as input type except that Symbol is no longer an atom.

Need a hint on a homework question which asks to add numbers in a list in a particular way

1 Answers