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.

3 comments:

tonyg said...

Is that final test case quite what you mean, in the light of clause 3 of the definition of patterns?

Joe Marshall said...

You're right, I blew it on that one. I'll have a correction in a few...

Joe Marshall said...

Nope, I changed my mind, the last one is correct, but tricky. The list (? ? ?) is not a pattern variable (because it has three elements), so it is a cons of two patterns. The first pattern is the symbol ?, which does not match the symbol foo, so the entire match fails.