Treeから経路への変換

Scheme 30分プログラム

30分プログラム、その613。Treeから経路への変換。

例えば、こんな木があったとする。

(define *tree* (make-tree 'foo
			  (make-tree 'bar (make-tree 'baz))
			  (make-tree 'xyzzy)
			  (make-tree 'baz)))

で、これから、根から各末端への経路のリストを求める。例えば、この木の場合は次のようになる。

(foo)
(foo bar)
(foo bar baz)
(foo xyzzy)
(foo baz)

ホントは、この逆の変換がやりたかったんだけど、結構たいへんで30分じゃ無理だった。そのうち、再チャレンジする。

使い方

gosh> (tree->path-list *tree*)
((foo) (foo bar) (foo bar baz) (foo xyzzy) (foo baz))

ソースコード

#! /opt/local/bin/gosh
;; -*- mode:scheme; coding:utf-8 -*-
;;
;; tree.scm -
;;
;; Copyright(C) 2009 by mzp
;; Author: MIZUNO Hiroki / mzpppp at gmail dot com
;; http://howdyworld.org
;;
;; Timestamp: 2009/06/30 21:39:50
;;
;; This program is free software; you can redistribute it and/or
;; modify it under MIT Lincence.
;;
(use srfi-1)
(define (make-tree name . sub-trees)
  (list name sub-trees))
(define (tree-name tree)
  (car tree))
(define (sub-trees tree)
  (cadr tree))
(define (leaf? tree)
  (eq? tree '()))

(define (tree->path-list tree)
  (cons (list (tree-name tree))
	(map (cute cons (tree-name tree) <>)  (append-map tree->path-list (sub-trees tree)))))

(define *path-list* '((foo bar baz) (foo bar) (foo xyzzy) (foo baz)))
(define *tree* (make-tree 'foo
			  (make-tree 'bar (make-tree 'baz))
			  (make-tree 'xyzzy)
			  (make-tree 'baz)))

(tree->path-list *tree*)
(path-list->tree *path-list*)

(print (eq? *tree* (path-list->tree *path-list*)))

参考