Removing repeated elements in lists

Question

I am having a bit of trouble with some code I've written but I am unable to locate the error. The programming language is in scheme and the problem is below:

Leave only the elements that are not repeated. Ex: (a b a a a c c) -> (a b)

I have written the below code.

    (define x '(a b a a a c c))
    (display x)
    (define z '())
    (define (removeReps y)
    (if (null? y)
      '()
      (if( = (car y) (removeReps (cdr y)))  '() (append z (car y)))))
    (removeReps x)
    (display z)

For full disclosure, this was a homework assignment but I was unable to solve it.

Thank you.

Answer 1

Something along the following lines would probably be acceptable:

;; expr list -> list
;; produce a list where leading elements equal to EXPR have been dropped
(define (drop-in-front elt list)
  (cond [(null? list) list]                            ; empty list, we're done
        [(equal? elt (first list))                     ; first element matches
         (drop-in-front elt (rest list))]              ; drop and repeat
        [#t list]))                                    ; no match, we're done

;; list -> list
;; produce a list where blocks of repeated elements have been dropped
(define (remove-repeated list)
  (cond [(or (null? list)                              ; empty list
             (null? (cdr list)))                       ; or list with one element
         list]                                         ; we're done
        [(equal? (first list)                 
                 (second list))                        ; two matching elements in front
         (remove-repeated                              ; continue with
          (drop-in-front (first list)                  ; list where block in front
                         (rest list)))]                ; has been dropped
        [#t                                            ; first elt different from snd
         (cons (first list)                            ; stick it in front of
               (remove-repeated (rest list)))]))       ; cleaned up rest of list

I sincerely hope that your course will present some style guides soon.

If you have the opportunity, try to look at the lectures of Introduction to Systematic Program Design or have a look at How to Design Programs.

Answer 2

In Common Lisp, I would use stack apis for lists:

(defun elim-dup (l)
    (if (null l)
        nil
        (progn
            (setf new ())
            (dolist (x l)
                (setq elem (pop l))
                (if (not (member elem new))
                    (push elem new)))
            new)))

If you prefer in the original order, add:

(reverse new)

To avoid destruction of the original list, you have to take the nth element instead of pop (and maintain a counter). pop is more straightforward but destructive.

Answer 3

The solution is not that simple, you have to keep track of the previous element found while iterating, and also have a flag that tells you whether the previous element has appeared more than once. Here's my shot, assuming that the input list is non-empty (it's trivial to handle the case if the input list is empty, left as an exercise for the reader):

(define (removeReps lst)
  ; we need some extra parameters, use a named let for iteration
  (let loop ([lst (cdr lst)]  ; list to process, assuming non-empty
             [prev (car lst)] ; pick first as "previous" value
             [first #t])      ; flag: is this the first element in sequence?
    (cond ((null? lst)        ; if we reached the end of the list
           (if first          ; edge case: handle last element
               (list prev)    ; if it was the first in sequence add it
               '()))          ; otherwise skip it and end list
          ; if current element equals previous element
          ((equal? (car lst) prev)
           ; skip it, advance recursion and update flag
           (loop (cdr lst) prev #f))
          ; new element, if previous element had exactly one repetition
          (first
           ; add it to output, advance recursion, update prev and flag
           (cons prev (loop (cdr lst) (car lst) #t)))
          ; new element, if previous element had more than one repetition
          (else
           ; skip it, advance recursion, update prev and flag
           (loop (cdr lst) (car lst) #t)))))

UPDATE

I really liked @chris's implementation in Haskell: higher-level and makes use of existing procedures instead of explicit recursion, it works for empty lists and it's not too difficult to translate to Scheme (it's more verbose in Scheme than in Haskell, though.) Here's yet another option using Racket and SRFI-1's span procedure, take a look at @chris's answer to see an explanation of how this works:

(require srfi/1) ; import `span`

(define (group lst)
  (match lst
    ['() '()]
    [(cons x xs)
     (let-values (((ys zs) (span (curry equal? x) xs)))
       (cons (cons x ys) (group zs)))]))

(define (removeReps lst)
  (filter-map (lambda (x) (and (= (length x) 1) (first x)))
              (group lst)))

Or more portable, without using Racket-specific procedures and special forms:

(require srfi/1) ; import `span`

(define (group lst)
  (if (null? lst)
      '()
      (let ((x  (car lst))
            (xs (cdr lst)))
        (let-values (((ys zs) (span (lambda (e) (equal? e x)) xs)))
          (cons (cons x ys)
                (group zs))))))

(define (removeReps lst)
  (map car
       (filter (lambda (x) (= (length x) 1))
               (group lst))))

Let's test the procedures with some edge cases - it works as expected with any of the above implementations:

(removeReps '(a b a a a c c))
=> '(a b)

(removeReps '(x a a x b b x c c x))
=> '(x x x x)

(removeReps '(a a a))
=> '()

(removeReps '(a b b c c))
=> '(a)

(removeReps '(a a b b c c d))
=> '(d)

Answer 4

another recursive solution that seems to handle the test cases.

;rep is the last repeated elem, input is the input list and first is boolean
(define notrepeatedrec
  (lambda (rep input first)
    (cond ((null? input) (if (eq? first #t) (list rep) '()))
          ((eq? rep (car input)) (notrepeatedrec (car input) (cdr input) #f))
          (else (if (eq? first #t) 
                  (cons rep (notrepeatedrec (car input) (cdr input) #t))
                  (notrepeatedrec (car input) (cdr input) #t))))))

;helper function to start the recursion
(define notrepeated 
  (lambda (lst)
    (notrepeatedrec '() lst #f)))

Answer 5

Another possible solution is the following

import Data.List

removeDups :: Eq a => [a] -> [a]
removeDups = map head . filter ((== 1) . length) . group

written in Haskell and using the library functions group, length, (==), filter, head, and map.

Since the above might not be overly readable, I'll step through the definition piecewise

First a textual description of the individual parts that constitute the above definition

1. First group the list into sublists containing equal elements.
2. For each of those, check whether it is of length exactly 1. If so keep it, otherwise throw it away.
3. From the resulting list of lists (of which we know that every element has length exactly 1) we actually just need the singleton elements, which correspond to the heads of the individual list.

Now for some code. A function that groups elements of a list together as long as they are equal can be defined as follows (sorry I'm using Haskell syntax because I'm not very familiar with scheme, but it should be easy to translate):

group :: Eq a -> [a] -> [[a]]
group []     =  []
group (x:xs) =  (x:ys) : group zs
  where (ys, zs) = span (== x) xs

where span is another library function that, given some predicate p, splits its input list into an initial segment of elements all satisfying p and the remainder of the list. For completeness, it could be defined as follows

span :: (a -> Bool) -> [a] -> ([a], [a])
span _ [] =  ([], [])
span p xs@(x:xs')
  | p x =  let (ys, zs) = span p xs' in (x:ys, zs)
  | otherwise =  ([], xs)

map, filter, and head are even more standard then those and I'm sure they are part of schemes library (as might be group).

I guess my main point is that the solution is easy once you split the problem into small chunks of subproblems (using some predefined functions) and combine the results.