|
|
 |
 |
 |
 |
Scheme Programming Language
|
 |
 |
 |
 |
 |
 |
 |
 |
Newbie - I'm soooo stuck - trying to remove an item from a list
Hi all, Interesting how my skills is stripped to the bone if I am not able to use string functions that are available in other languages. Someone had to do the work for me to benefit ... which is why I'm trying to understand the process of programming / problem solving in more detail. So ... I realise this must be simple - but it has me stumped. I'm playing with lists so I can understand them better. Clearly I don't. Further, I don't even know how to approach the small problem and it is driving me nuts :). I can remove negatives values from a list easily enough, but if I try to translate that approach to, say, removing item 3 (the third item - I know they begin at item 0 through to n-1) from a list of values, I have no clue. The code for remove-negatives is based upon code from my lecturer that replaced negatives in a list. (Do not want to take credit for another person's work.) Anyway, I thought I understand it quite well. Evidently not well enough to translate it to another context. I was hoping to use a similar approach so I can remove a specific item in the list (by place), if that is even possible. ;--------------- template for recursion (bored with factorial :)-------- ; (define [remove-negatives numbers] (cond ;; Base case: No numbers provided, so return empty list [(empty? numbers) empty] ;; Recursive case: First number is negative, so return a ;; list constructed the rest of the ;; numbers [(negative? (first numbers)) (remove-negatives (rest numbers))] ;; Recursive case: First number is non-negative, so ;; return a list constructed from this number followed by ;; the rest of the numbers with negatives removed [else (cons (first numbers) (remove-negatives (rest numbers)))])) ;; Test (remove-negatives (list 1 2 -9 3 4 0 5 6 -8 7)) ; ==> (list 1 2 3 4 0 5 6 7) I can almost see what 'needs' to be done by playing with this in a logical sense. For example: Remove the 'x' item from this list (list 1 2 3 4 5). (define list1 (list 1 2 3 4 5)) 'x' = 1 then the result is (rest (list 1 2 3 4 5)) 'x' = 2 then (cons (first list1) (cons (third list1) (cons (fourth list1) (fifth list1)))) ; ==> (1 3 4 . 5) This is not my desired result but is shows that aside from the first item in the list, I add the first item in the list to the remainder to be processed. Then when I get to the item to be removed I add the first item to those remaining, excluding the one to be removed. I need a list as a result with no pair anywhere. Aside from the case where I want to exclude the first item in the list (which is just (rest list1)), I suspect this 'should' be able to be solved recursively but I do not know how to lay out the process. Can someone please push me in the right direction? Kindest regards, Mike
(define a-list (list 1 2 3 4 5)) ;; remove the nth item from a list .. (define (remove n a-list) (cond [(empty? a-list) empty] [(> n 1) (cons (first a-list)(remove (- n 1) (rest a-list)))] [else (rest a-list)])) hope this helps .. luca Mike ha scritto:
> Hi all, > Interesting how my skills is stripped to the bone if I am not able to use > string functions that are available in other languages. Someone had to do > the work for me to benefit ... which is why I'm trying to understand the > process of programming / problem solving in more detail. > So ... I realise this must be simple - but it has me stumped. > I'm playing with lists so I can understand them better. Clearly I don't. > Further, I don't even know how to approach the small problem and it is > driving me nuts :). > I can remove negatives values from a list easily enough, but if I try to > translate that approach to, say, removing item 3 (the third item - I know > they begin at item 0 through to n-1) from a list of values, I have no clue. > The code for remove-negatives is based upon code from my lecturer that > replaced negatives in a list. (Do not want to take credit for another > person's work.) > Anyway, I thought I understand it quite well. Evidently not well enough to > translate it to another context. I was hoping to use a similar approach so > I can remove a specific item in the list (by place), if that is even > possible. > ;--------------- template for recursion (bored with factorial :)-------- > ; > (define [remove-negatives numbers] > (cond > ;; Base case: No numbers provided, so return empty list > [(empty? numbers) > empty] > ;; Recursive case: First number is negative, so return a > ;; list constructed the rest of the > ;; numbers > [(negative? (first numbers)) > (remove-negatives (rest numbers))] > ;; Recursive case: First number is non-negative, so > ;; return a list constructed from this number followed by > ;; the rest of the numbers with negatives removed > [else > (cons (first numbers) (remove-negatives (rest numbers)))])) > ;; Test > (remove-negatives (list 1 2 -9 3 4 0 5 6 -8 7)) > ; ==> (list 1 2 3 4 0 5 6 7) > I can almost see what 'needs' to be done by playing with this in a logical > sense. > For example: Remove the 'x' item from this list (list 1 2 3 4 5). > (define list1 (list 1 2 3 4 5)) > 'x' = 1 then the result is (rest (list 1 2 3 4 5)) > 'x' = 2 then (cons (first list1) (cons (third list1) (cons (fourth list1) > (fifth list1)))) > ; ==> (1 3 4 . 5) > This is not my desired result but is shows that aside from the first item in > the list, I add the first item in the list to the remainder to be processed. > Then when I get to the item to be removed I add the first item to those > remaining, excluding the one to be removed. I need a list as a result with > no pair anywhere. > Aside from the case where I want to exclude the first item in the list > (which is just (rest list1)), I suspect this 'should' be able to be solved > recursively but I do not know how to lay out the process. > Can someone please push me in the right direction? > Kindest regards, > Mike
Mike <mcu87 @bigpond.net.au> wrote: > (define [remove-negatives numbers] > (cond > [(empty? numbers) > empty] > [(negative? (first numbers)) > (remove-negatives (rest numbers))] > [else > (cons (first numbers) (remove-negatives (rest numbers)))])) > [...] > (define list1 (list 1 2 3 4 5)) > 'x' = 1 then the result is (rest (list 1 2 3 4 5)) > 'x' = 2 then (cons (first list1) (cons (third list1) (cons (fourth list1) > (fifth list1)))) > ; ==> (1 3 4 . 5) Why do you think that your code will cons (fourth list1) to (fifth list1)? Does the above procedure return an improper list as its result? Why? Why don't you just try to write some code based on the above procedure and see how far you get? If you get stuck again, post your code. -- Nils M Holm <n m h @ t 3 x . o r g> -- http://t3x.org/nmh/
Hi Luca, > ;; remove the nth item from a list .. > (define (remove n a-list) > (cond > [(empty? a-list) empty] > [(> n 1) (cons (first a-list)(remove (- n 1) (rest a-list)))] > [else (rest a-list)]))
Thanks for this. Yep ... got a headache and lost sight of the forest while a tree was right in front of me. It seems so simple when I see it. In a way I wish I had not learned any programming before Scheme. I need to 'unlearn' bad habits even though my code worked perfectly well. I did not learn the problem solving process well enough. Excuse me if I stumble in trying to explain what you wrote but I need to know how and why you approached the problem this way. I've been wrangling with this for hours and now that I see what you have done, was way off. My earlier efforts were closer. Guess I was making a simple thing more complicated. Doh! Ok ... baby steps. I could tell that, unless the number was 1 you returned the first item plus the remainder of items to be processed. And I knew (pen and paper) that n had to decrease by 1 each pass in the recursive loop. I did not know how to 'do it' though. Is this a reasonable explanation of your code? Problem: Remove item n from a list and return a list containing the other values. 1.0 Return a list without the nth item. 2.0 No more items in list to process, so return the result (Base case) 3.0 More items in list so continue to process 3.1.1 Check item to remove is not the first in the list 3.1.1.2 Yes, nothing more to process return result (rest list) (Base case) 3.1.2 No, add first item in list to rest of list and decrease n by 1 (Recursive case) How would you describe your process? Here is a modified version of the task I was working on. It checked two lists to see how many items from list1 matched the corresponding item in list2. No doubt it can be improved but it does work ... whew! (define list1 (list 9 1 3 1)) (define list2 (list 2 1 3 4)) (define [check-item list1 list2] ; counts matched items from two lists. (if (empty? list1) ; nothing more to process, return result (Base case) 0 (if (eq? (first list1) (first list2)) ; a match? (+ 1 (check-item (rest list1) (rest list2))) ; yes, add 1 to number of matches remaining. (Recursive case) (check-item (rest list1) (rest list2)))) ; no, calculate the number of matches in the rest of the list (Recursive case). ) (check-item list1 list2) ;==> 2 Kindest regards, Mike
>> (define list1 (list 1 2 3 4 5)) >> 'x' = 1 then the result is (rest (list 1 2 3 4 5)) >> 'x' = 2 then (cons (first list1) (cons (third list1) (cons (fourth list1) >> (fifth list1)))) >> ; ==> (1 3 4 . 5) > Why do you think that your code will cons (fourth list1) to (fifth list1)? > Does the above procedure return an improper list as its result? Why? > Why don't you just try to write some code based on the above procedure > and see how far you get? If you get stuck again, post your code.
Hi Nils, Thanks for responding. I saw the reply from Luca (thanks again, Luca) that did the trick. But I will try to do as you ask (no peeking by me). Although I was walking through the steps, I could see that I needed to add the first item to the remaining items to be processed in the list. And I knew that I needed to step down (decrease n) by 1 each pass until I reached n where I would add items processed to the rest of the items waiting to be processed. Perhaps I have not worded it properly but it seemed perfectly suited to recursion which, aside from learning about cons, was why I was playing with this. (Bored with using factorial calculations as an example.) Your question about (cons (fourth list1) (fifth list1) hits the nail on the head. I know cons returns a pair and yet I also know that when I use it in recursive processes, I end up with a list. I don't know why. Sorry ... I follow the code in the debugger but it doesn't quite show me much until the end (DrScheme). Please correct me if you see anything in error ... there has to be or I wouldn't be asking for guidance. OK ... cons adds two objects together as a pair (at least that was what I thought). If I do this: (cons (first (list 1 2 3 4)) (second (list 1 2 3 4))) ;==> (1 . 2) And I expect the result is a paired object. What I can't understand is how cons seems to return a list when used in a recursive process. Ultimately the recursion ends. On the nth pass through the loop, the only difference is that I tend to use an empty (a list has been completely processed) or simply, the rest of the list. But the previous use of cons *should* have created a list with the tail as a pair? But ... it doesn't. So ... nope, not a clue and I need to understand why. It isn't enough for me to be able to parrot the goods, I want to understand how the good were delivered. Hope that makes sense :) Problem: Return a list excluding item n 1.0 Return the list without item n. 2.0 If n = 1, return the rest of the list. Stop. (Base case) 3.0 Otherwise add the first item to the remaining items to be processed and decrease n by 1. (Recursive base) I will try to do a variation and count all items from list1 that appear in list2 other than those appearing in the corresponding location and get back to you. Kindest regards, Mike
>> (define list1 (list 1 2 3 4 5)) >> 'x' = 1 then the result is (rest (list 1 2 3 4 5)) >> 'x' = 2 then (cons (first list1) (cons (third list1) (cons (fourth list1) >> (fifth list1)))) >> ; ==> (1 3 4 . 5) > Why do you think that your code will cons (fourth list1) to (fifth list1)? > Does the above procedure return an improper list as its result? Why? > Why don't you just try to write some code based on the above procedure > and see how far you get? If you get stuck again, post your code.
Hi Nils, Back again. I walked through the code that luca provided (almost had it actually) to see if I might answer the question regarding cons more fully. (define a-list (list 1 2 3 4 5)) (define (remove n a-list) (cond [(empty? a-list) empty] [(> n 1) (cons (first a-list)(remove (- n 1) (rest a-list)))] [else (rest a-list)])) (remove 2 a-list) Based on the above: First pass: (> n 1) ; #f ... n=2 (empty? a-list) ; #f so ... (cons (first a-list) (remove (- n 1) (rest a-list))) which is: (cons 1 (remove 1 (list 2 3 4 5))) ; aside ... (define a-list (list 2 3)) ; (cons 1 (cons (first a-list) (rest a-list))) ==> (1 2 3 4 5) and not a pair. ; but (cons 1 (cons (first a-list) (second a-list))) ==> (1 2 .3) ; Is this because (second a-list) is a typed value (number - could be a string if I used strings) and not a list? ; while (rest a-list) returns a list containing an item?? ; Ahhhh ... the loud noise is a huge penny dropping :) Second pass in loop: (> n 1) ; #t n=1 because it was decreased So ... (cons 1 (rest a-list)) (const 1 (list 3 4 5)) (1 3 4 5) Did that answer your question more completely? The 'problem' was mine - not understanding that (first a-list) or whichever of the nths I use, returns the typed value contained in the list (assuming I limit the list to typed values and not other lists or other objects)? Kindest regards, Mike
Mike <mcu87 @bigpond.net.au> wrote: > (define a-list (list 1 2 3 4 5)) > (define (remove n a-list) > (cond > [(empty? a-list) empty] > [(> n 1) > (cons (first a-list)(remove (- n 1) (rest a-list)))] > [else (rest a-list)])) > (remove 2 a-list) > Based on the above: > First pass: > (> n 1) ; #f ... n=2 > (empty? a-list) ; #f so ... > (cons (first a-list) (remove (- n 1) (rest a-list))) which is: > (cons 1 (remove 1 (list 2 3 4 5)))
Exactly. And what would the next step be? (BTW, please make lists start with the 0th element instead of the 1st, so that your REMOVE is compatible with LIST-TAIL and LIST-REF.) > ; aside ... (define a-list (list 2 3)) > ; (cons 1 (cons (first a-list) (rest a-list))) ==> (1 2 3 4 5) > and not a pair.
Right: consing the head of a list to its rest gives the original list. > ; but (cons 1 (cons (first a-list) (second a-list))) ==> (1 2 .3)
True, but where does the (second a-list) come from? I see no SECOND in the above procedure. > ; Is this because (second a-list) is a typed value (number - > could be a string if I used strings) and not a list?
(define first car) ; FIRST and REST are not part of R5RS (define rest cdr) All values are typed in Scheme: (define a-list (list 1 2 3 4 5)) (pair? a-list) => #t (integer? (first a-list)) => #t > ; while (rest a-list) returns a list containing an item??
FIRST (or CAR) returns the head of a list: (first (list 1 2)) => 1 while REST (or CDR) returns the rest of a list. The rest of a list is still a list: (cdr (list 1 2)) => (2) A list is just a special case of a pair: (define empty? null?) ; EMPTY? is not in R5RS either (define (list? x) (or (empty? x) (and (pair? x) (list? (rest x))))) You may want to play with CONS, FIRST (or CAR) and REST (or CDR) to get a feeling for lists and pairs. In particular, you might wonder what the rest of a one-element list would be and how to construct one. -- Nils M Holm <n m h @ t 3 x . o r g> -- http://t3x.org/nmh/
lukas @gmail.com writes: > (define a-list (list 1 2 3 4 5)) > ;; remove the nth item from a list .. > (define (remove n a-list) > (cond > [(empty? a-list) empty] > [(> n 1) (cons (first a-list)(remove (- n 1) (rest a-list)))] > [else (rest a-list)]))
Hi, i'm very new to scheme, and i just have a quick side question, which is, what's with the brackets?--the [foo] stuff instead of (foo)? Is this a general scheme thing i don't know about? What's it for? -- theron tlx (compose-mail (concat "thorne@" (rot13 "gvzoeny") ".net"))
what's with the brackets? That's an mzscheme-ism. They don't mean anything different from ordinary parentheses, but the mzscheme people like to use them to indicate ... something or other :-) Just pretend they're regular parentheses. -- ... apart from the sanitation, the medicine,education, wine, public order, irrigation, roads, a fresh water system, and public health, what have the Romans ever done for us? -- Reg, JPF
Eric Hanchrow wrote: > what's with the brackets? > That's an mzscheme-ism.
Afaik, that's not entirely correct. MzScheme is one of several implementations which support brackets, along with e.g. Gambit, SISC, and Chez. I'm not sure who started using them (perhaps someone else knows?) but I notice that they are used in a Waddell/Dybvig paper[*] in 1999. > They don't mean anything different from > ordinary parentheses, but the mzscheme people like to use them to > indicate ... something or other :-)
By convention, they're used to reduce ambiguity when delimiting groups other than procedure application, e.g. in let variable definitions and cond conditions. They're actually pretty useful in conjunction with an IDE that supports them - it makes mismatched parentheses errors harder to make and easier to find when you do make them. I don't use them myself, though, because they have sharp pointy corners and I'm afraid I might get hurt. Anton [*] Extending the Scope of Syntactic Abstraction, http://www.cs.indiana.edu/~dyb/papers/popl99.ps.gz
|
 |
 |
 |
 |
|