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

L-99 (73)

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

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

P72の問題に挑戦してみたけれど、問題の意図が分から

なかったので、飛してP73に挑戦。

お題は、多分岐ツリーをLisp的なリスト表現にする関数

の作成と、その逆変換をする関数の作成。

問題が進むにつれ、段々解答が正しいのか分からなくなっ

てきた。テストケースとかちゃんと書かないと駄目なの

かもしれない。

P73

解答
;; Common Lisp
(defun multiway-tree->lispy-token-list (tree)
  (cond	((atom tree) tree)
	((= 1 (length tree)) (car tree))
	('T `(,(multiway-tree->lispy-token-list (car tree))
	      ,@(mapcar #'multiway-tree->lispy-token-list
			(cdr tree))))))

(defun lispy-token-list->multiway-tree (tree)
  (labels ((frob (tree depth)
	     (cond ((and (zerop depth) (atom tree)) `(,tree))
		   ((atom tree) tree)
		   ('T `(,(frob (car tree) (1+ depth))
			  ,@(mapcar #'(lambda (n) 
					(if (atom n) 
					    `(,n) 
					    (frob n (1+ depth))))
				    (cdr tree)))))))
    (frob tree 0)))

;; Scheme 
(define (multiway-tree->lispy-token-list tree)
  (cond ((not (pair? tree)) tree)
	((= 1 (length tree)) (car tree))
	(else `(,(multiway-tree->lispy-token-list (car tree))
		,@(map multiway-tree->lispy-token-list
		       (cdr tree))))))

(define (lispy-token-list->multiway-tree tree)
  (let frob ((tree tree) 
	     (depth 0))
    (cond ((and (zero? depth) (not (pair? tree))) 
	   `(,tree))
	  ((not (pair? tree)) 
	   tree)
	  (else 
	   `(,(frob (car tree) (+ depth 1))
	     ,@(map (lambda (n) 
		      (if (pair? n) 
			  (frob n (+ depth 1))
			  `(,n)))
		    (cdr tree)))))))