1. ホーム
  2. scheme

[解決済み] Schemeでリスト内の要素の出現回数を数える?

2022-01-31 09:23:25

質問

命令型言語の配列やC++のマップ(木構造)などが使えれば、非常に簡単なのですが。schemeでは、このアイデアをどのように始めたらいいのか、さっぱりわかりません。どなたか教えてください。

ありがとうございます。

解決方法は?

Racket では、次のようにします。

(count even? '(1 2 3 4))

しかし、もっとまじめな話、Schemeでリストを使うのは、あなたが言うよりずっと簡単なことです。 リストは空か、最初の項目と残りの項目を持つペアのどちらかです。 その定義に従ってコードを書けば "自分自身を書き出すことができます"。

をベースにしたヒントを紹介します。 高度経済成長期 (この手のことを学ぶのに通読すると良い本です)。 関数 "header" だけから始めてください -- これは述語とリストを受け取るはずです。

(define (count what list)
  ...)

入力の型を追加する --。 what は何らかの値であり list は、もののリストです。

;; count : Any List -> Int
(define (count what list)
  ...)

ここで list そして、リストが空リストか2つのもののペアであるという定義から、それがどの種類のリストであるかを確認する必要があります。

;; count : Any List -> Int
(define (count what list)
  (cond [(null? list) ...]
        [else ...]))

最初のケースは明らかでしょう:いくつの what の項目が空リストに含まれているか?

2 番目のケースでは、空でないリストであることは分かっているので、次の 2 つの情報を得ることができます。 first または car で得られる)とその尾を rest または cdr ):

;; count : Any List -> Int
(define (count what list)
  (cond [(null? list) ...]
        [else ... (first list) ...
              ... (rest list) ...]))

あとは、この2つの情報をどう組み合わせれば、コードができるかを考えるだけです。 最後に、これを非常に簡単にしてくれる情報をひとつ。(空でない)リストの末尾はそれ自体がリストであるため、そのリストに対して count を使えば、その中にあるものを数えることができます。 したがって、さらに結論として (count what (rest list)) を入れる。