DouKaku?beta

Comment detail

自然数の分割 (Nested Flatten)

This comment is reply for 4303 shiro: comprehension大活躍。(自然数の分割). Go to thread root.

comprehensionって便利ですね。 List Comprehension - defmacro によるリストの内包表記 http://lambda.s55.xrea.com/Emacs.html のlist-of を利用してemacs-lispで書いてみました。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
(defun partitionNum (a b)
  (if (= b 1)
      (list (list a))
    (let ((x 0) (l '()))
      (while (<= x a)
    (progn
      (setq l
        (append 
         l
         (list-of (append (list (- a x)) y)
              (y in (partitionNum x (- b 1))))))
      (setq x (+ x 1))))
      l)))
(print (partitionNum 5 3))

Schemeならsrfi-42でcomprehensionが使えます。

1
2
3
4
5
6
7
(use srfi-42)

(define (partition-num n m)
  (if (= m 1)
    `((,n))
    (list-ec (: x 0 (+ n 1)) (: xs (partition-num x (- m 1)))
             (cons (- n x) xs))))

n=5 m=3 の場合、

(reverse (list-ec (: a 6) (: b 6) (: c 6) (if (= 5 (+ a b c))) (list a b c)))

というコードが生成されれば良い。

→マクロで書いてみる。

→nとmがコンパイル時に決まらないから無理？

→生成したコードをevalする方針に変更。

とこんな風になりました。

;; comprehensionと再起の組み合わせであんなに短く書けるとは。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
(use srfi-1)
(use srfi-42)

(define (quolifiers upper-bound n-quos)
  (let1 gensyms (map (lambda (x) (gensym)) (iota n-quos))
    (values gensyms
            (map (lambda (sym) `(: ,sym ,upper-bound))
                 gensyms))))

(define (partition-num n m)
  (receive (syms form) (quolifiers (+ n 1) m)
    (eval `(reverse (list-ec ,@form (if (= ,n (+ ,@syms))) (list ,@syms)))
          scheme-report-environment)))

evalの第二引数は (interaction-environment) にするか (current-module) にするのが良いでしょう。

現在はscheme-report-environmentの値である「手続きそのもの」が渡っているので本来はエラーなのですが、Gaucheはチェックをさぼってデフォルトである(current-module)の値を使っているためにたまたま動作してしまっています。

(scheme-report-environment 5) とすればevalの引数として正しいものが渡りますが、その環境の中ではR5RSで定義されている手続きや構文しか見えないのでlist-ecはエラーになります。

Index

Feed

Other

Link

Pathtraq

loading...
Creative Commons License このサイトの内容は、 クリエイティブ・コモンズ・ライセンスの下でライセンスされています。 [詳細]