Lambdaカクテル

集団への盲従を激しく嫌う

Common Lispで木構造の一部にパターンマッチさせてみた(optima)

パターンマッチングライブラリのoptimaで遊んでみた。ちょっと応用して入れ子になったリストの一部分にパターンがマッチするか検査する処理を書いてみた。将来的にはパースしたHTMLの部分マッチさせて抽出する処理に使ってみたい。

まずこういうリストがあるとする。

'(1 2 3 4 (5 6 (7 8) 9) 0))

このリストに(6 (7 8) X) (ここでXは何でもよい)であるような部分があるかを、Common Lispで確かめてみたい。

#!/bin/sh
#|-*- mode:lisp -*-|#
#| <Put a one-line description here>
exec ros -Q -- $0 "$@"
|#
(progn ;;init forms
  (ros:ensure-asdf)
  #+quicklisp (ql:quickload '(:optima) :silent t)
  )

(defpackage :ros.script.optimatest.3735458529
  (:use :cl :optima))
(in-package :ros.script.optimatest.3735458529)

;;; ここからメインロジック

;; 探索対象のリスト
(defparameter *lis* '(1 2 3 4 (5 6 (7 8) 9) 0))

;; リストを探索する関数。マッチしなければcar、cdrを再帰的に試していく。
(defun walk (lis)
  (match lis
    ((list 6 '(7 8) _) ; この条件にマッチさせたい
     (format t "~S ;matched.~%" lis)
     t)
    ((null _)
     (format t "null. failing back...~%") nil)
    ((list) (format t "empty list. falling back...~%") nil)
    ((cons a b)
     (or
      (format t "~S ;cons. walking car...~%" lis)
      (walk a)
      (format t "~S ;car failed. walking cdr...~%" lis)
      (walk b)))))

(defun main (&rest argv)
  (declare (ignorable argv))
  (walk *lis*))
;;; vim: set ft=lisp lisp:
windymelt% ./optimatest.ros
(1 2 3 4 (5 6 (7 8) 9) 0) ;cons. walking car...
(1 2 3 4 (5 6 (7 8) 9) 0) ;car failed. walking cdr...
(2 3 4 (5 6 (7 8) 9) 0) ;cons. walking car...
(2 3 4 (5 6 (7 8) 9) 0) ;car failed. walking cdr...
(3 4 (5 6 (7 8) 9) 0) ;cons. walking car...
(3 4 (5 6 (7 8) 9) 0) ;car failed. walking cdr...
(4 (5 6 (7 8) 9) 0) ;cons. walking car...
(4 (5 6 (7 8) 9) 0) ;car failed. walking cdr...
((5 6 (7 8) 9) 0) ;cons. walking car...
(5 6 (7 8) 9) ;cons. walking car...
(5 6 (7 8) 9) ;car failed. walking cdr...
(6 (7 8) 9) ;matched.

マッチした場合は値を変数に入れて取り出すこともできるので、さらに処理していくこともできそうだ。

まとめ

  • car/cdrを再帰的に歩くことで部分マッチを検索できそう。
  • car/cdrがあっても絶対にマッチしない場合があるので、その場合の枝刈りもできそう。
    • carしかない場合など

リンク

qiita.com

github.com