functional-programming - 在方案中的列表中查找重复元素

Question

我需要创建一个用方案编写的程序来接收这样的列表：

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

这必须给我作为输出：

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

这个输出是因为有 4 位 2、3 位 3、1 位 4 和 5 位 1。

Answer 1

正如@soegaard 所说，更多的上下文会很好。这个问题看起来像家庭作业，可能必须使用基本的列表操作来解决，而不必太担心效率。我将以一种不会作为家庭作业答案有用的方式来解决这个问题，因为它使用了一些高级功能，但希望它对将来的参考有用。

我将使用哈希表作为帮助数据结构来跟踪数字计数，旨在获得一个有效的答案，最大限度地减少输入列表上的列表遍历次数 - 只需要一次遍历。此外，它适用于任意数字列表，而不仅仅是数字列表。

首先是使用可变状态的高效、非函数式解决方案：

(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)))))

现在是相同的过程，但以纯功能样式实现，没有状态突变（请记住，问题被标记为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))))

无论哪种方式，这都有效 - 尽管结果可能以不同的顺序出现：

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

Answer 2

这是一个使用 offold代替原版递归的解决方案。我还有帮助程序来获取列表中的唯一元素以及计算元素出现次数的方法。

#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))

样本输入的结果：

(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

编辑代码：

(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 4

练习的背景很重要。有很多方法可以解决这个练习，所以正确的解决方案取决于你知道什么概念。

这是一个简单的解决方案，它使用列表包含数字的事实：

1. count将长度为 10的向量初始化为包含零。

   这里 count[i] 是 v 的第 i 个条目，是i到目前为止已处理的列表部分中出现的次数。

2. 对于列表中的每个元素i，递增i向量的第 th 个元素。

3. 将向量中的信息转换为列表形式。

如果您应该训练基于列表的函数，那么在进一步处理之前按升序对列表进行排序是个好主意。这简化了您需要进行的计数。