Hi Ian I think I have this thing lying around as well: On 27 Jun 2007, at 02:26, Ian Lynagh wrote:
dropPrefix :: Eq a => [a] -> [a] -> Maybe [a] dropPrefix [] ys = Just ys dropPrefix (x:xs) (y:ys) | x == y = dropPrefix xs ys dropPrefix _ _ = Nothing
But while I was grepping for it, I found I had written something slightly different. Recalling that Monoid w makes Applicative ((,) w), I have leftFactor :: Eq x => [x] -> [x] -> ([x], ([x], [x])) leftFactor (x : xs) (y : ys) | x == y = ([x], ()) *> leftFactor xs ys leftFactor xs ys = pure (xs, ys) Properties: if leftFactor xs ys = (zs, (xs', ys')) then zs is the longest list such that xs == zs ++ xs' ys == zs ++ ys' You get dropPrefix cheaply dropPrefix :: Eq a => [a] -> [a] -> Maybe [a] dropPrefix xs ys | (_, ([], zs)) <- leftFactor xs ys = Just zs | otherwise = Nothing but I also use it to do "common ancestor" calculations on hierarchical namespaces. Indeed, I have in the past used this thing on paths/contexts to determine whether two subterms of a given term were nested or not. A more frivolous usage is this variation on an ancient program: gcdList :: Eq x => [x] -> [x] -> Maybe [x] gcdList xs ys = case leftFactor xs ys of (_, ([], [])) -> Just xs (_, ([], zs)) -> gcdList xs zs (_, (zs, [])) -> gcdList zs ys _ -> Nothing gcdList xs ys calculates the largest zs such that xs == [1..m] >> zs and ys == [1..n] >> zs if any such exists. I was wondering what solutions there might be to xs ++ ys == ys ++ xs when out it popped! But I digress. It could well be that dropPrefix is much the more common, and hence that extra fuss required to get it from leftFactor isn't worth it, but I thought I'd punt out the possibility. As for whether these things should return in Maybe, or some arbitrary MonadPlus m, well, that seems like one instance of a wider question. We surely need a consistent policy here: do we target the specific *minimal* notion of computation supporting whatever it is (in this case, failure), or attempt to abstract an *arbitrary* such. If the latter, one should, of course, ask if Monad is too specific... Now I come to think about it, I quite like the minimal approach. It keeps the individual operations as simple as possible, and it pulls out the Maybe -> whatever homomorphism as a largest left factor. Or something. All the best Conor