For-loop in scheme

Question

I want to define a for-n function in scheme that takes 3 parameters, start and stop are integers and fn is a function. I want the for-n function to call fn with start then start+1 ... and in the end with stop.
Also I want to store all the values fn returns in a list. Please help me get started. I am an experienced programmer but have just starting learning scheme.

This is the function definition I got:

[edit]

    (define (fn a)
        a
     )

    (define (for-n start stop fn)
      (cond
        ((> start stop) (quote ()))
        ((= start stop) (list(fn start)))
        (else (list(for-n (+ start 1) stop fn))) 
       )
     )


    > (for-n 3 5 fn)
    (list (list (list 5)))

When (for-n 3 5 fn) is called, I want it to return (3 4 5), what am I doing wrong?

[edit-2]
Thanks for the help everyone. I got function working now. Here is what I got:

    (define (for-n start stop fn)
      (cond
        ((> start stop) (quote ()))
        ((= start stop) (list(fn start)))
        (else (cons (fn start) (for-n (+ start 1) stop fn))) 
       )
     )

Solution 1

You seldom want to use list to recursively construct lists. Lists are built with cons and null (aka '()); list is just a convenience function to create a fixed sized list.

(list 1 2 3) = (cons 1 (cons 2 (cons 3 null)))

You should only have two cases in your cond clause: either you're done or you aren't.

Examples help. In particular, pick examples that are related by your recursive calls. You included the example (for-n 3 5 fn). What about (for-n 4 5 fn); what should it return? Now, given start = 3, stop = 5, and (for-n 4 5 fn) = whatever you think it should produce, how can you construct the answer you think (for-n 3 5 fn) should produce?

I highly recommend How to Design Programs (text available online) as an introduction to functional programming.

Solution 2

Here's a solution that uses SRFI 1:

(define (for-n start stop fn)
  (map fn (iota (- stop start) start)))

If this is for homework, then it's up to you to define iota, and perhaps map also. :-D

---

Another solution using a different strategy (also uses SRFI 1):

(define (for-n start stop fn)
  (unfold-right (lambda (x) (< x start))
                fn sub1 (sub1 stop)))

where sub1 == (lambda (x) (- x 1)). Of course, you have to implement unfold-right yourself, in this case.

---

Hopefully from the above two example solutions, you have enough ideas to build your own from-scratch solution. :-)

Solution 3

I'm new to scheme too, but here's what I came up with for a generic for loop that seems to work for me:

(define (for i end-cond end-fn fn var)
    (if (end-cond i)
      var
      (for (end-fn i) end-cond end-fn fn (fn var))
    )
)

So the canonical:

for (i=0; i > 5; i++) {
  print i;
}
return i;

Can be written as:

(define i 0) (for i (lambda (x) (> 5 x)) (lambda (y) (+ 1 y)) display i)

...and you can see why the paradigm doesn't translate well, though you can replace those lambdas with named functions to make it more readable.

--

Self-edit 2015:

This is awful, and the wrong way to do functional programming. A 'map' or 'fold' based approach is much better.

Comments

[Ryan Culpepper]

Try deleting the (= start stop) case. Do your tests still pass?

[C. K. Young]

Glad to hear you got it working. You should still remove the (= start stop) line; it makes your function ~5 times uglier than it needs to be. (If this were homework, and I were the marker, I would dock you points off for having that line, because it demonstrates that you Don't Get Recursion™.)

[Marcin]

This isn't java. Don't format your code like it's java.

[Admin]

In addition to Marcin’s comment: There are some nice style guides for Scheme/Common-Lisp on the web. Cf. eg. mumble.net/~campbell/scheme/style.txt and google-styleguide.googlecode.com/svn/trunk/lispguide.xml.

[jamesio]

I want to build the function from the basic built-in functions. Dont want to use any outside libraries.

[C. K. Young]

@jamesio: I agree. Write those functions yourself. :-) (This question is too homework-like for most SO users to want to write you a straight-up code solution; such answers tend to get downvoted through the floor.)

[C. K. Young]

@jamesio: Hint: both map (which is a Scheme built-in, BTW) and iota are really easy to write. But you should write them yourself; discovering how to do it is a very enlightening learning experience.

[jamesio]

Please look at my code in the edit and comment. I really appreciate your help.

[C. K. Young]

@jamesio: 1. Do you know how to use cons? If you use cons, you will very quickly spot a bug in your default branch. 2. You should remove the second branch of the cond. Let the (= start stop) case fall through to the default, and let the first case trigger upon the next iteration.