Search Function With Wildcard in Haskell

Question

I'm teaching myself how to program Haskell, and I decided to make a find function in Haskell. What it does is it takes two strings, such as "hello" and "he", and it counts how many times "he" appears in "hello". In addition, it also uses the * character as a wildcard, so searching for "he*o" in "hello" will return 1.

Latest Update

This update used pattern matching and less guards, and also outputs 1 if ssearch "blah" "*".

ssearch _ [] = 0
ssearch [] _ = 0
ssearch ('*':_) _ = error "no '*' allowed in hay"
ssearch _ ['*'] = 1
ssearch haystack ('*':needles) = ssearch haystack needles --removes '*', and then searches through hay for the char after the '*'
ssearch (hay:haystack) (needle:needles)
  | needle == hay = search2 haystack needles + ssearch haystack (needle:needles) 
  | otherwise = ssearch haystack (needle:needles) 
    where
    search2 _ [] = 1
    search2 [] _ = 0
    search2 ('*':_) _ = error "no '*' allowed in hay" -- I need to declare this twice because search2 often jumps ahead of ssearch.
    search2  _ ['*'] = 1
    search2 haystack ('*':needles) = ssearch haystack needles
    search2 (hay:haystack) (needle:needles)
      | needle == hay = search2 haystack needles 
          | otherwise = 0

Update:

Thinking over dave4420's comments, I decided to redo the entire algorithm. I think that it fixes most of the bugs.

ssearch _ [] = 0
ssearch [] _ = 0
ssearch (hay:haystack) (needle:needles)
  | hay == '*' = error "no '*' allowed in hay" --no confusion with wildcard things
  | needle == '*' = ssearch (hay:haystack) needles --removes '*', and then searches through hay for the char after the '*'
  | needle == hay = search2 haystack needles + ssearch haystack (needle:needles) 
  | otherwise = ssearch haystack (needle:needles) 
    where
    search2 _ [] = 1
    search2 [] _ = 0
    search2 (hay:haystack) (needle:needles)
      | hay == '*' = error "no '*' allowed in hay" -- I need to declare this twice because search2 often jumps ahead of ssearch.
      | (needle == '*') && (needles /= []) = ssearch (hay:haystack) needles 
      | (needle == '*') && (needles == []) = 1 
      | needle == hay = search2 haystack needles 
          | otherwise = 0

I'm wondering if there are still any bugs, and also, if there is any way I can improve this code.

Old Code

search :: String -> String -> Integer
search x y = search1 x y y 0 -- n is set to 0, because nothing has been found yet :)
  where
    search1 :: String -> String -> String -> Integer -> Integer
    search1 _ _ [] n = n -- z can't be empty
    search1 x [] z n = search1 x z z (n+1) -- if y is empty but x isn't, it means the word was found, and y needs to be reset
    search1 [] _ _ n = n --end the program, bc if x is empty, the program has searched through the entire string
    search1 (x:xs) (y:ys) z n
      | x == '*' = error "you can not enter the character '*' in the first field: the '*' character is reserved for wildcard searches"
      | (y == '*') && ((head ys) == '*') = error "You can not include two '**' in a row, that messes up the wildcard operator"
      | x == y = search1 xs (ys) z n
      | (y == '*') && (ys /= []) = if (x == (head ys)) --this section is so search "hello" "h*llo" = 1
                        then search1 (x:xs) ys z n --if the string matches up with the rest of the string, excluding the '*', then redu the query, excluding the '*'
                       else search1 xs (y:ys) z n --} --otherwise keep on searching for the wildcard thing
      | (y == '*') && (ys == []) = n + 1 -- so search "hello" "*" = 1
      | otherwise = search1 xs z z n -- don't include (y:ys), otherwise search "hihe" "hhe" = 1

Answer 1

Update

Yes, that's better.

Here is a version of your code that uses pattern matching more and guards less. I think it is clearer.

ssearch _ [] = 0
ssearch [] _ = 0
ssearch ('*' : _) _ = error "no '*' allowed in hay" --no confusion with wildcard things
ssearch haystack ('*' : needles) = ssearch haystack needles --removes '*', and then searches through hay for the char after the '*'
ssearch (hay:haystack) (needle:needles)
  | needle == hay = search2 haystack needles + ssearch haystack (needle:needles) 
    where
    search2 _ [] = 1
    search2 [] _ = 0
    search2 ('*' : _) _ = error "no '*' allowed in hay" -- I need to declare this twice because search2 often jumps ahead of ssearch.
    search2 _ ['*'] = 1 
    search2 haystack ('*' : needles) = ssearch haystack needles 
    search2 (hay:haystack) (needle:needles)
      | needle == hay = search2 haystack needles 
    search2 _ _ = 0
ssearch (_:haystack) needles = ssearch haystack needles

There may still be bugs, but I can't see any :-)

Original

1. It appears to be buggy.

   • I expect search "hello" "he*lo" to result in 1, but it gives me 0.
   • I expect search "chanchance" "chance" to result in 1, but it gives me 0.

   Also

   • search "bobobob" "bob" results in 2, but perhaps it should result in 3. Whether or not you want your function to count overlapping matches, you should document that it does/doesn't.

   You need to rethink your algorithm. (Edit: as you are learning Haskell, I presume you'd rather get your function working yourself, rather than have us spoon-feed you a working version.)

2. x and y are not very descriptive names. They are suitable when you are writing generic code, but this code is more specific. I would call them haystack and needle instead (from the common English phrase).

3. This line:

     | (y == '*') && ((head ys) == '*') = error "You can not include two '**' in a row, that messes up the wildcard operator"
   

   • ys may be [], so head ys may be an error. You should be using pattern matching instead of head (and often instead of comparing to [] as well).
   • Why should a second * be an error anyway? The second * should successfully match a run of 0 characters, surely?