How to add in a list in racket

Here's how I would design such a function systematically using parts of the Design Recipe from How to Design Programs.

The input is a list that may contain numbers and lists of numbers. For now I'll assume lists can be nested further than that. With arbitrarily-nested lists allowed, that would make the input a tree of numbers, not just a list.

;; A NumTree is one of:
;;  - Number
;;  - [Listof NumTree]

;; sum : NumTree -> Number
(define (sum nt)
  ???)

The "one of" in the data definition above means the function should use a conditional, with a question for each bullet in the "one of".

;; sum : NumTree -> Number
(define (sum nt)
  (cond [(number? nt) ???]
        [(list? nt) ???]))

The aren't any "sub-parts" in the cases of the data definition, so the next step is finding the references to complex data definitions, including self-references, and inserting helper functions for those. [Listof NumTree] is a complex data definition, so make a helper function for summing that.

First add this function to your "wish list", you'll come back to it later.

;; sum-listofnumtree : [Listof NumTree] -> Number
(define (sum-listof-numtree lont)
  ???)

Now that it's in your wish list, use it to finish defining the rest of sum.

;; sum : NumTree -> Number
(define (sum nt)
  (cond [(number? nt) nt]
        [(list? nt) (sum-listof-numtree nt)]))

Now once that's done go back to your wish list and work on sum-listof-numtree. Again you can base it on the data definition, this time for Listof.

;; A [Listof NumTree] is one of:
;;  - '()
;;  - (cons NumTree [Listof NumTree])

;; sum-listofnumtree : [Listof NumTree] -> Number
(define (sum-listof-numtree lont)
  ???)

Again the "one of" turns into a cond, with a branch for each bullet point.

;; sum-listofnumtree : [Listof NumTree] -> Number
(define (sum-listof-numtree lont)
  (cond [(empty? lont) ???]
        [(cons? lont) ???]))

Here, the cons case has two sub-parts, the first and the rest.

;; sum-listofnumtree : [Listof NumTree] -> Number
(define (sum-listof-numtree lont)
  (cond [(empty? lont) ???]
        [(cons? lont) (.... (first lont) (rest lont) ....)]))

The next step is seeing whether any of the sub-parts are complex data definitions, and if they are, inserting helper functions. In this case both are complex data. (first lont) is a NumTree and (rest lont) is a [Listof NumTree].

The "helper" function for NumTree here is sum, so in the template you can use (sum (first lont)). And the "helper" function for [Listof NumTree] is sum-listof-numtree, so you can use (sum-listof-numtree (rest lont)) for that.

;; sum-listofnumtree : [Listof NumTree] -> Number
(define (sum-listof-numtree lont)
  (cond [(empty? lont) ???]
        [(cons? lont) (.... (sum (first lont)) (sum-listof-numtree (rest lont)) ....)]))

Now just fill in the holes with what makes sense for summing.

;; sum-listofnumtree : [Listof NumTree] -> Number
(define (sum-listof-numtree lont)
  (cond [(empty? lont) 0]
        [(cons? lont) (+ (sum (first lont)) (sum-listof-numtree (rest lont)))]))

Combined, these form a pair of mutually recursive functions, operating on a pair of mutually recursive data definitions.

;; A NumTree is one of:
;;  - Number
;;  - [Listof NumTree]

;; A [Listof NumTree] is one of:
;;  - '()
;;  - (cons NumTree [Listof NumTree])

;; sum : NumTree -> Number
(define (sum nt)
  (cond [(number? nt) nt]
        [(list? nt) (sum-listof-numtree nt)]))

;; sum-listofnumtree : [Listof NumTree] -> Number
(define (sum-listof-numtree lont)
  (cond [(empty? lont) 0]
        [(cons? lont) (+ (sum (first lont)) (sum-listof-numtree (rest lont)))]))

Here is a start:

(define (sum lloi)
  (cond
    [(empty? lloi) 0]
    [(number? (first lloi)) (+ (first lloi) (sum (rest lloi)))]
    [(list?   (first lloi)) ???]))

If (first lloi) is a list, you need to find its sum, and then add it to the sum of the remaining elements.

A little late, but here's my take:

(define (sum lloi)
  (cond
    [(empty? lloi) 0]
    [(number? lloi) lloi]
    [else (apply + (map sum lloi))]))

