Cute interview question solution

expressionmatch.hs

import qualified Data.Map.Strict as Map
import Data.List (inits, tails, any)

match ""   ""   _       = True
match ""   _    _       = False
match _    ""   _       = False
match expr text matches = let
  possibilities  = zip (tail $ inits text) (tail $ tails text)
  pattern        = head expr
  expr'          = tail expr
  possibilities' = if (Map.member pattern matches)
    then filter (\(m, _) -> (matches Map.! pattern) == m) possibilities
    else possibilities
  branches       = map (step expr' pattern matches) possibilities'
  in any id branches
  where 
    step exp pat matches (mat, rest) = let
      matches' = Map.insert pat mat matches
      in match exp rest matches'


match' expr text = match expr text Map.empty

main = do
  print $ match' "abba" "catdogdogcat"
  print $ match' "abab" "catdogcatdog"