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 |

2008-07-18

SERIESでツリーマッチング

| 01:36 | SERIESでツリーマッチング - わだばLisperになる を含むブックマーク はてなブックマーク - SERIESでツリーマッチング - わだばLisperになる

独習 Scheme 三週間 Teach Yourself Scheme in Fixnum Daysでは、ジェネレータを使うことによって、2つのツリーをflattenして比較するよりも効率の良いツリーマッチングを実現しているわけなのですが、SERIESは遅延評価なので効率良く似たようなことができるだろうということで色々考えてみました。

(same-fringe? '(1 (2 3)) '((1 2) 3))
(same-fringe? '(1 (2 3)) '(1 2 3))
;=> T

(same-fringe? '(1 (2 3)) '((1 2) 3 4))
;=> nil

;; コード
(use-package :series)
(series::install) ;#Mや、#Z等のリーダーマクロを使うため

;; 1
(defun same-fringe? (tree1 tree2)
  (let ((t1 (scan-lists-of-lists-fringe tree1))
        (t2 (scan-lists-of-lists-fringe tree2)))
    (and (collect-and (#Mequal t1 t2))
         (= (collect-length t1) (collect-length t2)))))

;; 2 割と無理やりにgeneratorを使ってみたもの
(defun same-fringe? (tree1 tree2)
  (let ((t1 (scan-lists-of-lists-fringe tree1))
        (t2 (scan-lists-of-lists-fringe tree2)))
    (let ((g1 (generator t1))
          (g2 (generator t2))
          (limit (max (collect-length t1) (collect-length t2))))
      (loop :repeat limit :always (equal (next-in g1) (next-in g2))))))

1は、割と普通に書いてみました。SERIESは基本的に短い方に長さが揃えられてしまうので、長さを計っています。長さを計らなければ、無限リストにも対応できますが、今度は、(1 2 3 .....)と、(1 2 3)の場合で真が返ってしまいます。

2は、オリジナルがジェネレータ使用ということで、generatorを使ってみたのですが、いまいちです。

そもそも、collect-lengthを使ってしまった時点で駄目な気がしますが、どうやったら良いんでしょうー。