Recursively adding to a list using Scheme

Question

I'm brand new to functional programming, and relatively new to programming as a whole. So I'm pretty lost trying to understand the syntax of Scheme. But this is a pretty simple question. I'm trying to create a function that recursively fills and prints a list from numbers x to y. Between recursion and this being a new language for me, I'm quite stuck.

 (define (gen-list x y)

  (if (> start end)

      '()

      (append '() (gen-list ((+ 1 x) y)) ) ))

If I were to enter in (gen-list 1 5) I would expect the result to be 1 2 3 4 5. This is currently giving me an error of "application: not a procedure" when it tries to call itself again. I have gotten around the error, but not been able to print anything remotely like what I'd like to. Any help is appreciated.

Answer 1

Just adding tail call recursive version

(define (gen-list start end (acc '()) #:step (step 1))
  (cond ((> start end) (reverse acc))
        (else (gen-list (+ start step) end (cons start acc)))))

Personally I love cond because you have all the conditions then below each other (or an else) - this is the style of The little Schemer a very good book for learning recursive thinking.

Answer 2

One of the problems with the 'obvious' answer to this question is that it doesn't really work very well. Consider this:

(define (gen-list start end)
  (if (> start end)
      '()
      (cons start
            (gen-list (+ start 1) end))))

Well, if start is much less than end there are going to be a huge number of recursive calls on the stack, because this is a properly recursive function: the recursive call to gen-list is a real call and has to return before the call to cons (which is a tail call) can happen.

The way to deal with this is to turn patterns which look like (cons x (<recursive-call> ...)) into patterns which look like (<tail-call> ... (cons x ...)): you need a function with an extra argument, an accumulator. This means that the calls which were previously recursive are now tail calls and everything is therefore good: the process is now iterative.

The problem with this is that lists come out backwards (you need to think about why this is, but it's obvious after a bit of thought). So you then need to reverse the result. Fortunately reversing a list is also an iterative process, so that's OK.

But in this case, well, you can just count backwards! So a simple-minded approach looks like this, using a locally-defined auxiliary function (this can be defined as a top-level function, but why bother?):

(define (gen-list low high)
  (define (gla i result)
    (if (< i low)
        result
        (gla (- i 1) (cons i result))))
  (gla high '()))

You can see this is counting backwards: the initial call to gla starts with high & then constructs the list backwards. So, now:

> (gen-list 1 3)
'(1 2 3)

As we want.

This is such a common pattern in Scheme that there is a special construct for it: named let. So we can rewrite the above more idiomatically as:

(define (gen-list low high)
  (let gla ([i high] [result '()])
    (if (< i low)
        result
        (gla (- i 1) (cons i result)))))

This is exactly the same as the previous answer: it just moves the initial call to the top and combines it with the local definition of gla. This is probably the idiomatic Scheme way to do something like this (although people who write more Scheme than me might differ: I'm really a CL person and have inevitably poor taste).

---

This is where the story should end, but I can't resist adding the following. In the bad old days of comp.lang.lisp, people used to ask obvious homework questions and since there was no karma system one approach was to give an answer which solved the problem ... while being absurdly opaque.

So first of all we can turn gla into a function which gets passed a continuation to call rather than knowing it must call itself:

(define (gen-list low high)
  (let ([gla (λ (cont i result)
               (if (< i low)
                   result
                   (cont cont (- i 1) (cons i result))))])
    (gla gla high '())))

And then, of course we can turn (let ([x y]) ...) into ((λ (x) ...) y):

(define (gen-list low high)
  ((λ (gla)
     (gla gla high '()))
   (λ (cont i result)
     (if (< i low)
         result
         (cont cont (- i 1) (cons i result))))))

And that's a nice, pure answer ... which no student would ever come up with.

An alternative approach which is even more malicious is just to explicitly use the Y combinator, of course.

Answer 3

You have a couple of errors:

• The parameters are called x and y, but you refer to them as start and end (I'd suggest to use start and end instead, they make the code easier to understand.)
• You have more parentheses than needed in the last line. This is very important and an endless source of confusion for beginners. Don't surround all expressions with () unless you want to call a procedure.
• We recursively build new lists with cons, append is for concatenating existing lists.
• You're not actually using start, which is the current element in the recursion, to build the new list - you're just appending empty lists.
• A list is an element consed to another list, or the empty list '(). That's why we return '() in the base case. For example, this is how a two-element list looks like: (cons 1 (cons 2 '())).

With all said and done, this is the proper way to build our list:

(define (gen-list start end)
  (if (> start end)
      '()
      (cons start
            (gen-list (+ start 1) end))))

As a final comment: the above procedure already exists in Racket, you don't need to rewrite it. Read about range in the documentation.

Answer 4

You need more than just the (> start end) base case, you also need a (= start end) base case in which you return (list start)