3

私は 2 日前に Lisp の勉強を始めました。Paul Graham の ANSI Common List を読んでいて、言語構造が非常に興味深い方法で公開されています。初心者にとっては理論的すぎず、浅すぎません (個人的に嫌いな Sierra-Bate の Head First Java のように)。簡単な一般的な言語の紹介の後、彼はリストについて話し始め、単純なリスト圧縮の例を挙げます。基本的に、el は n 回繰り返される要素とします。それらすべてを 1 つの (n el) リストに置き換えます。これを行うために、彼はコードの実装を提供しましたが、私は自分で実装しようとしましたが、明らかに機能しています。可能であれば、誰かが私のコードを分析して、その実装の重要なポイントを教えてくれることを望みます。これは、Lisp との最初の接触なので、たくさんあると確信しています。ありがとうございます！

(defun compress (x)
"compress a list replacing repeated sequential values for (<n> <value>)"
(let ((lst '()) (fst t) (lt nil) (n 0)) 
    (dolist (el x)
        (if fst
            (progn
                (setq fst nil)
                (setq lt el)
                (setq n 1))
            (progn 
                (if (equal el lt)
                    (setq n (+ n 1))
                    (progn
                        (setq lst (cons (if (= n 1)
                                    lt
                                    (list n lt)) 
                                lst))
                        (setq lt el)
                        (setq n 1)
                    )))))
    (setq lst (cons (if (and (not (= n 0)) (= n 1))
                        lt
                        (list n lt)) 
            lst))
(reverse lst)))
4

2 に答える 2

3

スタニスラフの答えに加えて、 別の可能な実装を示したいと思います。圧縮アルゴリズムは、 foldREDUCEとも呼ばれるの完全なユースケースです。リダクション関数は、これまでの結果である新しい要素を取得し、それらを結合して次の結果を生成します。必要な結果は、カップルのリストです。初期要素は空のリストです。

(defun compress (sequence)
  (reduce (lambda (number list &aux (head (first list)))
            (if (eql number (first head))
                (prog1 list
                  (incf (second head)))
                (cons (list number 1) list)))
          sequence
          :from-end t
          :initial-value nil))

リダクションは末尾からcons適用されるため、要素の既存の順序を維持しながら、現在の結果の上に新しいカップルを簡単に追加できます。入力が'(a b b c)の場合、無名縮小関数は次のように呼び出されます。

number  list           new list
---------------------------------------------
c       nil            ((c 1))
b       ((c 1))        ((b 1)(c 1))
b       ((b 1)(c 1))   ((b 2)(c 1))
a       ((b 2)(c 1))   ((a 1)(b 2)(c 1))

REDUCEシーケンスに対して定義されているため、圧縮関数は一般的です。

;; string
(compress "aaddzadzaaaddb")
=> ((#\a 2) (#\d 2) (#\z 1) (#\a 1) (#\d 1) (#\z 1) (#\a 3) (#\d 2) (#\b 1))

;; vector
(compress #(1 2 3 3 3 3 4 4 4 55 5 5 5 5 5 5 ))
=> ((1 1) (2 1) (3 4) (4 3) (55 1) (5 6))

;; list
(compress '(1 2 3 3 3 3 4 4 4 55 5 5 5 5 5 5 ))
=> ((1 1) (2 1) (3 4) (4 3) (55 1) (5 6))
于 2015-10-06T14:16:07.130 に答える