{-# LANGUAGE Haskell2010, FlexibleInstances, Trustworthy #-}
module Data.Monoid.GCD (
GCDMonoid(..),
LeftGCDMonoid(..), RightGCDMonoid(..), OverlappingGCDMonoid(..)
)
where
import qualified Prelude
import Data.Monoid
import qualified Data.ByteString as ByteString
import qualified Data.ByteString.Unsafe as ByteString
import qualified Data.ByteString.Lazy as LazyByteString
import qualified Data.Text as Text
import qualified Data.Text.Internal as Internal
import qualified Data.Text.Internal.Lazy as LazyInternal
import Data.Text.Unsafe (lengthWord16, reverseIter)
import qualified Data.Text.Lazy as LazyText
import qualified Data.IntMap as IntMap
import qualified Data.IntSet as IntSet
import qualified Data.Map as Map
import qualified Data.Sequence as Sequence
import qualified Data.Set as Set
import Data.Sequence (ViewL((:<)), ViewR((:>)), (<|), (|>))
import qualified Data.Vector as Vector
import Numeric.Natural (Natural)
import Data.Semigroup.Cancellative
import Data.Monoid.Monus
import Prelude hiding (gcd)
class (Monoid m, Commutative m, Reductive m, LeftGCDMonoid m, RightGCDMonoid m, OverlappingGCDMonoid m) => GCDMonoid m where
gcd :: m -> m -> m
class (Monoid m, LeftReductive m) => LeftGCDMonoid m where
commonPrefix :: m -> m -> m
stripCommonPrefix :: m -> m -> (m, m, m)
commonPrefix x :: m
x y :: m
y = m
p
where (p :: m
p, _, _) = m -> m -> (m, m, m)
forall m. LeftGCDMonoid m => m -> m -> (m, m, m)
stripCommonPrefix m
x m
y
stripCommonPrefix x :: m
x y :: m
y = (m
p, m
x', m
y')
where p :: m
p = m -> m -> m
forall m. LeftGCDMonoid m => m -> m -> m
commonPrefix m
x m
y
Just x' :: m
x' = m -> m -> Maybe m
forall m. LeftReductive m => m -> m -> Maybe m
stripPrefix m
p m
x
Just y' :: m
y' = m -> m -> Maybe m
forall m. LeftReductive m => m -> m -> Maybe m
stripPrefix m
p m
y
{-# MINIMAL commonPrefix | stripCommonPrefix #-}
class (Monoid m, RightReductive m) => RightGCDMonoid m where
commonSuffix :: m -> m -> m
stripCommonSuffix :: m -> m -> (m, m, m)
commonSuffix x :: m
x y :: m
y = m
s
where (_, _, s :: m
s) = m -> m -> (m, m, m)
forall m. RightGCDMonoid m => m -> m -> (m, m, m)
stripCommonSuffix m
x m
y
stripCommonSuffix x :: m
x y :: m
y = (m
x', m
y', m
s)
where s :: m
s = m -> m -> m
forall m. RightGCDMonoid m => m -> m -> m
commonSuffix m
x m
y
Just x' :: m
x' = m -> m -> Maybe m
forall m. RightReductive m => m -> m -> Maybe m
stripSuffix m
s m
x
Just y' :: m
y' = m -> m -> Maybe m
forall m. RightReductive m => m -> m -> Maybe m
stripSuffix m
s m
y
{-# MINIMAL commonSuffix | stripCommonSuffix #-}
instance GCDMonoid () where
gcd :: () -> () -> ()
gcd () () = ()
instance LeftGCDMonoid () where
commonPrefix :: () -> () -> ()
commonPrefix () () = ()
instance RightGCDMonoid () where
commonSuffix :: () -> () -> ()
commonSuffix () () = ()
instance GCDMonoid a => GCDMonoid (Dual a) where
gcd :: Dual a -> Dual a -> Dual a
gcd (Dual a :: a
a) (Dual b :: a
b) = a -> Dual a
forall a. a -> Dual a
Dual (a -> a -> a
forall m. GCDMonoid m => m -> m -> m
gcd a
a a
b)
instance LeftGCDMonoid a => RightGCDMonoid (Dual a) where
commonSuffix :: Dual a -> Dual a -> Dual a
commonSuffix (Dual a :: a
a) (Dual b :: a
b) = a -> Dual a
forall a. a -> Dual a
Dual (a -> a -> a
forall m. LeftGCDMonoid m => m -> m -> m
commonPrefix a
a a
b)
instance RightGCDMonoid a => LeftGCDMonoid (Dual a) where
commonPrefix :: Dual a -> Dual a -> Dual a
commonPrefix (Dual a :: a
a) (Dual b :: a
b) = a -> Dual a
forall a. a -> Dual a
Dual (a -> a -> a
forall m. RightGCDMonoid m => m -> m -> m
commonSuffix a
a a
b)
instance GCDMonoid (Sum Natural) where
gcd :: Sum Natural -> Sum Natural -> Sum Natural
gcd (Sum a :: Natural
a) (Sum b :: Natural
b) = Natural -> Sum Natural
forall a. a -> Sum a
Sum (Natural -> Natural -> Natural
forall a. Ord a => a -> a -> a
min Natural
a Natural
b)
instance LeftGCDMonoid (Sum Natural) where
commonPrefix :: Sum Natural -> Sum Natural -> Sum Natural
commonPrefix a :: Sum Natural
a b :: Sum Natural
b = Sum Natural -> Sum Natural -> Sum Natural
forall m. GCDMonoid m => m -> m -> m
gcd Sum Natural
a Sum Natural
b
instance RightGCDMonoid (Sum Natural) where
commonSuffix :: Sum Natural -> Sum Natural -> Sum Natural
commonSuffix a :: Sum Natural
a b :: Sum Natural
b = Sum Natural -> Sum Natural -> Sum Natural
forall m. GCDMonoid m => m -> m -> m
gcd Sum Natural
a Sum Natural
b
instance GCDMonoid (Product Natural) where
gcd :: Product Natural -> Product Natural -> Product Natural
gcd (Product a :: Natural
a) (Product b :: Natural
b) = Natural -> Product Natural
forall a. a -> Product a
Product (Natural -> Natural -> Natural
forall a. Integral a => a -> a -> a
Prelude.gcd Natural
a Natural
b)
instance LeftGCDMonoid (Product Natural) where
commonPrefix :: Product Natural -> Product Natural -> Product Natural
commonPrefix a :: Product Natural
a b :: Product Natural
b = Product Natural -> Product Natural -> Product Natural
forall m. GCDMonoid m => m -> m -> m
gcd Product Natural
a Product Natural
b
instance RightGCDMonoid (Product Natural) where
commonSuffix :: Product Natural -> Product Natural -> Product Natural
commonSuffix a :: Product Natural
a b :: Product Natural
b = Product Natural -> Product Natural -> Product Natural
forall m. GCDMonoid m => m -> m -> m
gcd Product Natural
a Product Natural
b
instance (GCDMonoid a, GCDMonoid b) => GCDMonoid (a, b) where
gcd :: (a, b) -> (a, b) -> (a, b)
gcd (a :: a
a, b :: b
b) (c :: a
c, d :: b
d) = (a -> a -> a
forall m. GCDMonoid m => m -> m -> m
gcd a
a a
c, b -> b -> b
forall m. GCDMonoid m => m -> m -> m
gcd b
b b
d)
instance (LeftGCDMonoid a, LeftGCDMonoid b) => LeftGCDMonoid (a, b) where
commonPrefix :: (a, b) -> (a, b) -> (a, b)
commonPrefix (a :: a
a, b :: b
b) (c :: a
c, d :: b
d) = (a -> a -> a
forall m. LeftGCDMonoid m => m -> m -> m
commonPrefix a
a a
c, b -> b -> b
forall m. LeftGCDMonoid m => m -> m -> m
commonPrefix b
b b
d)
instance (RightGCDMonoid a, RightGCDMonoid b) => RightGCDMonoid (a, b) where
commonSuffix :: (a, b) -> (a, b) -> (a, b)
commonSuffix (a :: a
a, b :: b
b) (c :: a
c, d :: b
d) = (a -> a -> a
forall m. RightGCDMonoid m => m -> m -> m
commonSuffix a
a a
c, b -> b -> b
forall m. RightGCDMonoid m => m -> m -> m
commonSuffix b
b b
d)
instance (GCDMonoid a, GCDMonoid b, GCDMonoid c) => GCDMonoid (a, b, c) where
gcd :: (a, b, c) -> (a, b, c) -> (a, b, c)
gcd (a1 :: a
a1, b1 :: b
b1, c1 :: c
c1) (a2 :: a
a2, b2 :: b
b2, c2 :: c
c2) = (a -> a -> a
forall m. GCDMonoid m => m -> m -> m
gcd a
a1 a
a2, b -> b -> b
forall m. GCDMonoid m => m -> m -> m
gcd b
b1 b
b2, c -> c -> c
forall m. GCDMonoid m => m -> m -> m
gcd c
c1 c
c2)
instance (LeftGCDMonoid a, LeftGCDMonoid b, LeftGCDMonoid c) => LeftGCDMonoid (a, b, c) where
commonPrefix :: (a, b, c) -> (a, b, c) -> (a, b, c)
commonPrefix (a1 :: a
a1, b1 :: b
b1, c1 :: c
c1) (a2 :: a
a2, b2 :: b
b2, c2 :: c
c2) = (a -> a -> a
forall m. LeftGCDMonoid m => m -> m -> m
commonPrefix a
a1 a
a2, b -> b -> b
forall m. LeftGCDMonoid m => m -> m -> m
commonPrefix b
b1 b
b2, c -> c -> c
forall m. LeftGCDMonoid m => m -> m -> m
commonPrefix c
c1 c
c2)
instance (RightGCDMonoid a, RightGCDMonoid b, RightGCDMonoid c) => RightGCDMonoid (a, b, c) where
commonSuffix :: (a, b, c) -> (a, b, c) -> (a, b, c)
commonSuffix (a1 :: a
a1, b1 :: b
b1, c1 :: c
c1) (a2 :: a
a2, b2 :: b
b2, c2 :: c
c2) = (a -> a -> a
forall m. RightGCDMonoid m => m -> m -> m
commonSuffix a
a1 a
a2, b -> b -> b
forall m. RightGCDMonoid m => m -> m -> m
commonSuffix b
b1 b
b2, c -> c -> c
forall m. RightGCDMonoid m => m -> m -> m
commonSuffix c
c1 c
c2)
instance (GCDMonoid a, GCDMonoid b, GCDMonoid c, GCDMonoid d) => GCDMonoid (a, b, c, d) where
gcd :: (a, b, c, d) -> (a, b, c, d) -> (a, b, c, d)
gcd (a1 :: a
a1, b1 :: b
b1, c1 :: c
c1, d1 :: d
d1) (a2 :: a
a2, b2 :: b
b2, c2 :: c
c2, d2 :: d
d2) = (a -> a -> a
forall m. GCDMonoid m => m -> m -> m
gcd a
a1 a
a2, b -> b -> b
forall m. GCDMonoid m => m -> m -> m
gcd b
b1 b
b2, c -> c -> c
forall m. GCDMonoid m => m -> m -> m
gcd c
c1 c
c2, d -> d -> d
forall m. GCDMonoid m => m -> m -> m
gcd d
d1 d
d2)
instance (LeftGCDMonoid a, LeftGCDMonoid b, LeftGCDMonoid c, LeftGCDMonoid d) => LeftGCDMonoid (a, b, c, d) where
commonPrefix :: (a, b, c, d) -> (a, b, c, d) -> (a, b, c, d)
commonPrefix (a1 :: a
a1, b1 :: b
b1, c1 :: c
c1, d1 :: d
d1) (a2 :: a
a2, b2 :: b
b2, c2 :: c
c2, d2 :: d
d2) =
(a -> a -> a
forall m. LeftGCDMonoid m => m -> m -> m
commonPrefix a
a1 a
a2, b -> b -> b
forall m. LeftGCDMonoid m => m -> m -> m
commonPrefix b
b1 b
b2, c -> c -> c
forall m. LeftGCDMonoid m => m -> m -> m
commonPrefix c
c1 c
c2, d -> d -> d
forall m. LeftGCDMonoid m => m -> m -> m
commonPrefix d
d1 d
d2)
instance (RightGCDMonoid a, RightGCDMonoid b, RightGCDMonoid c, RightGCDMonoid d) => RightGCDMonoid (a, b, c, d) where
commonSuffix :: (a, b, c, d) -> (a, b, c, d) -> (a, b, c, d)
commonSuffix (a1 :: a
a1, b1 :: b
b1, c1 :: c
c1, d1 :: d
d1) (a2 :: a
a2, b2 :: b
b2, c2 :: c
c2, d2 :: d
d2) =
(a -> a -> a
forall m. RightGCDMonoid m => m -> m -> m
commonSuffix a
a1 a
a2, b -> b -> b
forall m. RightGCDMonoid m => m -> m -> m
commonSuffix b
b1 b
b2, c -> c -> c
forall m. RightGCDMonoid m => m -> m -> m
commonSuffix c
c1 c
c2, d -> d -> d
forall m. RightGCDMonoid m => m -> m -> m
commonSuffix d
d1 d
d2)
instance LeftGCDMonoid x => LeftGCDMonoid (Maybe x) where
commonPrefix :: Maybe x -> Maybe x -> Maybe x
commonPrefix (Just x :: x
x) (Just y :: x
y) = x -> Maybe x
forall a. a -> Maybe a
Just (x -> x -> x
forall m. LeftGCDMonoid m => m -> m -> m
commonPrefix x
x x
y)
commonPrefix _ _ = Maybe x
forall a. Maybe a
Nothing
stripCommonPrefix :: Maybe x -> Maybe x -> (Maybe x, Maybe x, Maybe x)
stripCommonPrefix (Just x :: x
x) (Just y :: x
y) = (x -> Maybe x
forall a. a -> Maybe a
Just x
p, x -> Maybe x
forall a. a -> Maybe a
Just x
x', x -> Maybe x
forall a. a -> Maybe a
Just x
y')
where (p :: x
p, x' :: x
x', y' :: x
y') = x -> x -> (x, x, x)
forall m. LeftGCDMonoid m => m -> m -> (m, m, m)
stripCommonPrefix x
x x
y
stripCommonPrefix x :: Maybe x
x y :: Maybe x
y = (Maybe x
forall a. Maybe a
Nothing, Maybe x
x, Maybe x
y)
instance RightGCDMonoid x => RightGCDMonoid (Maybe x) where
commonSuffix :: Maybe x -> Maybe x -> Maybe x
commonSuffix (Just x :: x
x) (Just y :: x
y) = x -> Maybe x
forall a. a -> Maybe a
Just (x -> x -> x
forall m. RightGCDMonoid m => m -> m -> m
commonSuffix x
x x
y)
commonSuffix _ _ = Maybe x
forall a. Maybe a
Nothing
stripCommonSuffix :: Maybe x -> Maybe x -> (Maybe x, Maybe x, Maybe x)
stripCommonSuffix (Just x :: x
x) (Just y :: x
y) = (x -> Maybe x
forall a. a -> Maybe a
Just x
x', x -> Maybe x
forall a. a -> Maybe a
Just x
y', x -> Maybe x
forall a. a -> Maybe a
Just x
s)
where (x' :: x
x', y' :: x
y', s :: x
s) = x -> x -> (x, x, x)
forall m. RightGCDMonoid m => m -> m -> (m, m, m)
stripCommonSuffix x
x x
y
stripCommonSuffix x :: Maybe x
x y :: Maybe x
y = (Maybe x
x, Maybe x
y, Maybe x
forall a. Maybe a
Nothing)
instance Ord a => LeftGCDMonoid (Set.Set a) where
commonPrefix :: Set a -> Set a -> Set a
commonPrefix = Set a -> Set a -> Set a
forall a. Ord a => Set a -> Set a -> Set a
Set.intersection
instance Ord a => RightGCDMonoid (Set.Set a) where
commonSuffix :: Set a -> Set a -> Set a
commonSuffix = Set a -> Set a -> Set a
forall a. Ord a => Set a -> Set a -> Set a
Set.intersection
instance Ord a => GCDMonoid (Set.Set a) where
gcd :: Set a -> Set a -> Set a
gcd = Set a -> Set a -> Set a
forall a. Ord a => Set a -> Set a -> Set a
Set.intersection
instance LeftGCDMonoid IntSet.IntSet where
commonPrefix :: IntSet -> IntSet -> IntSet
commonPrefix = IntSet -> IntSet -> IntSet
IntSet.intersection
instance RightGCDMonoid IntSet.IntSet where
commonSuffix :: IntSet -> IntSet -> IntSet
commonSuffix = IntSet -> IntSet -> IntSet
IntSet.intersection
instance GCDMonoid IntSet.IntSet where
gcd :: IntSet -> IntSet -> IntSet
gcd = IntSet -> IntSet -> IntSet
IntSet.intersection
instance (Ord k, Eq a) => LeftGCDMonoid (Map.Map k a) where
commonPrefix :: Map k a -> Map k a -> Map k a
commonPrefix = (k -> a -> a -> Maybe a)
-> (Map k a -> Map k a)
-> (Map k a -> Map k a)
-> Map k a
-> Map k a
-> Map k a
forall k a b c.
Ord k =>
(k -> a -> b -> Maybe c)
-> (Map k a -> Map k c)
-> (Map k b -> Map k c)
-> Map k a
-> Map k b
-> Map k c
Map.mergeWithKey (\_ a :: a
a b :: a
b -> if a
a a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
b then a -> Maybe a
forall a. a -> Maybe a
Just a
a else Maybe a
forall a. Maybe a
Nothing) (Map k a -> Map k a -> Map k a
forall a b. a -> b -> a
const Map k a
forall k a. Map k a
Map.empty) (Map k a -> Map k a -> Map k a
forall a b. a -> b -> a
const Map k a
forall k a. Map k a
Map.empty)
instance Eq a => LeftGCDMonoid (IntMap.IntMap a) where
commonPrefix :: IntMap a -> IntMap a -> IntMap a
commonPrefix = (Key -> a -> a -> Maybe a)
-> (IntMap a -> IntMap a)
-> (IntMap a -> IntMap a)
-> IntMap a
-> IntMap a
-> IntMap a
forall a b c.
(Key -> a -> b -> Maybe c)
-> (IntMap a -> IntMap c)
-> (IntMap b -> IntMap c)
-> IntMap a
-> IntMap b
-> IntMap c
IntMap.mergeWithKey (\_ a :: a
a b :: a
b -> if a
a a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
b then a -> Maybe a
forall a. a -> Maybe a
Just a
a else Maybe a
forall a. Maybe a
Nothing)
(IntMap a -> IntMap a -> IntMap a
forall a b. a -> b -> a
const IntMap a
forall a. IntMap a
IntMap.empty) (IntMap a -> IntMap a -> IntMap a
forall a b. a -> b -> a
const IntMap a
forall a. IntMap a
IntMap.empty)
instance Eq x => LeftGCDMonoid [x] where
commonPrefix :: [x] -> [x] -> [x]
commonPrefix (x :: x
x:xs :: [x]
xs) (y :: x
y:ys :: [x]
ys) | x
x x -> x -> Bool
forall a. Eq a => a -> a -> Bool
== x
y = x
x x -> [x] -> [x]
forall a. a -> [a] -> [a]
: [x] -> [x] -> [x]
forall m. LeftGCDMonoid m => m -> m -> m
commonPrefix [x]
xs [x]
ys
commonPrefix _ _ = []
stripCommonPrefix :: [x] -> [x] -> ([x], [x], [x])
stripCommonPrefix x0 :: [x]
x0 y0 :: [x]
y0 = ([x] -> [x]) -> [x] -> [x] -> ([x], [x], [x])
forall a a. Eq a => ([a] -> a) -> [a] -> [a] -> (a, [a], [a])
strip' [x] -> [x]
forall a. a -> a
id [x]
x0 [x]
y0
where strip' :: ([a] -> a) -> [a] -> [a] -> (a, [a], [a])
strip' f :: [a] -> a
f (x :: a
x:xs :: [a]
xs) (y :: a
y:ys :: [a]
ys) | a
x a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
y = ([a] -> a) -> [a] -> [a] -> (a, [a], [a])
strip' ([a] -> a
f ([a] -> a) -> ([a] -> [a]) -> [a] -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
:)) [a]
xs [a]
ys
strip' f :: [a] -> a
f x :: [a]
x y :: [a]
y = ([a] -> a
f [], [a]
x, [a]
y)
instance Eq x => RightGCDMonoid [x] where
stripCommonSuffix :: [x] -> [x] -> ([x], [x], [x])
stripCommonSuffix x0 :: [x]
x0 y0 :: [x]
y0 = [x] -> [x] -> ([x], [x], [x])
forall a a. [a] -> [a] -> ([x], [x], [x])
go1 [x]
x0 [x]
y0
where go1 :: [a] -> [a] -> ([x], [x], [x])
go1 (_:xs :: [a]
xs) (_:ys :: [a]
ys) = [a] -> [a] -> ([x], [x], [x])
go1 [a]
xs [a]
ys
go1 [] [] = ([x] -> [x])
-> ([x] -> [x]) -> ([x] -> [x]) -> [x] -> [x] -> ([x], [x], [x])
forall a c c.
Eq a =>
([a] -> c)
-> ([a] -> c) -> ([a] -> [a]) -> [a] -> [a] -> (c, c, [a])
go2 [x] -> [x]
forall a. a -> a
id [x] -> [x]
forall a. a -> a
id [x] -> [x]
forall a. a -> a
id [x]
x0 [x]
y0
go1 [] ys :: [a]
ys = ([x] -> [x])
-> ([x] -> [x]) -> ([x] -> [x]) -> [x] -> [x] -> ([x], [x], [x])
forall a c c.
Eq a =>
([a] -> c)
-> ([a] -> c) -> ([a] -> [a]) -> [a] -> [a] -> (c, c, [a])
go2 [x] -> [x]
forall a. a -> a
id [x] -> [x]
yp [x] -> [x]
forall a. a -> a
id [x]
x0 [x]
yr
where (yp :: [x] -> [x]
yp, yr :: [x]
yr) = ([x] -> [x]) -> [a] -> [x] -> ([x] -> [x], [x])
forall a c a. ([a] -> c) -> [a] -> [a] -> ([a] -> c, [a])
splitAtLengthOf [x] -> [x]
forall a. a -> a
id [a]
ys [x]
y0
go1 xs :: [a]
xs [] = ([x] -> [x])
-> ([x] -> [x]) -> ([x] -> [x]) -> [x] -> [x] -> ([x], [x], [x])
forall a c c.
Eq a =>
([a] -> c)
-> ([a] -> c) -> ([a] -> [a]) -> [a] -> [a] -> (c, c, [a])
go2 [x] -> [x]
xp [x] -> [x]
forall a. a -> a
id [x] -> [x]
forall a. a -> a
id [x]
xr [x]
y0
where (xp :: [x] -> [x]
xp, xr :: [x]
xr) = ([x] -> [x]) -> [a] -> [x] -> ([x] -> [x], [x])
forall a c a. ([a] -> c) -> [a] -> [a] -> ([a] -> c, [a])
splitAtLengthOf [x] -> [x]
forall a. a -> a
id [a]
xs [x]
x0
go2 :: ([a] -> c)
-> ([a] -> c) -> ([a] -> [a]) -> [a] -> [a] -> (c, c, [a])
go2 xp :: [a] -> c
xp yp :: [a] -> c
yp cs :: [a] -> [a]
cs [] [] = ([a] -> c
xp [], [a] -> c
yp [], [a] -> [a]
cs [])
go2 xp :: [a] -> c
xp yp :: [a] -> c
yp cs :: [a] -> [a]
cs (x :: a
x:xs :: [a]
xs) (y :: a
y:ys :: [a]
ys)
| a
x a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
y = ([a] -> c)
-> ([a] -> c) -> ([a] -> [a]) -> [a] -> [a] -> (c, c, [a])
go2 [a] -> c
xp [a] -> c
yp ([a] -> [a]
cs ([a] -> [a]) -> ([a] -> [a]) -> [a] -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:)) [a]
xs [a]
ys
| Bool
otherwise = ([a] -> c)
-> ([a] -> c) -> ([a] -> [a]) -> [a] -> [a] -> (c, c, [a])
go2 ([a] -> c
xp ([a] -> c) -> ([a] -> [a]) -> [a] -> c
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [a] -> [a]
cs ([a] -> [a]) -> ([a] -> [a]) -> [a] -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:)) ([a] -> c
yp ([a] -> c) -> ([a] -> [a]) -> [a] -> c
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [a] -> [a]
cs ([a] -> [a]) -> ([a] -> [a]) -> [a] -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a
ya -> [a] -> [a]
forall a. a -> [a] -> [a]
:)) [a] -> [a]
forall a. a -> a
id [a]
xs [a]
ys
go2 _ _ _ _ _ = [Char] -> (c, c, [a])
forall a. HasCallStack => [Char] -> a
error "impossible"
splitAtLengthOf :: ([a] -> c) -> [a] -> [a] -> ([a] -> c, [a])
splitAtLengthOf yp :: [a] -> c
yp (_:xs :: [a]
xs) (y :: a
y:ys :: [a]
ys) = ([a] -> c) -> [a] -> [a] -> ([a] -> c, [a])
splitAtLengthOf ([a] -> c
yp ([a] -> c) -> ([a] -> [a]) -> [a] -> c
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a
ya -> [a] -> [a]
forall a. a -> [a] -> [a]
:)) [a]
xs [a]
ys
splitAtLengthOf yp :: [a] -> c
yp [] ys :: [a]
ys = ([a] -> c
yp, [a]
ys)
splitAtLengthOf _ _ _ = [Char] -> ([a] -> c, [a])
forall a. HasCallStack => [Char] -> a
error "impossible"
instance Eq a => LeftGCDMonoid (Sequence.Seq a) where
stripCommonPrefix :: Seq a -> Seq a -> (Seq a, Seq a, Seq a)
stripCommonPrefix = Seq a -> Seq a -> Seq a -> (Seq a, Seq a, Seq a)
forall a. Eq a => Seq a -> Seq a -> Seq a -> (Seq a, Seq a, Seq a)
findCommonPrefix Seq a
forall a. Seq a
Sequence.empty
where findCommonPrefix :: Seq a -> Seq a -> Seq a -> (Seq a, Seq a, Seq a)
findCommonPrefix prefix :: Seq a
prefix a :: Seq a
a b :: Seq a
b = case (Seq a -> ViewL a
forall a. Seq a -> ViewL a
Sequence.viewl Seq a
a, Seq a -> ViewL a
forall a. Seq a -> ViewL a
Sequence.viewl Seq a
b)
of (a1 :: a
a1:<a' :: Seq a
a', b1 :: a
b1:<b' :: Seq a
b') | a
a1 a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
b1 -> Seq a -> Seq a -> Seq a -> (Seq a, Seq a, Seq a)
findCommonPrefix (Seq a
prefix Seq a -> a -> Seq a
forall a. Seq a -> a -> Seq a
|> a
a1) Seq a
a' Seq a
b'
_ -> (Seq a
prefix, Seq a
a, Seq a
b)
instance Eq a => RightGCDMonoid (Sequence.Seq a) where
stripCommonSuffix :: Seq a -> Seq a -> (Seq a, Seq a, Seq a)
stripCommonSuffix = Seq a -> Seq a -> Seq a -> (Seq a, Seq a, Seq a)
forall a. Eq a => Seq a -> Seq a -> Seq a -> (Seq a, Seq a, Seq a)
findCommonSuffix Seq a
forall a. Seq a
Sequence.empty
where findCommonSuffix :: Seq a -> Seq a -> Seq a -> (Seq a, Seq a, Seq a)
findCommonSuffix suffix :: Seq a
suffix a :: Seq a
a b :: Seq a
b = case (Seq a -> ViewR a
forall a. Seq a -> ViewR a
Sequence.viewr Seq a
a, Seq a -> ViewR a
forall a. Seq a -> ViewR a
Sequence.viewr Seq a
b)
of (a' :: Seq a
a':>a1 :: a
a1, b' :: Seq a
b':>b1 :: a
b1) | a
a1 a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
b1 -> Seq a -> Seq a -> Seq a -> (Seq a, Seq a, Seq a)
findCommonSuffix (a
a1 a -> Seq a -> Seq a
forall a. a -> Seq a -> Seq a
<| Seq a
suffix) Seq a
a' Seq a
b'
_ -> (Seq a
a, Seq a
b, Seq a
suffix)
instance Eq a => LeftGCDMonoid (Vector.Vector a) where
stripCommonPrefix :: Vector a -> Vector a -> (Vector a, Vector a, Vector a)
stripCommonPrefix x :: Vector a
x y :: Vector a
y = (Vector a
xp, Vector a
xs, Key -> Vector a -> Vector a
forall a. Key -> Vector a -> Vector a
Vector.drop Key
maxPrefixLength Vector a
y)
where maxPrefixLength :: Key
maxPrefixLength = Key -> Key -> Key
prefixLength 0 (Vector a -> Key
forall a. Vector a -> Key
Vector.length Vector a
x Key -> Key -> Key
forall a. Ord a => a -> a -> a
`min` Vector a -> Key
forall a. Vector a -> Key
Vector.length Vector a
y)
prefixLength :: Key -> Key -> Key
prefixLength n :: Key
n len :: Key
len | Key
n Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
< Key
len Bool -> Bool -> Bool
&& Vector a
x Vector a -> Key -> a
forall a. Vector a -> Key -> a
Vector.! Key
n a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== Vector a
y Vector a -> Key -> a
forall a. Vector a -> Key -> a
Vector.! Key
n = Key -> Key -> Key
prefixLength (Key -> Key
forall a. Enum a => a -> a
succ Key
n) Key
len
prefixLength n :: Key
n _ = Key
n
(xp :: Vector a
xp, xs :: Vector a
xs) = Key -> Vector a -> (Vector a, Vector a)
forall a. Key -> Vector a -> (Vector a, Vector a)
Vector.splitAt Key
maxPrefixLength Vector a
x
instance Eq a => RightGCDMonoid (Vector.Vector a) where
stripCommonSuffix :: Vector a -> Vector a -> (Vector a, Vector a, Vector a)
stripCommonSuffix x :: Vector a
x y :: Vector a
y = Key -> Key -> (Vector a, Vector a, Vector a)
findSuffix (Vector a -> Key
forall a. Vector a -> Key
Vector.length Vector a
x Key -> Key -> Key
forall a. Num a => a -> a -> a
- 1) (Vector a -> Key
forall a. Vector a -> Key
Vector.length Vector a
y Key -> Key -> Key
forall a. Num a => a -> a -> a
- 1)
where findSuffix :: Key -> Key -> (Vector a, Vector a, Vector a)
findSuffix m :: Key
m n :: Key
n | Key
m Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
>= 0 Bool -> Bool -> Bool
&& Key
n Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
>= 0 Bool -> Bool -> Bool
&& Vector a
x Vector a -> Key -> a
forall a. Vector a -> Key -> a
Vector.! Key
m a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== Vector a
y Vector a -> Key -> a
forall a. Vector a -> Key -> a
Vector.! Key
n =
Key -> Key -> (Vector a, Vector a, Vector a)
findSuffix (Key -> Key
forall a. Enum a => a -> a
pred Key
m) (Key -> Key
forall a. Enum a => a -> a
pred Key
n)
findSuffix m :: Key
m n :: Key
n = (Key -> Vector a -> Vector a
forall a. Key -> Vector a -> Vector a
Vector.take (Key -> Key
forall a. Enum a => a -> a
succ Key
m) Vector a
x, Vector a
yp, Vector a
ys)
where (yp :: Vector a
yp, ys :: Vector a
ys) = Key -> Vector a -> (Vector a, Vector a)
forall a. Key -> Vector a -> (Vector a, Vector a)
Vector.splitAt (Key -> Key
forall a. Enum a => a -> a
succ Key
n) Vector a
y
instance LeftGCDMonoid ByteString.ByteString where
stripCommonPrefix :: ByteString -> ByteString -> (ByteString, ByteString, ByteString)
stripCommonPrefix x :: ByteString
x y :: ByteString
y = (ByteString
xp, ByteString
xs, Key -> ByteString -> ByteString
ByteString.unsafeDrop Key
maxPrefixLength ByteString
y)
where maxPrefixLength :: Key
maxPrefixLength = Key -> Key -> Key
prefixLength 0 (ByteString -> Key
ByteString.length ByteString
x Key -> Key -> Key
forall a. Ord a => a -> a -> a
`min` ByteString -> Key
ByteString.length ByteString
y)
prefixLength :: Key -> Key -> Key
prefixLength n :: Key
n len :: Key
len | Key
n Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
< Key
len,
ByteString -> Key -> Word8
ByteString.unsafeIndex ByteString
x Key
n Word8 -> Word8 -> Bool
forall a. Eq a => a -> a -> Bool
== ByteString -> Key -> Word8
ByteString.unsafeIndex ByteString
y Key
n =
Key -> Key -> Key
prefixLength (Key -> Key
forall a. Enum a => a -> a
succ Key
n) Key
len
| Bool
otherwise = Key
n
(xp :: ByteString
xp, xs :: ByteString
xs) = Key -> ByteString -> (ByteString, ByteString)
ByteString.splitAt Key
maxPrefixLength ByteString
x
instance RightGCDMonoid ByteString.ByteString where
stripCommonSuffix :: ByteString -> ByteString -> (ByteString, ByteString, ByteString)
stripCommonSuffix x :: ByteString
x y :: ByteString
y = Key -> Key -> (ByteString, ByteString, ByteString)
findSuffix (ByteString -> Key
ByteString.length ByteString
x Key -> Key -> Key
forall a. Num a => a -> a -> a
- 1) (ByteString -> Key
ByteString.length ByteString
y Key -> Key -> Key
forall a. Num a => a -> a -> a
- 1)
where findSuffix :: Key -> Key -> (ByteString, ByteString, ByteString)
findSuffix m :: Key
m n :: Key
n | Key
m Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
>= 0, Key
n Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
>= 0,
ByteString -> Key -> Word8
ByteString.unsafeIndex ByteString
x Key
m Word8 -> Word8 -> Bool
forall a. Eq a => a -> a -> Bool
== ByteString -> Key -> Word8
ByteString.unsafeIndex ByteString
y Key
n =
Key -> Key -> (ByteString, ByteString, ByteString)
findSuffix (Key -> Key
forall a. Enum a => a -> a
pred Key
m) (Key -> Key
forall a. Enum a => a -> a
pred Key
n)
| Bool
otherwise = let (yp :: ByteString
yp, ys :: ByteString
ys) = Key -> ByteString -> (ByteString, ByteString)
ByteString.splitAt (Key -> Key
forall a. Enum a => a -> a
succ Key
n) ByteString
y
in (Key -> ByteString -> ByteString
ByteString.unsafeTake (Key -> Key
forall a. Enum a => a -> a
succ Key
m) ByteString
x, ByteString
yp, ByteString
ys)
instance LeftGCDMonoid LazyByteString.ByteString where
stripCommonPrefix :: ByteString -> ByteString -> (ByteString, ByteString, ByteString)
stripCommonPrefix x :: ByteString
x y :: ByteString
y = (ByteString
xp, ByteString
xs, Int64 -> ByteString -> ByteString
LazyByteString.drop Int64
maxPrefixLength ByteString
y)
where maxPrefixLength :: Int64
maxPrefixLength = Int64 -> Int64 -> Int64
prefixLength 0 (ByteString -> Int64
LazyByteString.length ByteString
x Int64 -> Int64 -> Int64
forall a. Ord a => a -> a -> a
`min` ByteString -> Int64
LazyByteString.length ByteString
y)
prefixLength :: Int64 -> Int64 -> Int64
prefixLength n :: Int64
n len :: Int64
len | Int64
n Int64 -> Int64 -> Bool
forall a. Ord a => a -> a -> Bool
< Int64
len Bool -> Bool -> Bool
&& ByteString -> Int64 -> Word8
LazyByteString.index ByteString
x Int64
n Word8 -> Word8 -> Bool
forall a. Eq a => a -> a -> Bool
== ByteString -> Int64 -> Word8
LazyByteString.index ByteString
y Int64
n =
Int64 -> Int64 -> Int64
prefixLength (Int64 -> Int64
forall a. Enum a => a -> a
succ Int64
n) Int64
len
prefixLength n :: Int64
n _ = Int64
n
(xp :: ByteString
xp, xs :: ByteString
xs) = Int64 -> ByteString -> (ByteString, ByteString)
LazyByteString.splitAt Int64
maxPrefixLength ByteString
x
instance RightGCDMonoid LazyByteString.ByteString where
stripCommonSuffix :: ByteString -> ByteString -> (ByteString, ByteString, ByteString)
stripCommonSuffix x :: ByteString
x y :: ByteString
y = Int64 -> Int64 -> (ByteString, ByteString, ByteString)
findSuffix (ByteString -> Int64
LazyByteString.length ByteString
x Int64 -> Int64 -> Int64
forall a. Num a => a -> a -> a
- 1) (ByteString -> Int64
LazyByteString.length ByteString
y Int64 -> Int64 -> Int64
forall a. Num a => a -> a -> a
- 1)
where findSuffix :: Int64 -> Int64 -> (ByteString, ByteString, ByteString)
findSuffix m :: Int64
m n :: Int64
n | Int64
m Int64 -> Int64 -> Bool
forall a. Ord a => a -> a -> Bool
>= 0 Bool -> Bool -> Bool
&& Int64
n Int64 -> Int64 -> Bool
forall a. Ord a => a -> a -> Bool
>= 0 Bool -> Bool -> Bool
&& ByteString -> Int64 -> Word8
LazyByteString.index ByteString
x Int64
m Word8 -> Word8 -> Bool
forall a. Eq a => a -> a -> Bool
== ByteString -> Int64 -> Word8
LazyByteString.index ByteString
y Int64
n =
Int64 -> Int64 -> (ByteString, ByteString, ByteString)
findSuffix (Int64 -> Int64
forall a. Enum a => a -> a
pred Int64
m) (Int64 -> Int64
forall a. Enum a => a -> a
pred Int64
n)
findSuffix m :: Int64
m n :: Int64
n = (Int64 -> ByteString -> ByteString
LazyByteString.take (Int64 -> Int64
forall a. Enum a => a -> a
succ Int64
m) ByteString
x, ByteString
yp, ByteString
ys)
where (yp :: ByteString
yp, ys :: ByteString
ys) = Int64 -> ByteString -> (ByteString, ByteString)
LazyByteString.splitAt (Int64 -> Int64
forall a. Enum a => a -> a
succ Int64
n) ByteString
y
instance LeftGCDMonoid Text.Text where
stripCommonPrefix :: Text -> Text -> (Text, Text, Text)
stripCommonPrefix x :: Text
x y :: Text
y = (Text, Text, Text)
-> ((Text, Text, Text) -> (Text, Text, Text))
-> Maybe (Text, Text, Text)
-> (Text, Text, Text)
forall b a. b -> (a -> b) -> Maybe a -> b
maybe (Text
Text.empty, Text
x, Text
y) (Text, Text, Text) -> (Text, Text, Text)
forall a. a -> a
id (Text -> Text -> Maybe (Text, Text, Text)
Text.commonPrefixes Text
x Text
y)
instance RightGCDMonoid Text.Text where
stripCommonSuffix :: Text -> Text -> (Text, Text, Text)
stripCommonSuffix x :: Text
x@(Internal.Text xarr :: Array
xarr xoff :: Key
xoff xlen :: Key
xlen) y :: Text
y@(Internal.Text yarr :: Array
yarr yoff :: Key
yoff ylen :: Key
ylen) = Key -> Key -> (Text, Text, Text)
go (Key -> Key
forall a. Enum a => a -> a
pred Key
xlen) (Key -> Key
forall a. Enum a => a -> a
pred Key
ylen)
where go :: Key -> Key -> (Text, Text, Text)
go i :: Key
i j :: Key
j | Key
i Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
>= 0 Bool -> Bool -> Bool
&& Key
j Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
>= 0 Bool -> Bool -> Bool
&& Char
xc Char -> Char -> Bool
forall a. Eq a => a -> a -> Bool
== Char
yc = Key -> Key -> (Text, Text, Text)
go (Key
iKey -> Key -> Key
forall a. Num a => a -> a -> a
+Key
xd) (Key
jKey -> Key -> Key
forall a. Num a => a -> a -> a
+Key
yd)
| Bool
otherwise = (Array -> Key -> Key -> Text
Internal.text Array
xarr Key
xoff (Key -> Key
forall a. Enum a => a -> a
succ Key
i),
Array -> Key -> Key -> Text
Internal.text Array
yarr Key
yoff (Key -> Key
forall a. Enum a => a -> a
succ Key
j),
Array -> Key -> Key -> Text
Internal.text Array
xarr (Key
xoffKey -> Key -> Key
forall a. Num a => a -> a -> a
+Key
iKey -> Key -> Key
forall a. Num a => a -> a -> a
+1) (Key
xlenKey -> Key -> Key
forall a. Num a => a -> a -> a
-Key
iKey -> Key -> Key
forall a. Num a => a -> a -> a
-1))
where (xc :: Char
xc, xd :: Key
xd) = Text -> Key -> (Char, Key)
reverseIter Text
x Key
i
(yc :: Char
yc, yd :: Key
yd) = Text -> Key -> (Char, Key)
reverseIter Text
y Key
j
instance LeftGCDMonoid LazyText.Text where
stripCommonPrefix :: Text -> Text -> (Text, Text, Text)
stripCommonPrefix x :: Text
x y :: Text
y = (Text, Text, Text)
-> ((Text, Text, Text) -> (Text, Text, Text))
-> Maybe (Text, Text, Text)
-> (Text, Text, Text)
forall b a. b -> (a -> b) -> Maybe a -> b
maybe (Text
LazyText.empty, Text
x, Text
y) (Text, Text, Text) -> (Text, Text, Text)
forall a. a -> a
id (Text -> Text -> Maybe (Text, Text, Text)
LazyText.commonPrefixes Text
x Text
y)
instance RightGCDMonoid LazyText.Text where
stripCommonSuffix :: Text -> Text -> (Text, Text, Text)
stripCommonSuffix x0 :: Text
x0 y0 :: Text
y0
| Key
x0len Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
< Key
y0len = (Text -> Text)
-> (Text -> Text)
-> (Text -> Text)
-> Text
-> Text
-> (Text, Text, Text)
forall c c.
(Text -> c)
-> (Text -> c) -> (Text -> Text) -> Text -> Text -> (c, c, Text)
go Text -> Text
forall a. a -> a
id Text -> Text
y0p Text -> Text
forall a. a -> a
id Text
x0 Text
y0s
| Key
x0len Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
> Key
y0len = (Text -> Text)
-> (Text -> Text)
-> (Text -> Text)
-> Text
-> Text
-> (Text, Text, Text)
forall c c.
(Text -> c)
-> (Text -> c) -> (Text -> Text) -> Text -> Text -> (c, c, Text)
go Text -> Text
x0p Text -> Text
forall a. a -> a
id Text -> Text
forall a. a -> a
id Text
x0s Text
y0
| Bool
otherwise = (Text -> Text)
-> (Text -> Text)
-> (Text -> Text)
-> Text
-> Text
-> (Text, Text, Text)
forall c c.
(Text -> c)
-> (Text -> c) -> (Text -> Text) -> Text -> Text -> (c, c, Text)
go Text -> Text
forall a. a -> a
id Text -> Text
forall a. a -> a
id Text -> Text
forall a. a -> a
id Text
x0 Text
y0
where (y0p :: Text -> Text
y0p, y0s :: Text
y0s) = (Text -> Text) -> Key -> Text -> (Text -> Text, Text)
forall c. (Text -> c) -> Key -> Text -> (Text -> c, Text)
splitWord16 Text -> Text
forall a. a -> a
id (Key
y0len Key -> Key -> Key
forall a. Num a => a -> a -> a
- Key
x0len) Text
y0
(x0p :: Text -> Text
x0p, x0s :: Text
x0s) = (Text -> Text) -> Key -> Text -> (Text -> Text, Text)
forall c. (Text -> c) -> Key -> Text -> (Text -> c, Text)
splitWord16 Text -> Text
forall a. a -> a
id (Key
x0len Key -> Key -> Key
forall a. Num a => a -> a -> a
- Key
y0len) Text
x0
x0len :: Key
x0len = Text -> Key
lazyLengthWord16 Text
x0
y0len :: Key
y0len = Text -> Key
lazyLengthWord16 Text
y0
lazyLengthWord16 :: Text -> Key
lazyLengthWord16 = (Key -> Text -> Key) -> Key -> Text -> Key
forall a. (a -> Text -> a) -> a -> Text -> a
LazyText.foldlChunks Key -> Text -> Key
addLength 0
addLength :: Key -> Text -> Key
addLength n :: Key
n x :: Text
x = Key
n Key -> Key -> Key
forall a. Num a => a -> a -> a
+ Text -> Key
lengthWord16 Text
x
splitWord16 :: (Text -> c) -> Key -> Text -> (Text -> c, Text)
splitWord16 xp :: Text -> c
xp 0 x :: Text
x = (Text -> c
xp, Text
x)
splitWord16 xp :: Text -> c
xp n :: Key
n (LazyInternal.Chunk x :: Text
x@(Internal.Text arr :: Array
arr off :: Key
off len :: Key
len) xs :: Text
xs)
| Key
n Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
< Key
len = (Text -> c
xp (Text -> c) -> (Text -> Text) -> Text -> c
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Text -> Text -> Text
LazyInternal.chunk (Array -> Key -> Key -> Text
Internal.Text Array
arr Key
off Key
n),
Text -> Text -> Text
LazyInternal.chunk (Array -> Key -> Key -> Text
Internal.Text Array
arr (Key
offKey -> Key -> Key
forall a. Num a => a -> a -> a
+Key
n) (Key
lenKey -> Key -> Key
forall a. Num a => a -> a -> a
-Key
n)) Text
xs)
| Bool
otherwise = (Text -> c) -> Key -> Text -> (Text -> c, Text)
splitWord16 (Text -> c
xp (Text -> c) -> (Text -> Text) -> Text -> c
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Text -> Text -> Text
LazyInternal.chunk Text
x) (Key
n Key -> Key -> Key
forall a. Num a => a -> a -> a
- Key
len) Text
xs
splitWord16 _ _ LazyInternal.Empty = [Char] -> (Text -> c, Text)
forall a. HasCallStack => [Char] -> a
error "impossible"
go :: (Text -> c)
-> (Text -> c) -> (Text -> Text) -> Text -> Text -> (c, c, Text)
go xp :: Text -> c
xp yp :: Text -> c
yp cs :: Text -> Text
cs LazyInternal.Empty LazyInternal.Empty = (Text -> c
xp Text
forall a. Monoid a => a
mempty, Text -> c
yp Text
forall a. Monoid a => a
mempty, Text -> Text
cs Text
forall a. Monoid a => a
mempty)
go xp :: Text -> c
xp yp :: Text -> c
yp cs :: Text -> Text
cs (LazyInternal.Chunk x :: Text
x@(Internal.Text xarr :: Array
xarr xoff :: Key
xoff xlen :: Key
xlen) xs :: Text
xs)
(LazyInternal.Chunk y :: Text
y@(Internal.Text yarr :: Array
yarr yoff :: Key
yoff ylen :: Key
ylen) ys :: Text
ys)
| Key
xlen Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
< Key
ylen = (Text -> c)
-> (Text -> c) -> (Text -> Text) -> Text -> Text -> (c, c, Text)
go Text -> c
xp Text -> c
yp Text -> Text
cs (Text -> Text -> Text
LazyInternal.Chunk Text
x Text
xs)
(Text -> Text -> Text
LazyInternal.Chunk (Array -> Key -> Key -> Text
Internal.Text Array
yarr Key
yoff Key
xlen) (Text -> Text) -> Text -> Text
forall a b. (a -> b) -> a -> b
$
Text -> Text -> Text
LazyInternal.Chunk (Array -> Key -> Key -> Text
Internal.Text Array
yarr (Key
yoffKey -> Key -> Key
forall a. Num a => a -> a -> a
+Key
xlen) (Key
ylenKey -> Key -> Key
forall a. Num a => a -> a -> a
-Key
xlen)) Text
ys)
| Key
xlen Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
> Key
ylen = (Text -> c)
-> (Text -> c) -> (Text -> Text) -> Text -> Text -> (c, c, Text)
go Text -> c
xp Text -> c
yp Text -> Text
cs (Text -> Text -> Text
LazyInternal.Chunk (Array -> Key -> Key -> Text
Internal.Text Array
xarr Key
xoff Key
ylen) (Text -> Text) -> Text -> Text
forall a b. (a -> b) -> a -> b
$
Text -> Text -> Text
LazyInternal.Chunk (Array -> Key -> Key -> Text
Internal.Text Array
xarr (Key
xoffKey -> Key -> Key
forall a. Num a => a -> a -> a
+Key
ylen) (Key
xlenKey -> Key -> Key
forall a. Num a => a -> a -> a
-Key
ylen)) Text
xs)
(Text -> Text -> Text
LazyInternal.Chunk Text
y Text
ys)
| Text
x Text -> Text -> Bool
forall a. Eq a => a -> a -> Bool
== Text
y = (Text -> c)
-> (Text -> c) -> (Text -> Text) -> Text -> Text -> (c, c, Text)
go Text -> c
xp Text -> c
yp (Text -> Text
cs (Text -> Text) -> (Text -> Text) -> Text -> Text
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Text -> Text -> Text
LazyInternal.chunk Text
x) Text
xs Text
ys
| (x1p :: Text
x1p, y1p :: Text
y1p, c1s :: Text
c1s) <- Text -> Text -> (Text, Text, Text)
forall m. RightGCDMonoid m => m -> m -> (m, m, m)
stripCommonSuffix Text
x Text
y =
(Text -> c)
-> (Text -> c) -> (Text -> Text) -> Text -> Text -> (c, c, Text)
go (Text -> c
xp (Text -> c) -> (Text -> Text) -> Text -> c
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Text -> Text
cs (Text -> Text) -> (Text -> Text) -> Text -> Text
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Text -> Text -> Text
LazyInternal.chunk Text
x1p) (Text -> c
yp (Text -> c) -> (Text -> Text) -> Text -> c
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Text -> Text
cs (Text -> Text) -> (Text -> Text) -> Text -> Text
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Text -> Text -> Text
LazyInternal.chunk Text
y1p) (Text -> Text -> Text
LazyInternal.chunk Text
c1s) Text
xs Text
ys
go _ _ _ _ _ = [Char] -> (c, c, Text)
forall a. HasCallStack => [Char] -> a
error "impossible"