Implement glob Matcher Implement a function of pattern and string to be matched, return true if the pattern matches the WHOLE string, otherwise false.

Our glob pattern syntax is:


? matches any one character
+ matches one or more characters
* matches zero or more characters
\ escapes


Rules:


No eval, no converting into regular expression, no calling a system glob function.
I/O are not required: you can just write a function
Shortest wins


Examples:

glob('abc', 'abc') =&gt; true
glob('abc', 'abcdef') =&gt; false IMPORTANT!
glob('a??', 'aww') =&gt; true
glob('a*b', 'ab') =&gt; true
glob('a*b', 'agwijgwbgioeb') =&gt; true
glob('a*?', 'a') =&gt; false
glob('?*', 'def') =&gt; true
glob('5+', '5ggggg') =&gt; true
glob('+', '') =&gt; false
glob('a\*b', 'a*b') =&gt; true


Here is a tip to get started: http://en.wikipedia.org/wiki/Backtracking
Haskell, 141 characters

c('\\':a:z)s=a&amp;s&gt;&gt;=c z
c(a:z)s=a%s&gt;&gt;=c z
c[]s=[null s]
p&amp;(a:z)|a==p=[z]
_&amp;_=[]
'?'%(a:z)=[z]
'*'%a=a:'+'%a
'+'%(a:z)='*'%z
l%a=l&amp;a
g=(or.).c


Works for all input, both patterns and strings to match against. Handles trailing backslash in the pattern as a literal match (behavior was unspecified.)

This can be run with the following test driver:

main = do
    globtest "abc" "abc"    True
    globtest "abc" "abcdef" False
    globtest "a??" "aww"    True
    globtest "a*b" "ab"     True
    globtest "a*b" "agwijgwbgioeb" True
    globtest "a*?" "a"      False
    globtest "?*" "def"     True
    globtest "5+" "5ggggg"  True
    globtest "+" ""         False
    globtest "a\\*b" "a*b"  True
  where
    globtest p s e =
      if g p s == e
        then putStrLn "pass"
        else putStrLn$"fail: g " ++ show p ++ " " ++ show s ++ " /= " ++ show e




Update: I wrote a blog post about this particular answer, as I think it shows off well how Haskell so easily encodes the problem.




Edit: (181 -> 174) replaced d and m with operators
Edit: (174 -> 151) inlined r into c
Edit: (151 -> 149) removed an unnecessarily generated option in the + case
Edit: (149 -> 141) removed an unnecessary clause for %, which was handled by &amp;