DouKaku? 4303 shiro: comprehension大活躍。(自然数の分割)

Comment detail

comprehension大活躍。

1 2	partitionNum n 1 = [[n]] partitionNum n m = [(n-x):xs \| x <- [0..n], xs <- partitionNum x (m-1)]

あちゃ。先こされた ^^

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

(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が使えます。

(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と再起の組み合わせであんなに短く書けるとは。

(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はエラーになります。

高階関数を使った版。

コード長くなった、読みづらくなった。orz

import List

partitionNum n m = iterate f ([[]]: repeat []) !! m !! n  where
  f xs = tail $ snd $ mapAccumL g (repeat []) [0..] where
    g (y:ys) i = (zipWith (++) (map (map (i:)) xs) ys, y)

DouKaku?

Comment detail

Index

Feed

Other

Link

Pathtraq