Haskell Boyer-Moore Implementation not working

  • (2 Pages)
  • +
  • 1
  • 2

18 Replies - 5663 Views - Last Post: 18 December 2012 - 02:59 PM

#1 Party Boy  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 13
  • Joined: 23-October 12

Haskell Boyer-Moore Implementation not working

Posted 18 December 2012 - 12:47 PM

How's it going.
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)) 


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

How's it going.
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.

Is This A Good Question/Topic? 0
  • +

Replies To: Haskell Boyer-Moore Implementation not working

#2 modi123_1  Icon User is offline

  • Suitor #2
  • member icon



Reputation: 8955
  • View blog
  • Posts: 33,571
  • Joined: 12-June 08

Re: Haskell Boyer-Moore Implementation not working

Posted 18 December 2012 - 12:53 PM

Quote

Man how do you edit posts I have no idea.

You have to hit the threshold of being here and how many posts you have created.
Was This Post Helpful? 0
  • +
  • -

#3 Party Boy  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 13
  • Joined: 23-October 12

Re: Haskell Boyer-Moore Implementation not working

Posted 18 December 2012 - 12:58 PM

I see, how many posts do I need to be able to edit?
Was This Post Helpful? 0
  • +
  • -

#4 modi123_1  Icon User is offline

  • Suitor #2
  • member icon



Reputation: 8955
  • View blog
  • Posts: 33,571
  • Joined: 12-June 08

Re: Haskell Boyer-Moore Implementation not working

Posted 18 December 2012 - 01:00 PM

http://www.dreaminco...-to-edit-times/
Was This Post Helpful? 0
  • +
  • -

#5 Party Boy  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 13
  • Joined: 23-October 12

Re: Haskell Boyer-Moore Implementation not working

Posted 18 December 2012 - 01:05 PM

Great thanks for the link.
Any idea on the code?
Was This Post Helpful? 0
  • +
  • -

#6 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2090
  • View blog
  • Posts: 3,185
  • Joined: 21-June 11

Re: Haskell Boyer-Moore Implementation not working

Posted 18 December 2012 - 01:14 PM

Define "not working". If you get an error during compilation or at runtime, please say so and post the error message (verbatim - preferably copy and pasted). If the function compiles and runs without error, but produces the wrong answer, please tell us which arguments you called the function with, what the result was and why that result is wrong/what the result should have been.

PS: Haskell questions should go in the "Function Programming" sub-forum. Please post there the next time.

This post has been edited by sepp2k: 18 December 2012 - 01:15 PM

Was This Post Helpful? 0
  • +
  • -

#7 modi123_1  Icon User is offline

  • Suitor #2
  • member icon



Reputation: 8955
  • View blog
  • Posts: 33,571
  • Joined: 12-June 08

Re: Haskell Boyer-Moore Implementation not working

Posted 18 December 2012 - 01:17 PM

Moved..
Was This Post Helpful? 0
  • +
  • -

#8 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2090
  • View blog
  • Posts: 3,185
  • Joined: 21-June 11

Re: Haskell Boyer-Moore Implementation not working

Posted 18 December 2012 - 01:27 PM

Also: When asking a question that you've already asked somewhere else or that's a follow-up to a question you've asked somewhere else, please:

  • Say so
  • Link to the question
  • Summarize which advice was given to you and what you did in response to the advice or why you couldn't follow up on that advice (like you didn't understand it or you tried to implement it, but failed for some reason)


If we don't know that you've asked the question somewhere else, we're likely to repeat advice that was already given to you, wasting everybody's time.

PS: You should also only ask questions somewhere else if you didn't get any answers after a reasonable amount of time on the site where you've originally posted or it was closed on the original site (i.e. you should not post to multiple sites simultaneously) - which you did (this time). You should also think about why your question was closed/not answered and, if necessary, improve it before you post it again somewhere else.
Was This Post Helpful? 0
  • +
  • -

#9 Party Boy  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 13
  • Joined: 23-October 12

Re: Haskell Boyer-Moore Implementation not working

Posted 18 December 2012 - 01:37 PM

Okay sure thing sorry about that.
I actually got Boyer Moore working. So now the only problems are things that I can expand on.
Basically the program works, however it doesn't seem to work for sort of special cases, such as if there are spaces, capital letters etc.

boyerMoore " hello" "hello" returns false, it should return true, is an example.
Just wondering, but from looking at the updated code, how should I handle these specialized areas?

Link to code: http://hpaste.org/79482
Was This Post Helpful? 0
  • +
  • -

#10 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2090
  • View blog
  • Posts: 3,185
  • Joined: 21-June 11

Re: Haskell Boyer-Moore Implementation not working

Posted 18 December 2012 - 01:49 PM

Why is your exit condition patternString > mainString? That does not seem right to me.

boyerMoore " hello" "hello" returns False because "h" > " " and thus "hello" > " hello".

You probably intended to compare the strings' lengths, so do that.

This post has been edited by sepp2k: 18 December 2012 - 01:53 PM

Was This Post Helpful? 0
  • +
  • -

#11 Party Boy  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 13
  • Joined: 23-October 12

Re: Haskell Boyer-Moore Implementation not working

Posted 18 December 2012 - 01:55 PM

Actually this isn't work really at all.

boyerMoore "howareyou" "are" returns false.
It's only true if its an exact match i.e

boyerMoore "hello" "hello"

Is patternString > mainString the exit condition? I thought it was just the if part, and if its greater than the main string it returns false, otherwise it goes into the rest of the code?
Was This Post Helpful? 0
  • +
  • -

#12 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2090
  • View blog
  • Posts: 3,185
  • Joined: 21-June 11

Re: Haskell Boyer-Moore Implementation not working

Posted 18 December 2012 - 02:03 PM

Yes, my point was: Are you sure you want patternString > mainString to be the condition for returning false?
Was This Post Helpful? 0
  • +
  • -

#13 Party Boy  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 13
  • Joined: 23-October 12

Re: Haskell Boyer-Moore Implementation not working

Posted 18 December 2012 - 02:10 PM

Well it would be one of the conditions wouldn't it?
If the user enters a pattern to search for in the main String, and the pattern is too long for the main string it should return false right? Or do you think I should have a separate if statement for that and use this if statement as something else?

Oh I just saw your edit there.
Yeah I made that change, silly mistake thanks.
So any idea how I can make it work?
I'm guessing it's something small I have left out that's making it not go through it right?
Was This Post Helpful? 0
  • +
  • -

#14 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2090
  • View blog
  • Posts: 3,185
  • Joined: 21-June 11

Re: Haskell Boyer-Moore Implementation not working

Posted 18 December 2012 - 02:13 PM

You seem to be under the impression that patternString > mainString compares the strings' lengths. As I indicated previously, it does not. It compares the strings lexicographically. So, as I said, "hello" > " hello" because 'h' > ' '. That's why boyerMoore " hello" "hello" returns False.

View PostParty Boy, on 18 December 2012 - 10:10 PM, said:

Oh I just saw your edit there.
Yeah I made that change, silly mistake thanks.
So any idea how I can make it work?


Does it not work after making that change?
Was This Post Helpful? 0
  • +
  • -

#15 Party Boy  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 13
  • Joined: 23-October 12

Re: Haskell Boyer-Moore Implementation not working

Posted 18 December 2012 - 02:19 PM

I changed it do

if (length patternString) > (length mainString)


And it still doesn't work.
It returns false if the pattern is larger than the main, which is good,
but if I say:

boyerMoore "hellomynameis" "my"

it returns false.
Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2