[Haskell-cafe] Subsequence near solved hopefully

[Ketil Malde]

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 
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