Checking whether a word satisfies a template with wildcards

Question

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

Answer 1

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.