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-16

L-99 (57)

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

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

今回のお題は、数値のリストを二分探索木的に配置した

二分木を作成せよとのこと。

今回遭遇した謎:

問題自体には全く関係ないが、Scheme(Gauche)で、

(let ((foo 'foo))
  (let ((bar (list foo ())))
    `(,bar ,bar)))

の様に書くと、

(#0=(foo ()) #0#)

のような値が返ってくる。

DrSchemeでも、

(shared ((-1- (list 'foo empty) ) ) (list -1- -1-) )

の様になる。MzSchemeでは、意図通りに((foo () ) (foo () ) )

Schemeでは、(list foo foo)の代わりに、`(,foo ,foo)

のような書き方は良くないのだろうか。

P57

解答
;; Lisp Machine Lisp
(defun add-leaf (leaf tree)
  (let ((root (car tree))
	(left (cadr tree))
	(right (caddr tree))
	(node `(,leaf () ())))
    (if (<= leaf root)
	(if (null left)
	    `(,root ,node ,right)
	  `(,root ,(add-leaf leaf left) ,right))
      (if (null right)
	  `(,root ,left ,node)
	`(,root ,left ,(add-leaf leaf right))))))

(defun construct (lst)
  (and lst
       (do ((l (cdr lst) (cdr l))
	    (retlst `(,(car lst) () ())
		    (add-leaf (car l) retlst)))
	   ((null l) retlst))))

;; Common Lisp
(defun add-leaf (leaf tree)
  (let ((root (car tree))
	(left (cadr tree))
	(right (caddr tree))
	(node `(,leaf () ())))
    (if (<= leaf root)
	(if (endp left)
	    `(,root ,node ,right)
	    `(,root ,(add-leaf leaf left) ,right))
	(if (endp right)
	    `(,root ,left ,node)
	    `(,root ,left ,(add-leaf leaf right))))))

(defun construct (lst)
  (reduce #'(lambda (lst leaf) (add-leaf leaf lst))
	  (cdr lst) :initial-value `(,(car lst) () ())))  

;; Scheme
(define (add-leaf leaf tree)
  (let ((root  (list-ref tree 0))
	(left  (list-ref tree 1))
	(right (list-ref tree 2))
	(node (list leaf () ())))
    (if (<= leaf root)
	(if (null? left)
	    `(,root ,node ,right)
	    `(,root ,(add-leaf leaf left) ,right))
	(if (null? right)
	    `(,root ,left ,node)
	    `(,root ,left ,(add-leaf leaf right))))))

(define (construct lst)
  (fold add-leaf `(,(car lst) () ()) (cdr lst)))
;