Haskell shift right

Question

Still working on trying to implement Boyer Moore algorithm. Due in a few hours and I can't get this pesky shift part working. It works if there is a 1:1 match i.e boyerMoore "hello" "hello"

but it doesn't work for "howareyou" "are"

I'm almost certain my problem lies within the boyMoore area with the ifs.

I'm pretty sure that it's something in the boyerMoore function itself and not the shift methods. Just wondering if I am calling it in the right way or if I am over looking something? Appreciate any help. Also sorry for asking so many questions today, just want this assignment over and done with as it is our last one.

boyerMoore :: String -> String -> Bool
boyerMoore [] _ = False
boyerMoore mainString patternString =
    let 
    patternLength = (length patternString)
    position = getPosition patternString (take patternLength(mainString))
    in if (mainString == patternString)
        then True
        else
                if position > -1
                then boyerMoore (patternString) (drop position(mainString))
                else boyerMoore (patternString) (drop patternLength(mainString))

getPosition :: String -> String -> Int
getPosition [] _ = -1
getPosition mainString patternString = shift patternString mainString (length patternString)

shift :: String -> String -> Int -> Int
shift [] _ _ = -1
shift textString patternString lengthVariable =
    if (last patternString) == (last textString)
    then lengthVariable - (length patternString)
    else shift (init patternString) textString lengthVariable

Answer 1

Your final equation for boyerMoore starts

boyerMoore mainString patternString =

but the recursive calls at the end both have the form

boyerMoore patternString (drop foo mainString)

My knowledge of Boyer-Moore is rusty, but I doubt you want to swap patternString with mainString like that.

Secondly, I think you may be confusing the last() function on the page you link to with Haskell's last function. last gives back the final element of the list you give it, whereas last(), despite the notation, takes two arguments: a character to look for, and the pattern string to look in.