Friday, January 13, 2012

A small puzzle

Here's a quick little puzzle that isn't too hard.

A pattern is:
  1. A symbol, number, boolean, or null (an atom).
  2. A pattern variable, which is a two element list where the first element is the symbol ? and the second is a symbolic (a symbol) name.
    ;;   Examples:
    ;;     (pattern-variable? '(? foo))                      => #t
    ;;     (pattern-variable? '(? another-pattern-variable)) => #t
    ;;
    ;;     (pattern-variable? '(not a (pattern variable)))   => #f
    ;;     (pattern-variable? '(?))                          => #f
    ;;     (pattern-variable? '(foo ?))                      => #f
    ;;     (pattern-variable? '(? foo . bar))                => #f
    ;;     (pattern-variable? '(? foo quux))                 => #f
    
    (define (pattern-variable? thing)
      (and (pair? thing)
           (eq? (car thing) '?)
           (pair? (cdr thing))
           (symbol? (cadr thing))
           (null? (cddr thing))))
  3. A pair (a cons) of two patterns.
Write a program that given a pattern and some list structure (an object composed of pairs, numbers, symbols, nulls, etc.) returns an association list (an alist) of the pattern variable names and the associated matching elements, or #F if the pattern does not match.
;;  Examples:
;;   (pmatch '(foo (? pvar1) (? pvar2) bar) '(foo 33 #f bar))
;;      => ((pvar2 . #f) (pvar1 . 33))
;;
;;   (pmatch '(foo (? pvar) bar) '(quux 33 bar))
;;      => #f
;;
;;   (pmatch '(a (? var1) (nested (c (? var2)))) '(a b (nested (c d))))
;;      => ((var2 . d) (var1 . b))
;;
;;  Edge cases:
;;
;;   (pmatch '(a b c) '(a b c))
;;      => '()
;;
;;   (pmatch '(foo (? pvar1) (? pvar2) bar) '(foo 33 (xyzzy #f) bar))
;;      => ((pvar2 xyzzy #f) (pvar1 . 33))
;;
;;   (pmatch '(foo . (? pvar)) '(foo bar baz))
;;      => ((pvar bar baz))
;;
;;   (pmatch '((? ?) quux) '(foo quux))
;;      => ((? . foo))
;;
;;   (pmatch '(? ?) '(foo quux))
;;      => ((? foo quux))
;;
;;   (pmatch '(? ? ?) '(foo quux))
;;      => #f
Please be careful and obfuscate your solution if you want to post it.
Post a Comment