-- This file is part of the 'term-rewriting' library. It is licensed
-- under an MIT license. See the accompanying 'LICENSE' file for details.
--
-- Authors: Christian Sternagel

module Data.Rewriting.Utils (
    dropCommonPrefix,
) where

-- | @dropCommonPrefix xs ys@ removes the common prefix of @xs@ and @ys@ and
-- returns the remaining lists as a pair.
--
-- >>>dropCommonPrefix [1,2,3] [1,2,4,1]
-- ([3], [4,1])
dropCommonPrefix :: Ord a => [a] -> [a] -> ([a], [a])
dropCommonPrefix :: forall a. Ord a => [a] -> [a] -> ([a], [a])
dropCommonPrefix (a
x:[a]
xs) (a
y:[a]
ys) | a
x a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
y = [a] -> [a] -> ([a], [a])
forall a. Ord a => [a] -> [a] -> ([a], [a])
dropCommonPrefix [a]
xs [a]
ys
dropCommonPrefix   [a]
xs     [a]
ys            = ([a]
xs, [a]
ys)