Racket recursive function for returning the sum of a list of squared numbers

Question

I am new to Racket, and I am trying to write a recursive function that takes a number n and returns the sum of the squares of the first n integers. For example, (this-function 3) returns 14 because 14 is 9 + 4 + 1 + 0.

I tried creating two separate functions, one that squares each number and returns a list of the squared numbers, and a second that sums up the list. The function the squares each number is:

(define (squared my-list)
  (cond [(empty? my-list) empty]
        [(zero? my-list) 0] 
        [else (cons (expt  my-list 2)
                    (cons (squared   (sub1 my-list)) empty))]))

which if I run (squared 3) returns (cons 9 (cons (cons 4 (cons (cons 1 (cons 0 empty)) empty)) empty)).

When I run the second function (the sum function):

(define (sum numbers)
  (cond
    [(empty? numbers) 0]
    [else (+ (first numbers) (sum (rest numbers)))]))

and run (sum (squared 3)) I get an error message because (squared 3) returns an extra "cons" in the list.

How can I fix this?

This sounds like homework. Are you permitted to use functions like foldl and map? — Alexis King
It is. I've come this far, but still suck because of the extra cons. And no we haven't learned foldl and map. — Ryan

Alexis King Alexis King · Accepted Answer · 2015-02-13T04:37:26

Your logic in squared is a little bit off. I'll explain the issues clause-by-clause.

[(empty? my-list) empty]

This doesn't make any sense since my-list will never even be a list. In fact, my-list is poorly named. The parameter squared takes is a number, not a list. This clause can be completely removed.

[(zero? my-list) 0]

This is what the actual terminating case should be, but it shouldn't return 0. Remember, squared has to return a list, not a number. This case should return empty.

[else (cons (expt my-list 2)
            (cons (squared (sub1 my-list)) empty))]))

Finally, this clause is far too complicated. You have the right idea—to cons the new number onto the rest of the list—but you're cons'ing too many times. Remember, the result of (squared (sub1 my-list)) is itself a list, and the second argument of cons is the rest of the list. You don't need the extra cons—you can just eliminate it completely.

Combining these changes, you get this, which does what you want:

(define (squared my-list)
  (if (zero? my-list) empty
      (cons (expt my-list 2)
            (squared (sub1 my-list)))))

(I also replaced cond with if since cond is no longer necessary.)

That said, this code is not very Racket-y. You had a good idea to break up your function into two functions—in functional programming, functions should really only ever do one thing—but you can break this up further! Specifically, you can leverage Racket's built-in higher-order functions to make this type of thing extremely easy.

You can replace your entire squared function by appropriately combining map and range. For example, the following creates a list of the squares from 0–3.

(map (curryr expt 2) (range 4))

(You need to call (range 4) because the list generated by range goes from 0 to n-1.)

Next, you can easily sum a list using apply. To sum the above list, you'd do something like this:

(apply + (map (curryr expt 2) (range 4)))

That gives you the appropriate result of 14. Obviously, you could encapsulate this in its own function for clarity, but it's a lot clearer what the above code is doing once you learn Racket's functional constructs.

(However, I'm not sure if you're allowed to use those, since your question looks a lot like homework. Just noted for future reference and completeness.)

Racket recursive function for returning the sum of a list of squared numbers

3 Answers