## 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))
(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.

tonyg said...

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

Jrm said...

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

Jrm 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.