CODEWITHSUNDEEP
functional-programmingscheme
yrazlik
yrazlik

Reputation: 10777

How to write the following function in scheme

I am new to scheme and doing some exercises. I am trying to do the following: The function i am going to write takes one list parameter (no input check needed). Then it remoces multiple occurences of the elements and returns the new list. Here is an example input-output:Let us call the function "once",

=>(once '(1 2 5 2 3 4 2 4 1 2))
=>Value: (1 2 5 3 4)

Here is my solution:

(define once
  (lambda (lst)
    (if (null? lst) 
        '() 
        (if (member (car lst) (cdr lst)) 
            (once (cdr lst)) 
            (cons (car lst) (once (cdr lst)))))))

But the order of elements is changed although it eliminates duplicates. Can anyone help? Thanks

Upvotes: 1

Views: 248

Answers (4)

GoZoner
GoZoner

Reputation: 70215

You want to add items from lst if they are not in the result.

(define (once lst)
  (let looking ((lst lst) (rst '()))
    (if (null? lst)
        (reverse rst)                   ; leave order unchanged
        (let ((nxt (car lst)))
          (looking (cdr lst)
                   (if (member nxt rst) ; nxt in rst
                       rst              ; yes: don't augment rst
                       (cons nxt rst)))))))

Upvotes: 1

WorBlux
WorBlux

Reputation: 1413

(define once L
 (if (null? L)
  '()
   (cons (car L) (once (filter (n-eq-x? (car L)) (cdr L))))))

(define (n-eq-x? value)
 (lambda (x) (if (eq? value x) #f #t)))

Of you can write it with a helper

(define (once L)
 (reverse (once-helper L '())))

(define (once-helper L L-once)
 (cond ((null? L) L-once)
       ((member? (car L) (L-once) 
        (once-helper (cdr L) L-once))
       (else (once-helper (cdr L) (cons (car L) L-once)))))

which is closer to the original, the difference here is that instead a building a list with elements that don't appear in the rest of the list, you build a second list, with elements of the original that aren't already members. The check will turn false if you already have the element, rather than being false if you're going to get the element later.

Upvotes: 2

Óscar López
Óscar López

Reputation: 236112

In Racket, it's as simple as this:

(define once remove-duplicates)
(once '(1 2 5 2 3 4 2 4 1 2))
=> '(1 2 5 3 4)

But if you have to implement it from scratch, here's the general idea, fill-in the blanks:

(define (once lst)
  (cond (<???>  ; is the list empty?
         <???>) ; return the empty list
        (<???>  ; is the current element member of the rest of the list?
         <???>) ; advance recursion
        (else   ; otherwise it's not duplicate,
         (cons <???>     ; cons current element
               <???>)))) ; advance recursion

Upvotes: 1

Doug Currie
Doug Currie

Reputation: 41220

As you process the input list, you have an element at the head of the list, and the remaining tail of the list.

  1. If the element at the head of the list is in the tail, then you don't need to add it to the result since it will be caught in a later iteration.
  2. If the element at the head of the list is not in the tail, push it onto the result.
  3. Recurse.

Upvotes: 1

Related Questions