    -----------------------------------------------------------------------------
    -- |
    -- Module      :  Data.Algorithm.Diff
    -- Copyright   :  (c) Sterling Clover 2008-2011, Kevin Charter 2011
    -- License     :  BSD 3 Clause
    -- Maintainer  :  s.clover@gmail.com
    -- Stability   :  experimental
    -- Portability :  portable
    --
    -- This is an implementation of the diff algorithm as described in
    -- /An \( O(ND) \) Difference Algorithm and Its Variations (1986)/
    -- <http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.4.6927>.
    -- For inputs of size \( O(N) \) with the number of differences \( D \)
    -- it has \( O(ND) \) time and \( O(D^2) \) space complexity.
    -----------------------------------------------------------------------------

    module Data.Algorithm.Diff
        ( Diff, PolyDiff(..)
        -- * Comparing lists for differences
        , getDiff
        , getDiffBy

        -- * Finding chunks of differences
        , getGroupedDiff
        , getGroupedDiffBy
        ) where

    import Prelude hiding (pi)
    import Data.Array (listArray, (!))
    import Data.Bifunctor

    data DI = F | S deriving (Int -> DI -> ShowS
    [DI] -> ShowS
    DI -> String
    (Int -> DI -> ShowS)
    -> (DI -> String) -> ([DI] -> ShowS) -> Show DI
    forall a.
    (Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
    $cshowsPrec :: Int -> DI -> ShowS
    showsPrec :: Int -> DI -> ShowS
    $cshow :: DI -> String
    show :: DI -> String
    $cshowList :: [DI] -> ShowS
    showList :: [DI] -> ShowS
    Show, DI -> DI -> Bool
    (DI -> DI -> Bool) -> (DI -> DI -> Bool) -> Eq DI
    forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
    $c== :: DI -> DI -> Bool
    == :: DI -> DI -> Bool
    $c/= :: DI -> DI -> Bool
    /= :: DI -> DI -> Bool
    Eq)

    -- | A value is either from the 'First' list, the 'Second' or from 'Both'.
    -- 'Both' contains both the left and right values, in case you are using a form
    -- of equality that doesn't check all data (for example, if you are using a
    -- newtype to only perform equality on side of a tuple).
    data PolyDiff a b = First a | Second b | Both a b
        deriving (Int -> PolyDiff a b -> ShowS
    [PolyDiff a b] -> ShowS
    PolyDiff a b -> String
    (Int -> PolyDiff a b -> ShowS)
    -> (PolyDiff a b -> String)
    -> ([PolyDiff a b] -> ShowS)
    -> Show (PolyDiff a b)
    forall a.
    (Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
    forall a b. (Show a, Show b) => Int -> PolyDiff a b -> ShowS
    forall a b. (Show a, Show b) => [PolyDiff a b] -> ShowS
    forall a b. (Show a, Show b) => PolyDiff a b -> String
    $cshowsPrec :: forall a b. (Show a, Show b) => Int -> PolyDiff a b -> ShowS
    showsPrec :: Int -> PolyDiff a b -> ShowS
    $cshow :: forall a b. (Show a, Show b) => PolyDiff a b -> String
    show :: PolyDiff a b -> String
    $cshowList :: forall a b. (Show a, Show b) => [PolyDiff a b] -> ShowS
    showList :: [PolyDiff a b] -> ShowS
    Show, PolyDiff a b -> PolyDiff a b -> Bool
    (PolyDiff a b -> PolyDiff a b -> Bool)
    -> (PolyDiff a b -> PolyDiff a b -> Bool) -> Eq (PolyDiff a b)
    forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
    forall a b. (Eq a, Eq b) => PolyDiff a b -> PolyDiff a b -> Bool
    $c== :: forall a b. (Eq a, Eq b) => PolyDiff a b -> PolyDiff a b -> Bool
    == :: PolyDiff a b -> PolyDiff a b -> Bool
    $c/= :: forall a b. (Eq a, Eq b) => PolyDiff a b -> PolyDiff a b -> Bool
    /= :: PolyDiff a b -> PolyDiff a b -> Bool
    Eq)

    instance Functor (PolyDiff a) where
      fmap :: forall a b. (a -> b) -> PolyDiff a a -> PolyDiff a b
    fmap a -> b
    _ (First a
    a) = a -> PolyDiff a b
    forall a b. a -> PolyDiff a b
    First a
    a
      fmap a -> b
    g (Second a
    b) = b -> PolyDiff a b
    forall a b. b -> PolyDiff a b
    Second (a -> b
    g a
    b)
      fmap a -> b
    g (Both a
    a a
    b) = a -> b -> PolyDiff a b
    forall a b. a -> b -> PolyDiff a b
    Both a
    a (a -> b
    g a
    b)

    instance Bifunctor PolyDiff where
      bimap :: forall a b c d.
    (a -> b) -> (c -> d) -> PolyDiff a c -> PolyDiff b d
    bimap a -> b
    f c -> d
    _ (First a
    a) = b -> PolyDiff b d
    forall a b. a -> PolyDiff a b
    First (a -> b
    f a
    a)
      bimap a -> b
    _ c -> d
    g (Second c
    b) = d -> PolyDiff b d
    forall a b. b -> PolyDiff a b
    Second (c -> d
    g c
    b)
      bimap a -> b
    f c -> d
    g (Both a
    a c
    b) = b -> d -> PolyDiff b d
    forall a b. a -> b -> PolyDiff a b
    Both (a -> b
    f a
    a) (c -> d
    g c
    b)

    -- | This is 'PolyDiff' specialized so both sides are the same type.
    type Diff a = PolyDiff a a

    data DL = DL {DL -> Int
    poi :: !Int, DL -> Int
    poj :: !Int, DL -> [DI]
    path::[DI]} deriving (Int -> DL -> ShowS
    [DL] -> ShowS
    DL -> String
    (Int -> DL -> ShowS)
    -> (DL -> String) -> ([DL] -> ShowS) -> Show DL
    forall a.
    (Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
    $cshowsPrec :: Int -> DL -> ShowS
    showsPrec :: Int -> DL -> ShowS
    $cshow :: DL -> String
    show :: DL -> String
    $cshowList :: [DL] -> ShowS
    showList :: [DL] -> ShowS
    Show, DL -> DL -> Bool
    (DL -> DL -> Bool) -> (DL -> DL -> Bool) -> Eq DL
    forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
    $c== :: DL -> DL -> Bool
    == :: DL -> DL -> Bool
    $c/= :: DL -> DL -> Bool
    /= :: DL -> DL -> Bool
    Eq)

    instance Ord DL
            where DL
    x <= :: DL -> DL -> Bool
    <= DL
    y = if DL -> Int
    poi DL
    x Int -> Int -> Bool
    forall a. Eq a => a -> a -> Bool
    == DL -> Int
    poi DL
    y
                    then  DL -> Int
    poj DL
    x Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    > DL -> Int
    poj DL
    y
                    else DL -> Int
    poi DL
    x Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    <= DL -> Int
    poi DL
    y

    canDiag :: (a -> b -> Bool) -> [a] -> [b] -> Int -> Int -> Int -> Int -> Bool
    canDiag :: forall a b.
    (a -> b -> Bool) -> [a] -> [b] -> Int -> Int -> Int -> Int -> Bool
    canDiag a -> b -> Bool
    eq [a]
    as [b]
    bs Int
    lena Int
    lenb = \ Int
    i Int
    j ->
       if Int
    i Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    < Int
    lena Bool -> Bool -> Bool
    && Int
    j Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    < Int
    lenb then (Array Int a
    arAs Array Int a -> Int -> a
    forall i e. Ix i => Array i e -> i -> e
    ! Int
    i) a -> b -> Bool
    `eq` (Array Int b
    arBs Array Int b -> Int -> b
    forall i e. Ix i => Array i e -> i -> e
    ! Int
    j) else Bool
    False
        where arAs :: Array Int a
    arAs = (Int, Int) -> [a] -> Array Int a
    forall i e. Ix i => (i, i) -> [e] -> Array i e
    listArray (Int
    0,Int
    lena Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - Int
    1) [a]
    as
              arBs :: Array Int b
    arBs = (Int, Int) -> [b] -> Array Int b
    forall i e. Ix i => (i, i) -> [e] -> Array i e
    listArray (Int
    0,Int
    lenb Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - Int
    1) [b]
    bs

    dstep :: (Int -> Int -> Bool) -> [DL] -> [DL]
    dstep :: (Int -> Int -> Bool) -> [DL] -> [DL]
    dstep Int -> Int -> Bool
    cd [DL]
    dls = DL
    hdDL -> [DL] -> [DL]
    forall a. a -> [a] -> [a]
    :[DL] -> [DL]
    forall {a}. Ord a => [a] -> [a]
    pairMaxes [DL]
    rst
      where (DL
    hd:[DL]
    rst) = [DL] -> [DL]
    nextDLs [DL]
    dls
            nextDLs :: [DL] -> [DL]
    nextDLs [] = []
            nextDLs (DL
    dl:[DL]
    rest) = DL
    dl'DL -> [DL] -> [DL]
    forall a. a -> [a] -> [a]
    :DL
    dl''DL -> [DL] -> [DL]
    forall a. a -> [a] -> [a]
    :[DL] -> [DL]
    nextDLs [DL]
    rest
              where dl' :: DL
    dl'  = (Int -> Int -> Bool) -> DL -> DL
    addsnake Int -> Int -> Bool
    cd (DL -> DL) -> DL -> DL
    forall a b. (a -> b) -> a -> b
    $ DL
    dl {poi=poi dl + 1, path=(F : pdl)}
                    dl'' :: DL
    dl'' = (Int -> Int -> Bool) -> DL -> DL
    addsnake Int -> Int -> Bool
    cd (DL -> DL) -> DL -> DL
    forall a b. (a -> b) -> a -> b
    $ DL
    dl {poj=poj dl + 1, path=(S : pdl)}
                    pdl :: [DI]
    pdl = DL -> [DI]
    path DL
    dl
            pairMaxes :: [a] -> [a]
    pairMaxes [] = []
            pairMaxes [a
    x] = [a
    x]
            pairMaxes (a
    x:a
    y:[a]
    rest) = a -> a -> a
    forall a. Ord a => a -> a -> a
    max a
    x a
    ya -> [a] -> [a]
    forall a. a -> [a] -> [a]
    :[a] -> [a]
    pairMaxes [a]
    rest

    addsnake :: (Int -> Int -> Bool) -> DL -> DL
    addsnake :: (Int -> Int -> Bool) -> DL -> DL
    addsnake Int -> Int -> Bool
    cd DL
    dl
        | Int -> Int -> Bool
    cd Int
    pi Int
    pj = (Int -> Int -> Bool) -> DL -> DL
    addsnake Int -> Int -> Bool
    cd (DL -> DL) -> DL -> DL
    forall a b. (a -> b) -> a -> b
    $
                     DL
    dl {poi = pi + 1, poj = pj + 1, path = path dl}
        | Bool
    otherwise   = DL
    dl
        where pi :: Int
    pi = DL -> Int
    poi DL
    dl; pj :: Int
    pj = DL -> Int
    poj DL
    dl

    lcs :: (a -> b -> Bool) -> [a] -> [b] -> [DI]
    lcs :: forall a b. (a -> b -> Bool) -> [a] -> [b] -> [DI]
    lcs a -> b -> Bool
    eq [a]
    as [b]
    bs = DL -> [DI]
    path (DL -> [DI]) -> (DL -> DL) -> DL -> [DI]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . [DL] -> DL
    forall a. HasCallStack => [a] -> a
    head ([DL] -> DL) -> (DL -> [DL]) -> DL -> DL
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (DL -> Bool) -> [DL] -> [DL]
    forall a. (a -> Bool) -> [a] -> [a]
    dropWhile (\DL
    dl -> DL -> Int
    poi DL
    dl Int -> Int -> Bool
    forall a. Eq a => a -> a -> Bool
    /= Int
    lena Bool -> Bool -> Bool
    || DL -> Int
    poj DL
    dl Int -> Int -> Bool
    forall a. Eq a => a -> a -> Bool
    /= Int
    lenb) ([DL] -> [DL]) -> (DL -> [DL]) -> DL -> [DL]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    .
                [[DL]] -> [DL]
    forall (t :: * -> *) a. Foldable t => t [a] -> [a]
    concat ([[DL]] -> [DL]) -> (DL -> [[DL]]) -> DL -> [DL]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . ([DL] -> [DL]) -> [DL] -> [[DL]]
    forall a. (a -> a) -> a -> [a]
    iterate ((Int -> Int -> Bool) -> [DL] -> [DL]
    dstep Int -> Int -> Bool
    cd) ([DL] -> [[DL]]) -> (DL -> [DL]) -> DL -> [[DL]]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (DL -> [DL] -> [DL]
    forall a. a -> [a] -> [a]
    :[]) (DL -> [DL]) -> (DL -> DL) -> DL -> [DL]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (Int -> Int -> Bool) -> DL -> DL
    addsnake Int -> Int -> Bool
    cd (DL -> [DI]) -> DL -> [DI]
    forall a b. (a -> b) -> a -> b
    $
                DL {poi :: Int
    poi=Int
    0,poj :: Int
    poj=Int
    0,path :: [DI]
    path=[]}
                where cd :: Int -> Int -> Bool
    cd = (a -> b -> Bool) -> [a] -> [b] -> Int -> Int -> Int -> Int -> Bool
    forall a b.
    (a -> b -> Bool) -> [a] -> [b] -> Int -> Int -> Int -> Int -> Bool
    canDiag a -> b -> Bool
    eq [a]
    as [b]
    bs Int
    lena Int
    lenb
                      lena :: Int
    lena = [a] -> Int
    forall a. [a] -> Int
    forall (t :: * -> *) a. Foldable t => t a -> Int
    length [a]
    as; lenb :: Int
    lenb = [b] -> Int
    forall a. [a] -> Int
    forall (t :: * -> *) a. Foldable t => t a -> Int
    length [b]
    bs

    -- | Takes two lists and returns a list of differences between them. This is
    -- 'getDiffBy' with '==' used as predicate.
    --
    -- > > getDiff ["a","b","c","d","e"] ["a","c","d","f"]
    -- > [Both "a" "a",First "b",Both "c" "c",Both "d" "d",First "e",Second "f"]
    -- > > getDiff "abcde" "acdf"
    -- > [Both 'a' 'a',First 'b',Both 'c' 'c',Both 'd' 'd',First 'e',Second 'f']
    getDiff :: (Eq a) => [a] -> [a] -> [Diff a]
    getDiff :: forall a. Eq a => [a] -> [a] -> [Diff a]
    getDiff = (a -> a -> Bool) -> [a] -> [a] -> [PolyDiff a a]
    forall a b. (a -> b -> Bool) -> [a] -> [b] -> [PolyDiff a b]
    getDiffBy a -> a -> Bool
    forall a. Eq a => a -> a -> Bool
    (==)

    -- | Takes two lists and returns a list of differences between them, grouped
    -- into chunks. This is 'getGroupedDiffBy' with '==' used as predicate.
    --
    -- > > getGroupedDiff "abcde" "acdf"
    -- > [Both "a" "a",First "b",Both "cd" "cd",First "e",Second "f"]
    getGroupedDiff :: (Eq a) => [a] -> [a] -> [Diff [a]]
    getGroupedDiff :: forall a. Eq a => [a] -> [a] -> [Diff [a]]
    getGroupedDiff = (a -> a -> Bool) -> [a] -> [a] -> [PolyDiff [a] [a]]
    forall a b. (a -> b -> Bool) -> [a] -> [b] -> [PolyDiff [a] [b]]
    getGroupedDiffBy a -> a -> Bool
    forall a. Eq a => a -> a -> Bool
    (==)

    -- | A form of 'getDiff' with no 'Eq' constraint. Instead, an equality predicate
    -- is taken as the first argument.
    getDiffBy :: (a -> b -> Bool) -> [a] -> [b] -> [PolyDiff a b]
    getDiffBy :: forall a b. (a -> b -> Bool) -> [a] -> [b] -> [PolyDiff a b]
    getDiffBy a -> b -> Bool
    eq [a]
    a [b]
    b = [a] -> [b] -> [DI] -> [PolyDiff a b]
    markup [a]
    a [b]
    b ([DI] -> [PolyDiff a b])
    -> ([DI] -> [DI]) -> [DI] -> [PolyDiff a b]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . [DI] -> [DI]
    forall a. [a] -> [a]
    reverse ([DI] -> [PolyDiff a b]) -> [DI] -> [PolyDiff a b]
    forall a b. (a -> b) -> a -> b
    $ (a -> b -> Bool) -> [a] -> [b] -> [DI]
    forall a b. (a -> b -> Bool) -> [a] -> [b] -> [DI]
    lcs a -> b -> Bool
    eq [a]
    a [b]
    b
        where markup :: [a] -> [b] -> [DI] -> [PolyDiff a b]
    markup (a
    x:[a]
    xs) (b
    y:[b]
    ys) [DI]
    ds
                | a -> b -> Bool
    eq a
    x b
    y = a -> b -> PolyDiff a b
    forall a b. a -> b -> PolyDiff a b
    Both a
    x b
    y PolyDiff a b -> [PolyDiff a b] -> [PolyDiff a b]
    forall a. a -> [a] -> [a]
    : [a] -> [b] -> [DI] -> [PolyDiff a b]
    markup [a]
    xs [b]
    ys [DI]
    ds
              markup (a
    x:[a]
    xs)   [b]
    ys   (DI
    F:[DI]
    ds) = a -> PolyDiff a b
    forall a b. a -> PolyDiff a b
    First a
    x  PolyDiff a b -> [PolyDiff a b] -> [PolyDiff a b]
    forall a. a -> [a] -> [a]
    : [a] -> [b] -> [DI] -> [PolyDiff a b]
    markup [a]
    xs [b]
    ys [DI]
    ds
              markup   [a]
    xs   (b
    y:[b]
    ys) (DI
    S:[DI]
    ds) = b -> PolyDiff a b
    forall a b. b -> PolyDiff a b
    Second b
    y PolyDiff a b -> [PolyDiff a b] -> [PolyDiff a b]
    forall a. a -> [a] -> [a]
    : [a] -> [b] -> [DI] -> [PolyDiff a b]
    markup [a]
    xs [b]
    ys [DI]
    ds
              markup [a]
    _ [b]
    _ [DI]
    _ = []

    getGroupedDiffBy :: (a -> b -> Bool) -> [a] -> [b] -> [PolyDiff [a] [b]]
    getGroupedDiffBy :: forall a b. (a -> b -> Bool) -> [a] -> [b] -> [PolyDiff [a] [b]]
    getGroupedDiffBy a -> b -> Bool
    eq [a]
    a [b]
    b = [PolyDiff a b] -> [PolyDiff [a] [b]]
    forall {a} {a}. [PolyDiff a a] -> [PolyDiff [a] [a]]
    go ([PolyDiff a b] -> [PolyDiff [a] [b]])
    -> [PolyDiff a b] -> [PolyDiff [a] [b]]
    forall a b. (a -> b) -> a -> b
    $ (a -> b -> Bool) -> [a] -> [b] -> [PolyDiff a b]
    forall a b. (a -> b -> Bool) -> [a] -> [b] -> [PolyDiff a b]
    getDiffBy a -> b -> Bool
    eq [a]
    a [b]
    b
        where go :: [PolyDiff a a] -> [PolyDiff [a] [a]]
    go (First a
    x  : [PolyDiff a a]
    xs) = let ([a]
    fs, [PolyDiff a a]
    rest) = [PolyDiff a a] -> ([a], [PolyDiff a a])
    forall {a} {b}. [PolyDiff a b] -> ([a], [PolyDiff a b])
    goFirsts  [PolyDiff a a]
    xs in [a] -> PolyDiff [a] [a]
    forall a b. a -> PolyDiff a b
    First  (a
    xa -> [a] -> [a]
    forall a. a -> [a] -> [a]
    :[a]
    fs)     PolyDiff [a] [a] -> [PolyDiff [a] [a]] -> [PolyDiff [a] [a]]
    forall a. a -> [a] -> [a]
    : [PolyDiff a a] -> [PolyDiff [a] [a]]
    go [PolyDiff a a]
    rest
              go (Second a
    x : [PolyDiff a a]
    xs) = let ([a]
    fs, [PolyDiff a a]
    rest) = [PolyDiff a a] -> ([a], [PolyDiff a a])
    forall {a} {a}. [PolyDiff a a] -> ([a], [PolyDiff a a])
    goSeconds [PolyDiff a a]
    xs in [a] -> PolyDiff [a] [a]
    forall a b. b -> PolyDiff a b
    Second (a
    xa -> [a] -> [a]
    forall a. a -> [a] -> [a]
    :[a]
    fs)     PolyDiff [a] [a] -> [PolyDiff [a] [a]] -> [PolyDiff [a] [a]]
    forall a. a -> [a] -> [a]
    : [PolyDiff a a] -> [PolyDiff [a] [a]]
    go [PolyDiff a a]
    rest
              go (Both a
    x a
    y : [PolyDiff a a]
    xs) = let ([(a, a)]
    fs, [PolyDiff a a]
    rest) = [PolyDiff a a] -> ([(a, a)], [PolyDiff a a])
    forall {a} {b}. [PolyDiff a b] -> ([(a, b)], [PolyDiff a b])
    goBoth    [PolyDiff a a]
    xs
                                       ([a]
    fxs, [a]
    fys) = [(a, a)] -> ([a], [a])
    forall a b. [(a, b)] -> ([a], [b])
    unzip [(a, a)]
    fs
                                   in [a] -> [a] -> PolyDiff [a] [a]
    forall a b. a -> b -> PolyDiff a b
    Both (a
    xa -> [a] -> [a]
    forall a. a -> [a] -> [a]
    :[a]
    fxs) (a
    ya -> [a] -> [a]
    forall a. a -> [a] -> [a]
    :[a]
    fys) PolyDiff [a] [a] -> [PolyDiff [a] [a]] -> [PolyDiff [a] [a]]
    forall a. a -> [a] -> [a]
    : [PolyDiff a a] -> [PolyDiff [a] [a]]
    go [PolyDiff a a]
    rest
              go [] = []

              goFirsts :: [PolyDiff a b] -> ([a], [PolyDiff a b])
    goFirsts  (First a
    x  : [PolyDiff a b]
    xs) = let ([a]
    fs, [PolyDiff a b]
    rest) = [PolyDiff a b] -> ([a], [PolyDiff a b])
    goFirsts  [PolyDiff a b]
    xs in (a
    xa -> [a] -> [a]
    forall a. a -> [a] -> [a]
    :[a]
    fs, [PolyDiff a b]
    rest)
              goFirsts  [PolyDiff a b]
    xs = ([],[PolyDiff a b]
    xs)

              goSeconds :: [PolyDiff a a] -> ([a], [PolyDiff a a])
    goSeconds (Second a
    x : [PolyDiff a a]
    xs) = let ([a]
    fs, [PolyDiff a a]
    rest) = [PolyDiff a a] -> ([a], [PolyDiff a a])
    goSeconds [PolyDiff a a]
    xs in (a
    xa -> [a] -> [a]
    forall a. a -> [a] -> [a]
    :[a]
    fs, [PolyDiff a a]
    rest)
              goSeconds [PolyDiff a a]
    xs = ([],[PolyDiff a a]
    xs)

              goBoth :: [PolyDiff a b] -> ([(a, b)], [PolyDiff a b])
    goBoth    (Both a
    x b
    y : [PolyDiff a b]
    xs) = let ([(a, b)]
    fs, [PolyDiff a b]
    rest) = [PolyDiff a b] -> ([(a, b)], [PolyDiff a b])
    goBoth [PolyDiff a b]
    xs    in ((a
    x,b
    y)(a, b) -> [(a, b)] -> [(a, b)]
    forall a. a -> [a] -> [a]
    :[(a, b)]
    fs, [PolyDiff a b]
    rest)
              goBoth    [PolyDiff a b]
    xs = ([],[PolyDiff a b]
    xs)