Find repeated elements in a list in scheme

Question

I need to create a program written in scheme to receive a list like this:

(function '(2 3 4 3 2 3 1 1 1 1 2 1 2))

Which must give me as output:

-> '((4 2) (3 3) (1 4) (5 1))

This output is because there are 4 digits 2, 3 digits 3, 1 digit 4 and 5 digits 1.

Answer 1

Edited code:

(define (counter lst) 
        (if (null? lst)
         '()
        (cons (cons (count_help (car lst) lst) (car lst))
              (counter (delete (car lst) lst)))))

(define (count_help x lst)
        (cond ((null? lst) 0)
        ((eq? x (car lst)) (+ 1 (count_help x (cdr lst))))
        (else   (count_help x (cdr lst)))))

(define delete
  (lambda (item list)
    (cond
      ((null? list) '())
     ((equal? item (car list)) (delete item (cdr list)))
     (else (cons (car list) (delete item (cdr list)))))))

Answer 2

Here is a solution that uses of fold in stead of vanilla recursion. I also have helper procedures to get the unique elements in a list and a way of counting the number of occurrences of an element.

#lang racket

(define (counted-elements lst)
  ;; This creates the list of (counted element)
  ;; pairs
  (foldl
    (lambda (next result)
      (cons
        (list (count next lst) next)
        result))
    '()
    (uniques lst)))


(define (count digit lst)
  ;; Count how many times digit appears in lst
  (foldl
    (lambda (next count)
      (if (= next digit) (+ count 1) count))
    0
    lst))

(define (uniques lst)
  ;; Get all the unique elements of lst
  (define (contains? elem collection)
    (not (zero? (count elem collection))))
  (foldl
    (lambda (next result)
      (if (contains? next result)
          result
          (cons next result)))
    '()
    lst))

The result on your sample input:

(counted-elements '(2 3 4 3 2 3 1 1 1 1 2 1 2))
;=> '((4 2) (3 3) (1 4) (5 1))

Answer 3

As @soegaard says, a bit more of context would be nice. The question looks like homework, and probably must be solved using basic list operations, without worrying much about efficiency. I'm gonna solve the question in a way that won't be useful as an answer for homework because it uses some advanced features, but hopefully it will be useful for future reference.

I'll use a hash table as a helper data structure for keeping track of the number count, aiming for an efficient answer that minimizes the number of list traversals over the input list - only one traversal is needed. Also, it will work for arbitrary lists of numbers, not just lists of digits.

First an efficient, non-functional-style solution using mutable state:

(define (counter lst)
  (let ((ht (make-hash)))
    (for-each
     (lambda (e)
       (hash-update! ht e add1 (lambda () 0)))
     lst)
    (hash-map ht (lambda (k v) (list v k)))))

Now the same procedure but implemented in a purely functional style without state mutation (bearing in mind that the question is tagged as functional-programming):

(define (counter lst)
  (hash-map
   (foldl (lambda (e ht)
            (hash-update ht e add1 (lambda () 0)))
          (hash)
          lst)
   (lambda (k v) (list v k))))

Either way, this works - although the results may appear in a different order:

(counter '(2 3 4 3 2 3 1 1 1 1 2 1 2))
> '((5 1) (4 2) (3 3) (1 4))

Answer 4

The context of the exercise is important. There are many ways to solve this exercise, so the proper solution depends on what concepts you know.

Here is a simple solution, that uses the fact that the list contains digits:

1. Initialize a vector count of length 10 to contains zeros.

   Here count[i], the i'th entry of v, is the number of occurences of i in the part of the list, that have been processed so far.

2. For each element i in the list, increment the ith element of the vector.

3. Convert the information in the vector to list form.

If you are supposed to train list based functions, then it would be a good idea to sort the list in ascending order before further processing. This simplifies the counting you need to do.