どう書く.orgの問題(親子のペアからツリーを構築)

http://ja.doukaku.org/178/
hash-tableを使うととても簡単に書ける。
親を探すコストの低い方法はないのかな？

(use srfi-1)
(use util.match)

(define pair-lst '((a b) (b c) (c d) (c e) (a f) (d x) (y z) (z c)))

(define (alist->tree alist)
  (let1 ht (make-hash-table)
    (define (replace k)
      (let1 vs (hash-table-get ht k #f)
	(if vs (cons k (reverse (map replace vs))) k)))
    (receive (ks vs) (unzip2 alist)
      (for-each (lambda (k v) (hash-table-push! ht k v)) ks vs)
      (let1 parents (lset-difference eq? ks vs)
	(map replace (delete-duplicates parents))))))

(define (show-tree tree)
  (define (show elt d)
    (if (list? elt)
	(match-let1 (head . tail) elt
	  (show head d)
	  (for-each (cute show <> (+ d 2)) tail))
	(print (make-string d #\space) "->" elt)))
  (for-each (cut show <> 0) tree))

(show-tree (alist->tree pair-lst))

->a
  ->b
    ->c
      ->d
        ->x
      ->e
  ->f
->y
  ->z
    ->c
      ->d
        ->x
      ->e