Home     |     .Net Programming    |     cSharp Home    |     Sql Server Home    |     Javascript / Client Side Development     |     Ajax Programming

Ruby on Rails Development     |     Perl Programming     |     C Programming Language     |     C++ Programming     |     IT Jobs

Python Programming Language     |     Laptop Suggestions?    |     TCL Scripting     |     Fortran Programming     |     Scheme Programming Language


 
 
Cervo Technologies
The Right Source to Outsource

MS Dynamics CRM 3.0

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:

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

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

Add to del.icio.us | Digg this | Stumble it | Powered by Megasolutions Inc