How do you implement a simple list iterator in scheme?-CodePudding

I'm trying to compare entries in a list of lists in Scheme using just the basic functions (car, cdr, cons, etc) but can't figure out how to iterate over a list. I tried writing this:

(define (iterate L X)
    (cond ((null? L) '())
          ((> X 0) (iterate ((cdr L) (- X 1))))
          ))

but I'm not sure why it doesn't work. My thinking is that iterate will just return the list of lists after n cdr's. So for example I'm trying to get:

(iterate ( ((10 20) (20 30) (30 40) (40 50)) '2)) -> ((30 40) (40 50))
(iterate ( ((10 20) (20 30) (30 40) (40 50)) '3)) -> ((40 50))

This is the error I get, no clue what it means:

*** ERROR: invalid application: (20 30)
Stack Trace:
_______________________________________
  0  (20 30)
        At line 45 of "./main.sc"
  1  ((10 20) (20 30) (30 40) (40 50))
        At line 45 of "./main.sc"
  2  (((10 20) (20 30) (30 40) (40 50)) '3)
        At line 45 of "./main.sc"
  3  (iterate (((10 20) (20 30) (30 40) (40 50)) '3))
        At line 45 of "./main.sc"

Any help is appreciated. Thanks!

CodePudding user response：

There are two fundamental problems:

You don't surround function arguments with parentheses in Scheme; the syntax is (function arg1 arg2), not (function (arg1 arg2)). The latter first applies the procedure arg1 to arg2, then passes the result of that to function.
((10 20) (20 30) (30 40) (40 50)) does not create a list, it tries to apply the procedure (10 20) to the arguments (20 30), (30 40) and (40 50). Your implementation evaluates the first argument – (20 30) – first, before (10 20), and this tries to apply 20 as a procedure to the argument 30. This is the "invalid application".
(If the procedure had been evaluated first you would have seen "invalid application: (10 20)".)

You need to either quote your list argument or use the list procedure.

Fixing these two problems gives

(define (iterate L X)
    (cond ((null? L) '())
          ((> X 0) (iterate (cdr L) (- X 1)))))

and

(iterate '((10 20) (20 30) (30 40) (40 50)) '3)

Now you only need to fix the problem that occurs when X reaches zero before the list is empty...

CodePudding user response：

Basically all control flow in Scheme, even the ones in the report, are syntax sugar for recursive procedures. Eg. when you would have written this in JS:

const arr = [];
for (let e of lst) {
  arr.push(e*2);
}
return arr;

In Scheme you would have written it like:

(define (loop lst acc)
  (if (null? lst)
      (reverse acc)
      (loop (cdr lst) (cons (* (car lst) 2) acc))))
(loop lst '())

And we have even a syntax sugar that does this more clearly:

(let loop ((lst lst) (acc '()))
  (if (null? lst)
      (reverse acc)
      (loop (cdr lst) (cons (* (car lst) 2) acc))))

In JS we have Array.forEach, Array.reduce and Array.map. In Scheme we have for-each, fold-left, fold-right, and map. eg. The code above can be written like this in JS:

[1, 2, 3, 4].map(v => v*2); // ==> [2, 3, 6, 8]

In like this in Scheme:

(map (lambda (v) (* v 2)) lst) ; ==> (2 3 6 8)

So I'm guessing you cannot use these list procedures, but you can create it by yourself or do roll your own recursion like my first example.