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 |

2007-04-15

L-99 (56)

| 12:14 | L-99 (56) - わだばLisperになる を含むブックマーク はてなブックマーク - L-99 (56) - わだばLisperになる

L-99 P56に挑戦 - L-99:Ninety-Nine Lisp Problems

50番台の問題が難しかったので、飛ばして70番台から進

めていたけれど、80番台も難しいので、50番台から解答

できそうな問題に挑戦することに。

今回は、二分木の対称性を調べる関数の作成が問題。ノー

ドのアイテムまで完全に同じかどうかではなく、骨格が

同じならば、真と判定せよとのこと。

CADRいじるのが楽しいので、Lisp Machine Lispでも回

答。

Lisp Machine Lispにはendpがないので、作ってみた。

そこで、listpが空リストでtを返さないことを発見。や

やこしい。

P56

解答
;; Lisp Machine Lisp / Common Lisp
(defun mirror (tree)
  (if (endp tree)
      '()
    (destructuring-bind (root l r)
			tree
      `(,root ,(mirror r) ,(mirror l)))))

(defun skeleton (tree)
  (if (endp tree)
      '()
    (destructuring-bind (root l r)
			tree
      `(x ,(skeleton l) ,(skeleton r)))))

(defun symmetric (tree)
  (let ((skel (skeleton tree)))
    (equal skel (mirror skel))))

; ENDP / Lisp Machine Lisp
(defun endp (obj)
  (if (listp obj)
      (null obj)
    (if (null obj)
	t
      (ferror nil "The value ~S is not of type LIST." obj))))

;; Scheme 
(use util.match)

(define (mirror tree)
  (if (null? tree)
      '()
      (match-let (((root l r) tree))
	`(,root ,(mirror r) ,(mirror l)))))

(define (skeleton tree)
  (if (null? tree)
      '()
      (match-let (((root l r) tree))
	`(x ,(skeleton l) ,(skeleton r)))))

(define (symmetric tree)
  (let ((skel (skeleton tree)))
    (equal? skel (mirror skel))))