Run length encoding of a list in scheme (R5RS)

Question

(Question Details image -- describes RLE encoding)

The (if ((equal? (car coins) (cadr coins))) piece of code in my rle function is not working, and the function stops working.

 (define (element-index  lst element)
  (let loop ((counter 1) (temp lst))
    (if (= element (car temp))
        counter
        (loop (+ counter 1) (cdr temp)))))

 (define (rle coins)
   (cond ((null? coins) '()))
      (if ((equal? (car coins) (cadr coins)))
          (rle (cdr coins))
           (append '( cons (element-index (coins) (car coins)) (car coins))
                   '( cons (rle (cdr coins))))))

score 2 · Answer 1 · 2020-10-31T17:36:28.710

I'm not going to answer how to solve the problem of run-length encoding something, but the basic syntax problem.

The summary of this is: in many programming languages, and often in mathematical notation, parentheses serve to control the order of operations, and are often more-or-less optional. So for instance 1 + 2 * 3 probably means 'multiply 2 by 3 then add 1 to the result', while (1 + 2) * 3 means 'add 1 and 2 and then multiply the result by 3'. But 1 + (2 * 3) means the same as 1 + 2 * 3 which means the same as (((1 + (2 * 3)))).

This is not the case in Scheme or Lisp-family languages, ever. In these languages parentheses are part of the syntax of the language and they are never optional: they must either be there, or they must not be there.

So, in particular, a simplified version of the syntax of an expression in Scheme might be: an expression is either

some atomic thing like a variable reference;
a form like (op ...), where op is some operator.

In the second case the parentheses are not optional: they are part of the syntax of the language. And in particular if you consider an expression like

((foo ...))

then this matches the second case, where op is now (foo ...) as a whole (and there are no arguments), and that in turn again matches the second case where op is foo. So this is an expression, whose operator is another expression, and the operator of that expression is foo: it's not an expression wrapped in some optional parentheses, and in particular it is not the case that ((foo ...)) is the same as (foo ...).

So then, the syntax of if is: (if expression consequent alternate). Well, let's look at your if:

(if ((equal? (car coins) (cadr coins)))
    ...
    ...)

So the expression here is ((equal? (car coins) (cadr coins))). Well this matches the (op ...) case where op is (equal? (car coins) (cadr coins)), and this in turn matches that case, so it will evaluate this to return either #tor #f. So the expression is the same thing as (#t) or (#f). And #t or #f are Booleans: they're not things you can call as functions.

And that's at least one of the errors in your code. There are others, but this seems to be the most important one, as it's also an error you've made in a comment to another answer.

In summary: parentheses are never optional in Scheme: they are either required or forbidden by the syntax of the language.

Another way of putting this is that, in a 'conventional Algol-style' language, parentheses usually serve two purposes:

they serve as critical and mandatory parts of the syntax, usually for function arguments as f(x, ...), but sometimes also for other syntactic purposes as if (...) ... in C say;
they serve to group expressions to control evaluation order where they are sometimes needed but often optional.

In Lisp-family languages only the former purpose exists.

or, to put is shorter, what's `op(a, ...)` in JS, is `(op a ...)` in Lisp. so Lisp's `((op ...))` is JS's `op(...)()`. — Will Ness, Oct 31 '20 at 13:55
@WillNess: yes, but critically what would be `(op(a, ...))` in JS is not even possible (or ever needed) in Lisp (well `(begin (op a))` perhaps, but, not really, because that's more like what would be `{op(a, ...)}` if JS was an expression language). See edit at the end. — , Oct 31 '20 at 17:31

Run length encoding of a list in scheme (R5RS)

1 Answers1