EoPL Exercise 1.36

Questions & Answers
1

Hello,

I’m reading EoPL and I’m stuck in the 1.36 exercise.

Write a procedure g such that number-elements from page 23 could be defined as:

(define number-elements
  (lambda (lst)
    (if (null? lst) ’()
      (g (list 0 (car lst))
         (number-elements (cdr lst))))))

(number-elements ‘(a b c d))
=> ‘((0 a) (1 b) (2 c) (3 d))

I really can't figure out how to solve this problem. I tried with an imperative approach but it didn’t work.

Matteo

1 Like
2

I'm not reading this book but I think I've found a solution.

> (define (g r l)
    (cons r (map (lambda (e) (list (add1 (car e)) (cadr e))) l)))
> (define number-elements
      (lambda (lst)
        (if (null? lst) '()
          (g (list 0 (car lst))
             (number-elements (cdr lst))))))
> (number-elements '(a b c d a))
'((0 a) (1 b) (2 c) (3 d) (4 a))
1 Like
3

I would take an equational approach: what must be true of (g (list 0 (car lst)) (number-elements (cdr lst))) when lst is '(a)? What about '(a b) or '(a b c)? Now generalize to (cons x xs). You'll have to expand definitions; for '(a), perhaps something like this

  (number-elements '(a))
= (g (list 0 'a)
     (number-elements '()))
= (g '(0 a) '())
= ???
= '((0 a))

and for '(a b)

  (number-elements '(a b))
= (g (list 0 'a)
     (number-elements '(b)))
= (g '(0 a)
     (g '(0 b) '()))
= ???
= '((0 a) (1 b))

That last example makes g look an awful lot like a cons operator that also does some counting/addition, doesn't it? Try again with 3 elements, and then see if you can generalize. You're looking for equations about g that have to be true, and then you can build an implementation that satisfies those requirements (if you have to guess at an implementation, it's a good idea to prove to yourself that it meets all the equational requirements). Don't forget the order of evaluation: in the last example, (g '(0 b) '()) is evaluated before the outer call to g.

2 Likes
4

I have put together an explanation of how to go about solving this kind of problem. I wrote it as a literate program, and had hope to make it more readable, but GitHub is not displaying the Scribble output properly. You can find the Scribble source in raw form at eopl-1.36.scrbl.

Copy and paste the Scribble code into DrRacket, and click on "Scribble HTML" to generate the documentation. Click on "Run" to run the program.

[GitHub is eliminating the chunk names. If anyone is interested in exploring why GitHub doesn't like the Scribble output, let me know.]

5

For the impatient, here is the code of my solution. You can read the Scribble if you want to understand how I developed it.

#lang racket

(define number-elements
  (lambda (lst)
    (if (null? lst)
        '()
        (g (list 0 (car lst))
           (number-elements (cdr lst))))))

(define g
  (lambda (first numbered-elements)
    (cons first (map (lambda (elt)
                       (cons (add1 (car elt)) (cdr elt)))
                     numbered-elements))))

Welcome to DrRacket, version 8.15 [cs].
Language: racket, with debugging; memory limit: 4096 MB.

(number-elements '(a b c d))
'((0 a) (1 b) (2 c) (3 d))

1 Like