Hatena::Groupcadr

わだばLisperになる このページをアンテナに追加 RSSフィード

2004 | 12 |
2005 | 01 | 02 | 07 | 10 | 11 |
2006 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2007 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2008 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2009 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2010 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2011 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 11 |

2008-04-21

CLで学ぶ「プログラミングGauche」 (7.2)

| 01:48 | CLで学ぶ「プログラミングGauche」 (7.2) - わだばLisperになる を含むブックマーク はてなブックマーク - CLで学ぶ「プログラミングGauche」 (7.2) - わだばLisperになる

7.2 手続きを取る手続き

前回からの続きです。7章は割と長いので小分けにしててくてく進んで行きます。

このセクションは高階関数のセクションで、かなり良いことが書いてあると思うので、個人的には何回も復習して,こういった種類の抽象化ができるようになりたいところです。

なぜ関数プログラミングは重要か」という有名な論文がありますが、このセクションもまた関数プログラムのエッセンスを濃縮して教えてくれているように思います。

とりあえず、for-eachの解説からなのですが、CLだと、mapcがfor-eachに相当します。

共通点としては、全体の返り値はあてにしないで、ループ構文として副作用目的で使われる、ということです。

そのため、for-each返り値は未定義であり、それは期待して使われないものということになっています。

mapcもCLtL2にはスタイルとして副作用目的で使われる、とあります。ちなみに、mapcの返り値は、未定義ではなく第2引数となっています。(つまり1番目のリスト)

また、昔(MacLISPの頃)は、mapcは好んで使われていたようですが、dolistが登場してからは、dolistが人気のようで、あまり使われなくなって来ています。

ここでは、とりあえず形が似ているということと、dolistはマクロなので高階関数の引数にするには都合が悪いので、mapcでfor-eachの代用をさせます。

また、schemeのmapは、CLのmapcarに相当しますが、R5RS的には引数の評価順序が規定されていないそうで、規定されたものには、srfi-1のmap-in-orderがあるようです。Gaucheのmapは、map-in-orderになっているとのことです。CLのmapcarは(というか基本的にどの関数でも)頭から順に評価されます。

色々CLに翻訳

(defun tree-walk (walker proc tree)
  (funcall walker (lambda (elt)
                    (if (listp elt)
                        (tree-walk walker proc elt)
                        (funcall proc elt)))
           tree))

(tree-walk #'mapc #'print '((1 2 3) 4 5 (6 (7 8))))
;=> 1 2 3 4 5 6 7 8

(defun reverse-for-each (proc lst)
  (mapc proc (reverse lst)))

(tree-walk #'reverse-for-each #'print '((1 2 3) 4 5 (6 (7 8))))
;>>> 1 2 3 4 5 6 7 8

(tree-walk #'mapcar (lambda (x) (* x 2))
           '((1 2 3) 4 5 (6 (7 8))))
;=> ((2 4 6) 8 10 (12 (14 16)))

(defun reverse-map (proc lst)
  (mapcar proc (reverse lst)))

(tree-walk #'reverse-map (lambda (x) x)
           '((1 2 3) 4 5 (6 (7 8))))
;=> (((8 7) 6) 5 4 (3 2 1))

(defun reversed (walker)
  (lambda (proc lst)
    (funcall walker proc (reverse lst))))

(funcall (reversed #'mapcar) #'values '(1 2 3 4))
;=> (4 3 2 1)

(tree-walk (reversed #'mapcar) (lambda (x) x)
           '((1 2 3) 4 5 (6 (7 8))))
;=> (((8 7) 6) 5 4 (3 2 1))

という流れで、ステップを踏んでどんどん骨組みを括り出す方法が解説されているのですが、非常にためになります!

[練習問題]

;; 6章の練習問題やってなかった…。
(defun filter (pred lst)
  (reduce (lambda (x res)
            (if (funcall pred x)
                (cons x res)
                res))
          lst :initial-value () :from-end 'T))

(defun for-each-numbers (proc lst)
  (mapc proc (filter #'numberp lst)))

(for-each-numbers #'print '(1 2 #:f 3 4 #:t))
;>>> 1 2 3 4

(defun map-numbers (proc lst)
  (mapcar proc (filter #'numberp lst)))

(map-numbers #'values '(1 2 #:f 3 4 #:t))
;=> '(1 2 3 4)

(defun numbers-only (walker)
  (lambda (proc lst)
    (funcall walker (lambda (x) 
                      (and (numberp x)
                           (funcall proc x)))
             (filter #'numberp lst))))) 

(funcall (numbers-only #'mapcar) #'values '(1 2 #:f 3 4 #:t))
;=> (1 2 3 4)

(funcall (numbers-only #'mapc) #'print '(1 2 #:f 3 4 #:t))
;>>> 1 2 3 4

(defun numbers-only-for-tree (walker)
  (lambda (proc tree)
    (funcall walker proc
	     (filter (lambda (x) (or (listp x) (numberp x)))
		     tree))))

(tree-walk (numbers-only-for-tree #'mapc) #'print 
           '((1 2 3 #:t) 4 5 (6 (7 8 #:t ((((((#:f 9))))))))))
;>>>1 2 3 4 5 6 7 8 9

(tree-walk (numbers-only-for-tree #'mapcar) #'values 
 '((1 2 3 #:t) 4 5 (6 (7 8 #:t ((((((#:f 9))))))))))
;=> ((1 2 3) 4 5 (6 (7 8 ((((((9)))))))))

;; おまけ
;; funcallが目に痛いという場合、リーダーマクロで!にしてしまうのはどうか
;; という試み。その代わり、!が名前に使い辛くなるという諸刃の剣。
(set-macro-character #\! (lambda (str char)
                           (declare (ignore str char))
                           'funcall))

(defun numbers-only-for-tree (walker)
  (lambda (proc tree)
    (!walker proc
       (filter (lambda (x) (or (listp x) (numberp x)))
		       tree))))

; と書ける。
;; 追記/numbers-only-for-treeの解釈を激しく間違っていたので修正しました(^^; 2008/5/15