The input list may contain numbers, empty lists or lists in the same format as the input list. In order to find the sum of this list, we add up all of its element.

• if the element is empty list, add 0
• if the element is a number, add the number
• if the element is a list, first find the sum of this list, then add it (recursion here)

(map sum lloi) applies the function sum to each element of lloi.

(map sum '(a b c d)) => '((sum a) (sum b) (sum c) (sum d))

(apply + list) adds up all elements of the list. You can't just do it like (+ list), because + takes only numbers as arguments, not lists.

(apply + (1 2 3 4)) => (+ 1 2 3 4)

OP problem is an example of a more general class of problems dealing with nested lists, often solved by tree-flattening or list-flattening.

With a nested list, each element is either a list or an atom (ignoring improper lists). A recursive procedure can traverse the input and flatten any encountered sublists, combining the results into a final flattened list.

(define (my-flatten xs)
  (cond ((null? xs)
         '())
        ((list? (first xs))
         (append (my-flatten (first xs))
                 (my-flatten (rest xs))))
        (else
         (cons (first xs)
               (my-flatten (rest xs))))))

Here, if the first element of the input is a list, it is flattened and combined with the result of flattening the rest of the list. Otherwise the first element is not a list, so it is consed onto the result of flattening the rest of the list.

The same pattern can be used to design a procedure that sums all of the elements of a nested list.

(define (my-sum xs)
  (cond ((null? xs)
         0)
        ((list? (first xs))
         (+ (my-sum (first xs))
            (my-sum (rest xs))))
        (else
         (+ (first xs)
            (my-sum (rest xs))))))

One could also make use of the my-flatten procedure to simplify the design of the summation procedure. There are several ways that such a procedure could be designed; here the sum-1 procedure first flattens the input list before using a named let to recursively sum over the simple list.

(define (sum-1 tr)
  (let ((xs (my-flatten tr)))
    (let sum-helper ((xs xs))
      (if (null? xs)
          0
          (+ (first xs)
             (sum-helper (rest xs)))))))

Racket already has a built-in flatten, which indicates that such a procedure might be a useful abstraction. Note that the Racket built-in procedure is more sophisticated than the simple my-flatten defined above; one improvement is that it handles improper lists as well as proper lists.

The flatten procedure really comes into its own when combined with other higher-order procedures that are often used in functional programming styles. OP summation problem can be solved very concisely by using apply or foldl with flatten.

(define (sum-2 tr)
  (apply + (flatten tr)))

(define (sum-3 tr)
  (foldl + 0 (flatten tr)))

Sample REPL interaction:

scratch.rkt> (my-flatten '((1 2) 3 (4 (5 6 (7 8 9) 10)) 11))
'(1 2 3 4 5 6 7 8 9 10 11)
scratch.rkt> (my-sum '((1 2) 3 (4 (5 6 (7 8 9) 10)) 11))
66
scratch.rkt> (sum-1 '((1 2) 3 (4 (5 6 (7 8 9) 10)) 11))
66
scratch.rkt> (sum-2 '((1 2) 3 (4 (5 6 (7 8 9) 10)) 11))
66
scratch.rkt> (sum-3 '((1 2) 3 (4 (5 6 (7 8 9) 10)) 11))
66

(define (sum l)
  (foldl (lambda(x acc) (+ acc (if (pair? x) (sum x) x)))
  0
  l))

 > (sum '(1 2 3 (1 2 3)))
12
> (sum '(1 2 3))
6

Another way in Racket is to use the for/sum comprehension to do all the work of adding and iterating. You just have to (recursively) give it the numbers to add together:

(define (sum lloi)
  (for/sum ([loi (in-list lloi)])
    (cond
      [(integer? loi) loi]
      [(list? loi) (sum loi)])))

(writeln (sum '())) ; 0
(writeln (sum '(1 2 3))) ; 6
(writeln (sum '(1 (2) 3 (4 5)))) ; 15

And a contracted version that enforces the type of its argument at call-time:

;;; An integer or list of (integer or list of ...)
(define loi? (or/c integer? (listof (recursive-contract loi?))))

(define/contract (sum lloi)
  (-> (listof loi?) integer?)
  (for/sum ([loi (in-list lloi)])
    (if (integer? loi)
        loi
        (sum loi))))

(writeln (sum '("foo"))) ; Contract violation