If i know how a traced output looks, how can i begin creating my function? (Scheme)

Question

I'm having a very hard time trying to learn to program in scheme. My professor says I keep falling into the trap of procedural thinking. I know he's right. I want to learn how to do this, however, reading books is becoming counter intuitive for me as these are supposed to be easy projects that shouldn't require a lot of reading and research anyways.

Conceptually, I understand how my traced function should look. (Although I might be wrong) Here in this case I’m working on a program called ndelete which takes in a list and returns the list with every nth element removed.

Below I’ve traced what I think my function should look like.

ndelete( '( a b c d e) 2)
(a b c d e)
> (b c d e)
> > (c d e)
> > > (d e)
> > > > (e)
> > > > > ( ) 
< < < < < ( ) ; return null
< < < < (e) ; return e 1
< < < (e) ; return 'd 2 removed 'd, 
< < (c e); return 'c 3
< (c e) ; return 'b 4 removed'b
(a c e) ; return 'a 5

I feel like I should know this easily, and it is very frustrating. Perhaps, someone could point me in the right direction or show me how I can utilize what I understand conceptually.

Here is my attempted code. I sort of haphazardly put it together using some example code that I thought I could use from my professor's examples.

(define x '(1 2 3 4 5 6 7 8 9 10))

(define ndelete(lambda (alist n)
                 (if '()
                     (car alist)
                     (ndelete (cdr alist)
                              (- n 1))
                     )))

(ndelete x 10)

Answer 1

It is a common practice to try to generalize from an example, provided:

1. You example is not too constrained. You want to be sure to cover all functional cases. A trace is good for that since the different cases occur generally at different depths for a recursive function. Also, you might need to try multiple examples to trust your solution.

2. you are confident that the trace represents an actual possible execution and is not just badly fabricated (e.g. skipping a step or returning suddenly a different result). You have keep in mind that the trace could be badly formed. You will eventually find out whether this is true by inspecting it closely and confronting your function with your examples.

Don't try to write everything at once, build your function step-by-step from what you see and can infer. I believe most experienced functional programmers still do the below steps, but maybe only in their heads (with time, patterns will start to emerge).

Here, you know that you are given a list and a number: you call them lst and n, because that's how everybody else does in Scheme. You also know that the function should return a list.

(a b c d e)
> (b c d e)
...
< (c e)
(a c e)

• The second line from the top tells you that you should call the function recursively with (cdr lst), for the list argument.
• The last line shows that you have to cons (car lst) on top of the resulting value.

You can write a first draft:

(define ndelete
  (lambda (lst n)
    (cons (car lst) (ndelete (cdr lst) n))))

But this is not enough, because your function does not explain other parts of the trace, like this:

> > > > > ( ) 
< < < < < ( )

Obviously there should be a base case for the empty list. We update the function:

(define ndelete
  (lambda (lst n)
    (if (null? lst) 
      '()
      (cons (car lst) (ndelete (cdr lst) n)))))

Here is another inconsistency:

> > > (d e)
> > > > (e)
....
< < < < (e)
< < < (e)

You don't always cons. In fact, you do it only when you have an even number of < in the trace, which corresponds to an even number of > when calling the function. You understand that 2 should be generalized to n and that you have to add a counter.

You might be tempted to reuse the existing n, but for a first draft, add another parameter. If really it can be derived from n, you'll have an opportunity to rewrite later. Necessarily, the counter must be passed (and modified) from one level to another. I won't copy-paste it here, but the result is Chris Jester-Young's answer. He uses a local function but that is the kind of refactoring that can be done afterwards.