functional-programming - スキームのリストで繰り返される要素を検索する

Question

次のようなリストを受け取るには、schemeで記述されたプログラムを作成する必要があります。

(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 が言うように、もう少しコンテキストがあればいいのにと思います。この問題は宿題のように見えますが、おそらく、効率をあまり気にせずに、基本的なリスト操作を使用して解決する必要があります。高度な機能を使用しているため、宿題の回答としては役に立たない方法で質問を解決しますが、今後の参考になれば幸いです。

数値カウントを追跡するためのヘルパー データ構造としてハッシュ テーブルを使用し、入力リストに対するリスト トラバーサルの数を最小限に抑える効率的な回答を目指します。必要なトラバーサルは 1 回だけです。また、数字のリストだけでなく、任意の数字のリストでも機能します。

まず、可変状態を使用した効率的で非機能的なスタイルのソリューション:

(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

foldこれは、バニラ再帰の代わりに使用するソリューションです。リスト内の一意の要素を取得するためのヘルパー プロシージャと、要素の出現回数をカウントする方法もあります。

#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のベクトルをゼロを含むように初期化します。

   ここで、v の i 番目のエントリである count[i] は、iこれまでに処理された、リストの一部での出現回数です。

2. リスト内の要素ごとに、ベクトルiの th 要素をインクリメントします。i

3. ベクトル内の情報をリスト形式に変換します。

リストベースの関数をトレーニングすることになっている場合は、さらに処理する前にリストを昇順にソートすることをお勧めします。これにより、必要なカウントが簡素化されます。