complement :: Signature -> Term -> Term -> Term
complement sig p1 p2 = p1 \\ p2
  where
    appl f ps | any isBottom ps = Bottom
              | otherwise = Appl f ps

    plus Bottom u = u
    plus t Bottom = t
    plus t u = Plus t u

    sum = foldr plus Bottom

    alias x Bottom = Bottom
    alias x t = Alias x t

    u \\ (Var _) = Bottom
    u \\ Bottom = u
    (Var x) \\ p@(Appl g ps) = alias x (sum [pattern f \\ p | f <- fs])
      where fs = ctorsOfSameRange sig g
            pattern f = Appl f (replicate (arity sig f) (Var "_"))
    Bottom \\ Appl _ _ = Bottom
    Appl f ps \\ Appl g qs
        | f /= g || someUnchanged = appl f ps
        | otherwise = sum [appl f ps' | ps' <- interleave ps pqs]
      where pqs = zipWith (\\) ps qs
            someUnchanged = or (zipWith (==) ps pqs)
    Plus q1 q2 \\ p@(Appl _ _) = plus (q1 \\ p) (q2 \\ p)
    Alias x p1 \\ p2 = alias x (p1 \\ p2)
    p1 \\ Alias x p2 = p1 \\ p2
    p \\ (Plus p1 p2) = (p \\ p1) \\ p2
complement :: Signature -> Term -> Term -> Term
complement sig p1 p2 = p1 \\ p2
  where
    appl f ps | any isBottom ps = Bottom
              | otherwise = Appl f ps

    plus Bottom u = u
    plus t Bottom = t
    plus t u = Plus t u

    sum = foldr plus Bottom

    alias x Bottom = Bottom
    alias x t = Alias x t

    u \\ (Var _) = Bottom
    u \\ Bottom = u
    (Var x) \\ p@(Appl g ps) = alias x (sum [pattern f \\ p | f <- fs])
      where fs = ctorsOfSameRange sig g
            pattern f = Appl f (replicate (arity sig f) (Var "_"))
    Bottom \\ Appl _ _ = Bottom
    Appl f ps \\ Appl g qs
        | f /= g || someUnchanged = appl f ps
        | otherwise = sum [appl f ps' | ps' <- interleave ps pqs]
      where pqs = zipWith (\\) ps qs
            someUnchanged = or (zipWith (==) ps pqs)
    Plus q1 q2 \\ p@(Appl _ _) = plus (q1 \\ p) (q2 \\ p)
    Alias x p1 \\ p2 = alias x (p1 \\ p2)
    p1 \\ Alias x p2 = p1 \\ p2
    p \\ (Plus p1 p2) = (p \\ p1) \\ p2
complement sig p1 p2 = p1 \\ p2
  where
    appl f ps | any isBottom ps = Bottom
              | otherwise = Appl f ps

    plus Bottom u = u
    plus t Bottom = t
    plus t u = Plus t u

    sum = foldr plus Bottom

    alias x Bottom = Bottom
    alias x t = Alias x t

    u \\ (Var _) = Bottom
    u \\ Bottom = u
    (Var x) \\ p@(Appl g ps) = alias x (sum [pattern f \\ p | f <- fs])
      where fs = ctorsOfSameRange sig g
            pattern f = Appl f (replicate (arity sig f) (Var "_"))
    Bottom \\ Appl _ _ = Bottom
    Appl f ps \\ Appl g qs
        | f /= g || someUnchanged = appl f ps
        | otherwise = sum [appl f ps' | ps' <- interleave ps pqs]
      where pqs = zipWith (\\) ps qs
            someUnchanged = or (zipWith (==) ps pqs)
    Plus q1 q2 \\ p@(Appl _ _) = plus (q1 \\ p) (q2 \\ p)
    Alias x p1 \\ p2 = alias x (p1 \\ p2)
    p1 \\ Alias x p2 = p1 \\ p2
    p \\ (Plus p1 p2) = (p \\ p1) \\ p2