On Fri, Oct 10, 2014 at 5:18 AM, Jon Fairbairn <jon.fairbairn@cl.cam.ac.uk> wrote:

That seems rather wordy to me. Can we get anywhere starting with

It is rather wordy; I just don't know how to do better.

a `isSuffixOf` b = a `elem` tails b

and transforming? I’m not awake enough to the efficiency
implications, but

a `isSuffixOf` b = a `elem` (take 1 $ dropWhile (longerThan a) $ tails b)

longerThan _ [] = False
longerThan [] _ = True
longerThan (_:a) (_:b) = longerThan a b

looks plausible.

That looks bad. The implementation I gave is something like O(m+n), whereas yours looks something like O(m*n).