Peter Stranney
Thanks guys for all your help, finally through code, sweat and tears i have found the solution;
Well done! I hope you don't mind some further comments?
isSubStrand:: String -> String -> Bool isSubStrand [] [] = True isSubStrand [] (y:ys) = False
You can just call it "ys" here, since the [] case is handled above. Although I see the point of using the pattern to make it explicit. Or you could write the two lines as isSubStrand [] ys = null ys -- null returns a Bool, True iff []
isSubStrand (x:xs) [] = False isSubStrand (x:xs) (y:ys) | length(x:xs)>length(y:ys) = False
You may think of this as an optimization, but it is the opposite - it will count up both lists at each iteration, making the algorithm O(n^2) complexity. Here I'd drop the (x:xs) pattern, and just use xs and ys.
| take (length (x:xs)) (y:ys)==(x:xs) = True
This is also inefficient; length traverses the xs, and equality does it again (until a mismatch) - and look up "isPrefixOf" in the Prelude!
| otherwise = isSubStrand (x:xs) ys
BTW, in addition to "isPrefixOf", look at the function "tails" (also in the List module), and see if you can come up with a short, elegant and efficient solution using these two functions. :-) -kzm -- If I haven't seen further, it is by standing in the footprints of giants