[clayton33]

I have to write a Scheme procedure that takes a single list of numbers as an argument and returns a list which is the same as the argument list but with all numbers in even positions multiplied by 2.
For example, (proc7 (list 1 2 3 4 5)) should return (2 2 6 4 10)

I tried the following:

(define procedure(lambda(x) (cons (car x)(cdr x))))

However, I think that the above code only works one time, and I need it to work recursively.
How could I do that?
Do I need more than one procedure?

[jon.kiparsky]

Two procedures will work. You can do it with two functions f and g - g defined within f - which call each other, round robin. However, that's a little less than elegant, as you more or less write the same function twice, with one change. I'm pretty sure you could do it cleaner with a calling function and a nested helper function. However, the f and g approach does in fact work.

[AdamSpeight2008]

This doesn't modify the list but produces new list.

[jon.kiparsky]

Yes. This is normal. Lists are not immutable in scheme, but they should be treated as if they are, particularly in a problem like this one.

[Tayacan]

Alright, so about recursive functions (this is not scheme-specific):

First, you need your base cases - when does the recursion stop? This is usually the simplest case - when working with lists, it's often the empty list or nil. In your case, if your function gets an empty list as input, it should return an empty list.

Now, since you want to do something to every other item, you need one more base case - the singleton, or the list of exactly one item. If you get a list of one item, it's in position 0, so in that case, you should return a list containing the element multiplied by two.

Okay, what if your list has more than one item? Well, then you split up the list into the first item (index 0), the second item (index 1), and the tail. Call your function on the tail (this is the recursion step), cons the second item onto that, and cons the first item, multiplied by two, onto that. At some point, the tail will be the empty list or a singleton, and then the function will return.

[Tayacan]

Edit: I was replying to a post, but it must have been removed...

This post has been edited by Tayacan: 14 November 2012 - 05:54 AM

[clayton33]

I'm assuming the list is not empty, at least has 1 element, so I wrote the code that gives the double of each element of the list.

(define (proc7 x)(if (null? x) '() (cons (* 2 (car x)) (proc7(cdr x)))))

Now, I tried to replace the cdr in the function by cadr, but the procedure crashed. Is there a function in scheme that gives me the position of each element? I don't know how to skip every other element.

[sepp2k]

cadr returns the second element of a list. So if you replace cdr with cadr, you'll get back an element instead of a list, leading to a type error. You could use cddr (which returns all elements of the list except the first two), which would run without error if the list contains an even number of elements, but that would remove even elements instead of keeping them unchanged. It would also cause an error when used with an odd number of elements in the list.

Have you tried Jon's suggestion about defining two functions that call each other? That really seems like the simplest solution.

[mojo666]

The mathy solution is to define a function that takes a list and an integer. This integer will always be 1 or -1. The equation (i+3)/2 will return 2 for i=1 and 1 for i=-1. So, multiply the head times that equation, then recurse on the tail and i*-1. Your main function will call this helper function with the list and 1 as inputs.

[jon.kiparsky]

clayton33, on 14 November 2012 - 07:15 PM, said:

Now, I tried to replace the cdr in the function by cadr, but the procedure crashed. Is there a function in scheme that gives me the position of each element? I don't know how to skip every other element.

If you don't know the length of the list, you don't know if there will be a cadr. I would stay away from those when you're in a recursion. They're mostly useful for a list which has a fixed structure.

[Tayacan]

Really. You only need three simple cases. The empty list, the list of one element, and anything else.

The empty list, or (), is easy to find.
The list of one element is the list xs where (cdr xs) equals the empty list.
Anything that doesn't satisfy one of those conditions, is a list of at least two items - hence you can take the first (car xs) and the second (cadr xs) and do stuff to them. Then you can call the function recursively on the rest of the list (cddr xs).

Now, I don't actually know scheme, so this may not be pretty, but it runs.

(define (foo xs)
  (cond ((null? xs) ()) ; Base case 1: The empty list
        ((null? (cdr xs)) (cons (* 2 (car xs)) '())) ; Base case 2: The singleton
        (else (cons (* 2 (car xs)) (cons (cadr xs) (foo (cddr xs))))))) ; Anything else

[jon.kiparsky]

No, not pretty. Here's another way to do it, also not very pretty but preferable, to my eyes:

(define foo (lambda (l)
(define  subfoo (lambda (l i )
(cond   ((null? l) ())
	(else (cons (* i (car l)) (subfoo (cdr l) (+ (modulo  (+ i 1) 2) 1)))))))
(subfoo l 2)))

I prefer this because it eliminates some complexity. The only thing you have to think about is this bit: (+ (modulo (+ i 1) 2) 1)
you don't have to think about proving to yourself that consing the car onto the cons of the cadr and the cddr is actually correct.

You can also do, as I said, something like this:

(define f (lambda (l)
  (define g (lambda (l)
  (cond ((null? l) ())
	  (else (cons (car l) (f (cdr l)))))))
(cond ((null? l) ())
	(else (cons (* 2 (car l)) (g (cdr l)))))))

That's repetitive, but at least it's clear what's going on.

I'm sure there are a number of variations on this theme - you could put the multiplier in a pair and swap the members on each call - first call has (2 1), then you cons the cadr onto the car for each recursive call. Or you could put the functions to modify the head of the list into a list and swap those, so you could add 1 to the even-indexed list members, and square the odd ones, or whatever you like.

There's a lot of ways of capturing something like this. The point, and the fun, is to try to solve it a half a dozen ways, to get hold of it from a number of different angles.