[Haskell-cafe] Subsequence near solved hopefully
ketil+haskell at ii.uib.no
Sun Oct 17 15:53:10 EDT 2004
Peter Stranney <peterstranney at yahoo.co.uk> writes:
> 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
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
> | 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. :-)
If I haven't seen further, it is by standing in the footprints of giants
More information about the Haskell-Cafe