So for the second part of my assignment I have to implement Boyer-Moore, and I am having some trouble with it.

I'm new to Haskell so I don't know the language very well.

I feel like the Boyer-Moore implementation I have is on the right track to getting it fully working but it's sadly not working.

I'm probably glancing over some obvious mistakes but I was hoping somebody here could help me out.

Would appreciate any feedback.

Thanks!

shift :: String -> String -> Int -> Int --take 2 strings and an int, returns int shift [] _ _ = -1 --if empty set return -1 shift mString pString pLength = --using main string, pattern string and length of main string if last pString == last mString --if last element in pattern string equals last element of main string then pLength - (length pString) -- then main length is take away length of pattern else shift (init pString) mString pLength --or else call shift again using every elemnt besides the last in the pString findPosition :: String -> String -> Int --take 2 strings return int, which is position findPosition [] _ = -1 --if empty set return -1 findPosition main pattern = shift main pattern (length pattern) --call shift method using length of pattern boyerMoore :: String -> String -> Bool -- take 2 strings give back a boolean boyerMoore [] _ = False -- if there is an empty set return false boyerMoore mainString patternString = -- 3 variables if patternString > mainString -- if the pattern is greater than the main string then False -- return false else if patternString == mainString --else if they are the same then True -- return true else let patternLength = length patternString --assign the length of patter to patternLength position = findPosition patternString (take patternLength (mainString)) --position will find position of pattern string in the mainstring in if patternString == mainString --if patternstring is equal to main string then True --return true else position == boyerMoore patternString (drop position (mainString))

Whoops uploaded the version with comments, which turned out ugly in the main post, didn't see an edit button.

Here is the implementation without comments:

shift :: String -> String -> Int -> Int shift [] _ _ = -1 shift mString pString pLength = if last pString == last mString then pLength - (length pString) else shift (init pString) mString pLength findPosition :: String -> String -> Int findPosition [] _ = -1 findPosition main pattern = shift main pattern (length pattern) boyerMoore :: String -> String -> Bool boyerMoore [] _ = False boyerMoore mainString patternString = if patternString > mainString then False else if patternString == mainString then True else let patternLength = length patternString position = findPosition patternString (take patternLength (mainString)) in if patternString == mainString then True else position == boyerMoore patternString (drop position (mainString))

Party Boy, on 18 December 2012 - 12:45 PM, said:

So for the second part of my assignment I have to implement Boyer-Moore, and I am having some trouble with it.

I'm new to Haskell so I don't know the language very well.

I feel like the Boyer-Moore implementation I have is on the right track to getting it fully working but it's sadly not working.

I'm probably glancing over some obvious mistakes but I was hoping somebody here could help me out.

Would appreciate any feedback.

Thanks!

shift :: String -> String -> Int -> Int shift [] _ _ = -1 shift mString pString pLength = if last pString == last mString then pLength - (length pString) else shift (init pString) mString pLength findPosition :: String -> String -> Int findPosition [] _ = -1 findPosition main pattern = shift main pattern (length pattern) boyerMoore :: String -> String -> Bool boyerMoore [] _ = False boyerMoore mainString patternString = if patternString > mainString then False else if patternString == mainString then True else let patternLength = length patternString position = findPosition patternString (take patternLength (mainString)) in if patternString == mainString then True else position == boyerMoore patternString (drop position (mainString))

Man how do you edit posts I have no idea.