{-# LANGUAGE CPP, Haskell2010, FlexibleInstances, Trustworthy #-}
module Data.Monoid.GCD
( GCDMonoid (..)
, LeftGCDMonoid (..)
, RightGCDMonoid (..)
, OverlappingGCDMonoid (..)
, DistributiveGCDMonoid
, LeftDistributiveGCDMonoid
, RightDistributiveGCDMonoid
)
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.Encoding as TextEncoding
import qualified Data.Text.Internal as Internal
import qualified Data.Text.Internal.Lazy as LazyInternal
import Data.Text.Unsafe (reverseIter)
#if MIN_VERSION_text(2,0,0)
import Data.Text.Unsafe (Iter(..))
#endif
import qualified Data.Text.Lazy as LazyText
import qualified Data.Text.Lazy.Encoding as LazyEncoding
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 Data.Maybe (isJust)
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 m
x m
y = m
p
where (m
p, m
_, m
_) = m -> m -> (m, m, m)
forall m. LeftGCDMonoid m => m -> m -> (m, m, m)
stripCommonPrefix m
x m
y
stripCommonPrefix m
x 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 m
x' = m -> m -> Maybe m
forall m. LeftReductive m => m -> m -> Maybe m
stripPrefix m
p m
x
Just 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 m
x m
y = m
s
where (m
_, m
_, m
s) = m -> m -> (m, m, m)
forall m. RightGCDMonoid m => m -> m -> (m, m, m)
stripCommonSuffix m
x m
y
stripCommonSuffix m
x 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 m
x' = m -> m -> Maybe m
forall m. RightReductive m => m -> m -> Maybe m
stripSuffix m
s m
x
Just 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) (Dual 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) (Dual 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) (Dual 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 Natural
a) (Sum 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 Sum Natural
a 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 Sum Natural
a 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 Natural
a) (Product 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 Product Natural
a 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 Product Natural
a 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, b
b) (a
c, 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, b
b) (a
c, 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, b
b) (a
c, 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 (a
a1, b
b1, c
c1) (a
a2, b
b2, 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 (a
a1, b
b1, c
c1) (a
a2, b
b2, 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 (a
a1, b
b1, c
c1) (a
a2, b
b2, 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 (a
a1, b
b1, c
c1, d
d1) (a
a2, b
b2, c
c2, 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 (a
a1, b
b1, c
c1, d
d1) (a
a2, b
b2, c
c2, 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 (a
a1, b
b1, c
c1, d
d1) (a
a2, b
b2, c
c2, 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) (Just 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
_ Maybe x
_ = Maybe x
forall a. Maybe a
Nothing
stripCommonPrefix :: Maybe x -> Maybe x -> (Maybe x, Maybe x, Maybe x)
stripCommonPrefix (Just x
x) (Just 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 (x
p, x
x', x
y') = x -> x -> (x, x, x)
forall m. LeftGCDMonoid m => m -> m -> (m, m, m)
stripCommonPrefix x
x x
y
stripCommonPrefix Maybe x
x 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) (Just 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
_ Maybe x
_ = Maybe x
forall a. Maybe a
Nothing
stripCommonSuffix :: Maybe x -> Maybe x -> (Maybe x, Maybe x, Maybe x)
stripCommonSuffix (Just x
x) (Just 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
s) = x -> x -> (x, x, x)
forall m. RightGCDMonoid m => m -> m -> (m, m, m)
stripCommonSuffix x
x x
y
stripCommonSuffix Maybe x
x 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 (\k
_ a
a 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 (\Key
_ a
a 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
y:[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 [x]
_ [x]
_ = []
stripCommonPrefix :: [x] -> [x] -> ([x], [x], [x])
stripCommonPrefix [x]
x0 [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' [a] -> a
f (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] -> (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' [a] -> a
f [a]
x [a]
y = ([a] -> a
f [], [a]
x, [a]
y)
instance Eq x => RightGCDMonoid [x] where
stripCommonSuffix :: [x] -> [x] -> ([x], [x], [x])
stripCommonSuffix [x]
x0 [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 (a
_:[a]
xs) (a
_:[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} {a} {b}.
Eq a =>
([a] -> a)
-> ([a] -> b) -> ([a] -> [a]) -> [a] -> [a] -> (a, b, [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 [] [a]
ys = ([x] -> [x])
-> ([x] -> [x]) -> ([x] -> [x]) -> [x] -> [x] -> ([x], [x], [x])
forall {a} {a} {b}.
Eq a =>
([a] -> a)
-> ([a] -> b) -> ([a] -> [a]) -> [a] -> [a] -> (a, b, [a])
go2 [x] -> [x]
forall a. a -> a
id [x] -> [x]
yp [x] -> [x]
forall a. a -> a
id [x]
x0 [x]
yr
where ([x] -> [x]
yp, [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 [a]
xs [] = ([x] -> [x])
-> ([x] -> [x]) -> ([x] -> [x]) -> [x] -> [x] -> ([x], [x], [x])
forall {a} {a} {b}.
Eq a =>
([a] -> a)
-> ([a] -> b) -> ([a] -> [a]) -> [a] -> [a] -> (a, b, [a])
go2 [x] -> [x]
xp [x] -> [x]
forall a. a -> a
id [x] -> [x]
forall a. a -> a
id [x]
xr [x]
y0
where ([x] -> [x]
xp, [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] -> a)
-> ([a] -> b) -> ([a] -> [a]) -> [a] -> [a] -> (a, b, [a])
go2 [a] -> a
xp [a] -> b
yp [a] -> [a]
cs [] [] = ([a] -> a
xp [], [a] -> b
yp [], [a] -> [a]
cs [])
go2 [a] -> a
xp [a] -> b
yp [a] -> [a]
cs (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] -> b) -> ([a] -> [a]) -> [a] -> [a] -> (a, b, [a])
go2 [a] -> a
xp [a] -> b
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] -> a)
-> ([a] -> b) -> ([a] -> [a]) -> [a] -> [a] -> (a, b, [a])
go2 ([a] -> a
xp ([a] -> a) -> ([a] -> [a]) -> [a] -> a
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] -> b
yp ([a] -> b) -> ([a] -> [a]) -> [a] -> b
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 [a] -> a
_ [a] -> b
_ [a] -> [a]
_ [a]
_ [a]
_ = [Char] -> (a, b, [a])
forall a. HasCallStack => [Char] -> a
error [Char]
"impossible"
splitAtLengthOf :: ([a] -> c) -> [a] -> [a] -> ([a] -> c, [a])
splitAtLengthOf [a] -> c
yp (a
_:[a]
xs) (a
y:[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 [a] -> c
yp [] [a]
ys = ([a] -> c
yp, [a]
ys)
splitAtLengthOf [a] -> c
_ [a]
_ [a]
_ = [Char] -> ([a] -> c, [a])
forall a. HasCallStack => [Char] -> a
error [Char]
"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 Seq a
prefix Seq a
a 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 (a
a1:<Seq a
a', a
b1:<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'
(ViewL a, ViewL a)
_ -> (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 Seq a
suffix Seq a
a 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 (Seq a
a':>a
a1, Seq a
b':>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'
(ViewR a, ViewR a)
_ -> (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 Vector a
x 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 Key
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 Key
n 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 Key
n Key
_ = Key
n
(Vector a
xp, 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 Vector a
x 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
- Key
1) (Vector a -> Key
forall a. Vector a -> Key
Vector.length Vector a
y Key -> Key -> Key
forall a. Num a => a -> a -> a
- Key
1)
where findSuffix :: Key -> Key -> (Vector a, Vector a, Vector a)
findSuffix Key
m Key
n | Key
m Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
>= Key
0 Bool -> Bool -> Bool
&& Key
n Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
>= Key
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 Key
m 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 (Vector a
yp, 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 ByteString
x ByteString
y = (ByteString
xp, ByteString
xs, Key -> ByteString -> ByteString
ByteString.unsafeDrop Key
maxPrefixLength ByteString
y)
where maxPrefixLength :: Key
maxPrefixLength = Key -> Key -> Key
prefixLength Key
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 Key
n 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
(ByteString
xp, ByteString
xs) = Key -> ByteString -> (ByteString, ByteString)
ByteString.splitAt Key
maxPrefixLength ByteString
x
instance RightGCDMonoid ByteString.ByteString where
stripCommonSuffix :: ByteString -> ByteString -> (ByteString, ByteString, ByteString)
stripCommonSuffix ByteString
x ByteString
y = Key -> Key -> (ByteString, ByteString, ByteString)
findSuffix (ByteString -> Key
ByteString.length ByteString
x Key -> Key -> Key
forall a. Num a => a -> a -> a
- Key
1) (ByteString -> Key
ByteString.length ByteString
y Key -> Key -> Key
forall a. Num a => a -> a -> a
- Key
1)
where findSuffix :: Key -> Key -> (ByteString, ByteString, ByteString)
findSuffix Key
m Key
n | Key
m Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
>= Key
0, Key
n Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
>= Key
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 (ByteString
yp, 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 ByteString
x ByteString
y = (ByteString
xp, ByteString
xs, Int64 -> ByteString -> ByteString
LazyByteString.drop Int64
maxPrefixLength ByteString
y)
where maxPrefixLength :: Int64
maxPrefixLength = Int64 -> Int64 -> Int64
prefixLength Int64
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 Int64
n Int64
len | Int64
n Int64 -> Int64 -> Bool
forall a. Ord a => a -> a -> Bool
< Int64
len Bool -> Bool -> Bool
&& HasCallStack => ByteString -> Int64 -> Word8
ByteString -> Int64 -> Word8
LazyByteString.index ByteString
x Int64
n Word8 -> Word8 -> Bool
forall a. Eq a => a -> a -> Bool
== HasCallStack => ByteString -> Int64 -> Word8
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 Int64
n Int64
_ = Int64
n
(ByteString
xp, ByteString
xs) = Int64 -> ByteString -> (ByteString, ByteString)
LazyByteString.splitAt Int64
maxPrefixLength ByteString
x
instance RightGCDMonoid LazyByteString.ByteString where
stripCommonSuffix :: ByteString -> ByteString -> (ByteString, ByteString, ByteString)
stripCommonSuffix ByteString
x ByteString
y = Int64 -> Int64 -> (ByteString, ByteString, ByteString)
findSuffix (ByteString -> Int64
LazyByteString.length ByteString
x Int64 -> Int64 -> Int64
forall a. Num a => a -> a -> a
- Int64
1) (ByteString -> Int64
LazyByteString.length ByteString
y Int64 -> Int64 -> Int64
forall a. Num a => a -> a -> a
- Int64
1)
where findSuffix :: Int64 -> Int64 -> (ByteString, ByteString, ByteString)
findSuffix Int64
m Int64
n | Int64
m Int64 -> Int64 -> Bool
forall a. Ord a => a -> a -> Bool
>= Int64
0 Bool -> Bool -> Bool
&& Int64
n Int64 -> Int64 -> Bool
forall a. Ord a => a -> a -> Bool
>= Int64
0 Bool -> Bool -> Bool
&& HasCallStack => ByteString -> Int64 -> Word8
ByteString -> Int64 -> Word8
LazyByteString.index ByteString
x Int64
m Word8 -> Word8 -> Bool
forall a. Eq a => a -> a -> Bool
== HasCallStack => ByteString -> Int64 -> Word8
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 Int64
m 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 (ByteString
yp, 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 Text
x 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
#if !ghcjs_HOST_OS
stripCommonSuffix :: Text -> Text -> (Text, Text, Text)
stripCommonSuffix x :: Text
x@(Internal.Text Array
xarr Key
xoff Key
xlen) y :: Text
y@(Internal.Text Array
yarr Key
yoff 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 Key
i Key
j | Key
i Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
>= Key
0 Bool -> Bool -> Bool
&& Key
j Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
>= Key
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
+Key
1) (Key
xlenKey -> Key -> Key
forall a. Num a => a -> a -> a
-Key
iKey -> Key -> Key
forall a. Num a => a -> a -> a
-Key
1))
#if MIN_VERSION_text(2,0,0)
where Iter Char
xc Key
xd = Text -> Key -> Iter
reverseIter Text
x Key
i
Iter Char
yc Key
yd = Text -> Key -> Iter
reverseIter Text
y Key
j
#else
where (xc, xd) = reverseIter x i
(yc, yd) = reverseIter y j
#endif
#else
stripCommonSuffix x y =
let (xlist, ylist, slist) =
stripCommonSuffix (TextEncoding.encodeUtf8 x) (TextEncoding.encodeUtf8 y)
in (TextEncoding.decodeUtf8 xlist, TextEncoding.decodeUtf8 ylist, TextEncoding.decodeUtf8 slist)
#endif
instance LeftGCDMonoid LazyText.Text where
stripCommonPrefix :: Text -> Text -> (Text, Text, Text)
stripCommonPrefix Text
x 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
#if !ghcjs_HOST_OS
stripCommonSuffix :: Text -> Text -> (Text, Text, Text)
stripCommonSuffix Text
x0 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 {a} {b}.
(Text -> a)
-> (Text -> b) -> (Text -> Text) -> Text -> Text -> (a, b, 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 {a} {b}.
(Text -> a)
-> (Text -> b) -> (Text -> Text) -> Text -> Text -> (a, b, 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 {a} {b}.
(Text -> a)
-> (Text -> b) -> (Text -> Text) -> Text -> Text -> (a, b, 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 (Text -> Text
y0p, 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
(Text -> Text
x0p, 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 Key
0
addLength :: Key -> Text -> Key
addLength Key
n Text
x = Key
n Key -> Key -> Key
forall a. Num a => a -> a -> a
+ (\(Internal.Text Array
_ Key
_ Key
l) -> Key
l) Text
x
splitWord16 :: (Text -> c) -> Key -> Text -> (Text -> c, Text)
splitWord16 Text -> c
xp Key
0 Text
x = (Text -> c
xp, Text
x)
splitWord16 Text -> c
xp Key
n (LazyInternal.Chunk x :: Text
x@(Internal.Text Array
arr Key
off Key
len) 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 Text -> c
_ Key
_ Text
LazyInternal.Empty = [Char] -> (Text -> c, Text)
forall a. HasCallStack => [Char] -> a
error [Char]
"impossible"
go :: (Text -> a)
-> (Text -> b) -> (Text -> Text) -> Text -> Text -> (a, b, Text)
go Text -> a
xp Text -> b
yp Text -> Text
cs Text
LazyInternal.Empty Text
LazyInternal.Empty = (Text -> a
xp Text
forall a. Monoid a => a
mempty, Text -> b
yp Text
forall a. Monoid a => a
mempty, Text -> Text
cs Text
forall a. Monoid a => a
mempty)
go Text -> a
xp Text -> b
yp Text -> Text
cs (LazyInternal.Chunk x :: Text
x@(Internal.Text Array
xarr Key
xoff Key
xlen) Text
xs)
(LazyInternal.Chunk y :: Text
y@(Internal.Text Array
yarr Key
yoff Key
ylen) Text
ys)
| Key
xlen Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
< Key
ylen = (Text -> a)
-> (Text -> b) -> (Text -> Text) -> Text -> Text -> (a, b, Text)
go Text -> a
xp Text -> b
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 -> a)
-> (Text -> b) -> (Text -> Text) -> Text -> Text -> (a, b, Text)
go Text -> a
xp Text -> b
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 -> a)
-> (Text -> b) -> (Text -> Text) -> Text -> Text -> (a, b, Text)
go Text -> a
xp Text -> b
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
| (Text
x1p, Text
y1p, Text
c1s) <- Text -> Text -> (Text, Text, Text)
forall m. RightGCDMonoid m => m -> m -> (m, m, m)
stripCommonSuffix Text
x Text
y =
(Text -> a)
-> (Text -> b) -> (Text -> Text) -> Text -> Text -> (a, b, Text)
go (Text -> a
xp (Text -> a) -> (Text -> Text) -> Text -> a
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 -> b
yp (Text -> b) -> (Text -> Text) -> Text -> b
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 Text -> a
_ Text -> b
_ Text -> Text
_ Text
_ Text
_ = [Char] -> (a, b, Text)
forall a. HasCallStack => [Char] -> a
error [Char]
"impossible"
#else
stripCommonSuffix x y =
let (xlist, ylist, slist) =
stripCommonSuffix (LazyEncoding.encodeUtf8 x) (LazyEncoding.encodeUtf8 y)
in (LazyEncoding.decodeUtf8 xlist, LazyEncoding.decodeUtf8 ylist, LazyEncoding.decodeUtf8 slist)
#endif
class (LeftDistributiveGCDMonoid m, RightDistributiveGCDMonoid m, GCDMonoid m)
=> DistributiveGCDMonoid m
instance DistributiveGCDMonoid ()
instance DistributiveGCDMonoid (Product Natural)
instance DistributiveGCDMonoid (Sum Natural)
instance DistributiveGCDMonoid IntSet.IntSet
instance DistributiveGCDMonoid a => DistributiveGCDMonoid (Dual a)
instance Ord a => DistributiveGCDMonoid (Set.Set a)
class LeftGCDMonoid m => LeftDistributiveGCDMonoid m
instance Eq a => LeftDistributiveGCDMonoid [a]
instance Eq a => LeftDistributiveGCDMonoid (Sequence.Seq a)
instance Eq a => LeftDistributiveGCDMonoid (Vector.Vector a)
instance LeftDistributiveGCDMonoid ByteString.ByteString
instance LeftDistributiveGCDMonoid LazyByteString.ByteString
instance LeftDistributiveGCDMonoid Text.Text
instance LeftDistributiveGCDMonoid LazyText.Text
instance LeftDistributiveGCDMonoid ()
instance LeftDistributiveGCDMonoid (Product Natural)
instance LeftDistributiveGCDMonoid (Sum Natural)
instance LeftDistributiveGCDMonoid IntSet.IntSet
instance Ord a => LeftDistributiveGCDMonoid (Set.Set a)
instance RightDistributiveGCDMonoid a => LeftDistributiveGCDMonoid (Dual a)
class RightGCDMonoid m => RightDistributiveGCDMonoid m
instance Eq a => RightDistributiveGCDMonoid [a]
instance Eq a => RightDistributiveGCDMonoid (Sequence.Seq a)
instance Eq a => RightDistributiveGCDMonoid (Vector.Vector a)
instance RightDistributiveGCDMonoid ByteString.ByteString
instance RightDistributiveGCDMonoid LazyByteString.ByteString
instance RightDistributiveGCDMonoid Text.Text
instance RightDistributiveGCDMonoid LazyText.Text
instance RightDistributiveGCDMonoid ()
instance RightDistributiveGCDMonoid (Product Natural)
instance RightDistributiveGCDMonoid (Sum Natural)
instance RightDistributiveGCDMonoid IntSet.IntSet
instance Ord a => RightDistributiveGCDMonoid (Set.Set a)
instance LeftDistributiveGCDMonoid a => RightDistributiveGCDMonoid (Dual a)