# Checking whether a word satisfies a template with wildcards

I'm working one of the recommended tutorials -- actually, the UPenn online course CS194 -- for learning Haskell, and I have a working solution to the final "challenge exercise" for HW 2. But it seems to be a very brute-force way of doing things, so I'm wondering if this is really the idiomatic Haskell way, or if I'm bringing my imperative programming habits in by accident.

The function is supposed to take a template representing a portion of a Scrabble board, and a set of tiles making up the Scrabble "hand", and see if you can legally play a given word within those constraints. The input would be:

• A Template - a string containing letters or '?' characters, representing empty spaces
• A Hand - a list of characters representing the available letters that can fill in the spaces.
• A Word - the string being checked to see if it fits the template.

A word "fits" the template if:

1. Every letter in the template matches the letter at that position in the word
2. Every '?' in the template can be replaced by the letter at that position in the word by removing it from the hand
3. '?' letters at the end of the template can also be "blank", if the template is longer than the word.

e.g.:

wordFitsTemplate "??r?" [’c’,’x’,’e’,’a’,’b’,’c’,’l’] "care" == True
wordFitsTemplate "??r?" [’c’,’x’,’e’,’w’,’b’,’c’,’l’] "care" == False
wordFitsTemplate "??r?" [’c’,’x’,’e’,’a’,’b’,’c’,’l’] "car" == True
wordFitsTemplate "let" [’x’,’x’] "let" == True


This is what I came up with; I feel like there are too many different patterns and guards that I should be able to condense somehow:

type Hand = [Char]
type Template = String

wordFitsTemplate :: Template -> Hand -> String -> Bool
wordFitsTemplate [] _ []            = True
wordFitsTemplate [] _ _             = False
wordFitsTemplate _ [] _             = False
wordFitsTemplate (t:ts) h []
| t == '?'                      = wordFitsTemplate ts h []
| otherwise                     = False
wordFitsTemplate ('?':ts) hs (s:ss)
| s elem hs                   = wordFitsTemplate ts (delete s hs) ss
| otherwise                     = False
wordFitsTemplate (t:ts) hs (s:ss)
| t == s                        = wordFitsTemplate ts hs ss
| otherwise                     = False

• There seems to be a lot of different possible cases, so it will be hard to compact many "legs" down. One thing I notice though is all the otherwise guards that end in False. Would it be possible to run the data through a pre-checker, then only continue if it returns True? That would at least cut out a few guards from this function. You might even be able to use a case structure to encapsulate the functions after the empty checks. Commented Nov 22, 2014 at 0:21

Let's omit the first 3 conditions (for now).

wordFitsTemplate :: Template -> Hand -> String -> Bool
wordFitsTemplate (t:ts) hs []
| t == '?'                      = wordFitsTemplate ts hs []
| otherwise                     = False
wordFitsTemplate ('?':ts) hs (s:ss)
| s elem hs                   = wordFitsTemplate ts (delete s hs) ss
| otherwise                     = False
wordFitsTemplate (t:ts) hs (s:ss)
| t == s                        = wordFitsTemplate ts hs ss
| otherwise                     = False


First, we can see that if we have an empty array, we're going to just check if the rest of the string is full of question marks. Let's reduce that case first. (This gives us the additional benefit of covering the case where we are given an empty template and string)

wordFitsTemplate :: Template -> Hand -> String -> Bool
wordFitsTemplate ts hs [] = all (== '?') ts
wordFitsTemplate ('?':ts) hs (s:ss)
| s elem hs                   = wordFitsTemplate ts (delete s hs) ss
| otherwise                     = False
wordFitsTemplate (t:ts) hs (s:ss)
| t == s                        = wordFitsTemplate ts hs ss
| otherwise                     = False


This is sort of messy, so let's introduce a helper function which checks a char from the template and the string. It returns a boolean indicating if it matches and the hand.

charFitsTemplate :: Char -> Hand -> Char -> (Bool, Hand)
charFitsTemplate t hand c
| t == '?' && c elem hand = (True, delete c hand)
| otherwise = (t == c, hand)


Let's redefine our wordFitsTemplate function now.

wordFitsTemplate :: Template -> Hand -> String -> Bool
wordFitsTemplate ts _ [] = all (== '?') ts
wordFitsTemplate (t:ts) hand (c:cs) = isFit && wordFitsTemplate ts newHand cs
where (isFit, newHand) = charFitsTemplate hand t c
wordFitsTemplate _ _ _ = False


It should be noted that when isFit evaluates to False, the function returns False; otherwise, when it evaluates to True, the result of the function depends on wordFitsTemplate ts newHand. Hence, we can combine them using &&.

This is the closest I could get to a nice solution. :) In functional programming, it's best to think of how to compartmentalize the problem and make it more elegant. In this case, we seperated the checking of whether a character matches (as well as the hand handling, no pun intended) with checking the template string. This gives us a rather elegant solution.