Proposal #1464: add dropPrefix to Data.List

[Conor McBride]

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