When I use sub_string("abberr","habberyry") , it returns True, when obviously it should be False. The point of the function is to search for the first argument within the second one. Any ideas what's wrong?
sub_string :: (String, String) -> Bool
sub_string(_,[]) = False
sub_string([],_) = True
sub_string(a:x,b:y) | a /= b = sub_string(a:x,y)
| otherwise = sub_string(x,y)
Let me give you hints on why it's not working:
And "r" is a subset of "yry". So it returns True. To illustrate a more simple example of your problem:
*Main> sub_string("rz","rwzf")
True
First off, you need to switch your first two lines. _ will match [] and this will matter when you're matching, say, substring "abc" "abc". Secondly, it is idiomatic Haskell to write a function with two arguments instead of one with a pair argument. So your code should start out:
substring :: String -> String -> Bool
substring [] _ = True
substring _ [] = False
substring needle (h : aystack)
| ...
Now we get to the tricky case where both of these lists are not empty. Here's the problem with recursing on substring as bs: you'll get results like "abc" being a substring of "axbxcx" (because "abc" will match 'a' first, then will look for "bc" in the rest of the string; the substring algorithm will then skip past the 'x' to look for "bc" in "bxcx", which will match 'b' and look for "c" in "xcx", which will return True.
Instead your condition needs to be more thorough. If you're willing to use functions from Data.List this is:
| isPrefixOf needle (h : aystack) = True
| otherwise = substring needle aystack
Otherwise you need to write your own isPrefixOf, for example:
isPrefixOf needle haystack = needle == take (length needle) haystack
$needle and $haystack to show the order of the arguments. Idiomatic Haskell would probably instead be type Needle = String etc.As Sibi already pointed out, your function tests for subsequence. Review the previous exercise, it is probably isPrefixof (hackage documentation), which is just a fancy way of saying startsWith, which looks very similar to the function you wrote.
If that is not the previous exercise, do that now!
Then write sub_string in terms of isPrefixOf:
sub_string (x, b:y) = isPrefixOf ... ?? ???
Fill in the dots and "?" yourself.
