How to Solve EoPL Exercise 1.36

eopl-1.36.scrbl

#lang scribble/lp2

@title{Solving EoPL Exercise 1.36}
@author[(author+email "Justin Zamora" "[email protected]")]

@section{The Problem}

The exercise is to write a procedure @racket[g] such that number-elements from page 23
could be defined as:

@chunk[<number-elements>
(define number-elements
  (lambda (lst)
    (if (null? lst)
        '()
        (g (list 0 (car lst))
           (number-elements (cdr lst))))))]

@section{Analysis}

What is this @racket[number-elements] function? What does it do? What does in consume, and what does
it produce? We cannot know what @racket[g] is supposed to do until we understand
@racket[number-elements].

We are given one example:

@racket[(number-elements '(a b c d))
=> '((0 a) (1 b) (2 c) (3 d))]

From this example, it seems that @racket[number-elements] consumes a list of symbols
and produces a list of ``elements''. Each ``element'' is a list of one of
the symbols and its position in the list, numbered beginning at 0.

@racket[g] is given a zero element made from the first symbol in the list, and the
output from @racket[number-elements] run on the rest of the list.

Therefore, in our example, the top-level call to @racket[g] looks like:

@racket[(g '(0 a) <numbered-elements>)]

Because we've already figured out what @racket[number-elements] does, we know that
the second argument to @racket[g] is the rest of the original list,
numbered from zero:

@chunk[<numbered-elements>'((0 b) (1 c) (2 d))]

Looking at this, we can see that the task of @racket[g] is to add one to the counter
of each element in the second list and @racket[cons] the first argument onto the
result.

So @racket[g] must look like this:

@chunk[<g>
(define g
  (lambda (first numbered-elements)
    (cons first <add-one-to-numbered-elements>)))]

Now that we have broken down @racket[g], we have the smaller task of adding one to
each of the elements in the list. The @racket[map] function seems like a natural
fit here. So we want something like:

@chunk[<add-one-to-numbered-elements>
       (map <add-one-to-single-element> numbered-elements)]

To add one to a single element, we need to extract the count from the @racket[car] of
the element, add one to it, then @racket[cons] the result back onto the rest of the element:

@chunk[<add-one-to-single-element>
       (lambda (elt)
         (cons (add1 (car elt)) (cdr elt)))]

We have completed our function, but we need to test it. At the very least, we should
make sure that our code gets the example right. I have included it below, but you
should add more to verify that it actually works on a variety of inputs. Pay special
attention to edge cases like an empty list.

@chunk[<tests>
       (number-elements '(a b c d))]
       
@section{Reflection}

It's worth taking a look at how we approached this problem so that we can learn to
solve other problems in the future. Instead of immediately trying guesses, we used a
disciplined approach to understanding the problem and creating a solution. Roughly
speaking, we performed the following tasks, which led us, step-by-step, toward the
solution.

@itemlist[
@item{Using an example to understand the task}
@item{Defining the inputs and outputs}
@item{Breaking down the problem into pieces}
@item{Transforming the pieces}
@item{Combining the results into the solution}
@item{Testing}]

You may notice that these steps are similar to those taught in
@hyperlink["https://htdp.org/"]{How to Design Programges} as part of the
design recipes. HTDP gives a more rigorous and formal presentation, but this
exercise shows how useful good design practices can be.

@section{Final Answer}

@chunk[<*>
       <g>
       <number-elements>
       <tests>]