    -- |
    -- Module      :  Cryptol.TypeCheck.TypeMap
    -- Copyright   :  (c) 2013-2016 Galois, Inc.
    -- License     :  BSD3
    -- Maintainer  :  cryptol@galois.com
    -- Stability   :  provisional
    -- Portability :  portable

    {-# LANGUAGE Safe #-}
    {-# LANGUAGE MultiParamTypeClasses, FunctionalDependencies #-}
    {-# LANGUAGE UndecidableInstances, FlexibleInstances #-}
    {-# LANGUAGE DeriveFunctor #-}
    {-# LANGUAGE DeriveFoldable #-}
    {-# LANGUAGE DeriveTraversable #-}
    module Cryptol.TypeCheck.TypeMap
      ( TypeMap(..), TypesMap, TrieMap(..)
      , insertTM, insertWithTM
      , membersTM
      , mapTM, mapWithKeyTM, mapMaybeTM

      , List(..)
      ) where

    import           Cryptol.TypeCheck.AST
    import           Cryptol.Utils.Ident
    import           Cryptol.Utils.RecordMap

    import qualified Data.Map as Map
    import           Data.Map (Map)
    import           Data.Maybe(fromMaybe,maybeToList)
    import           Control.Monad((<=<))
    import           Data.Maybe (isNothing)

    class TrieMap m k | m -> k where
      emptyTM  :: m a
      nullTM   :: m a -> Bool
      lookupTM :: k -> m a -> Maybe a
      alterTM  :: k -> (Maybe a -> Maybe a) -> m a -> m a
      unionTM  :: (a -> a -> a) -> m a -> m a -> m a
      toListTM :: m a -> [(k,a)]

      mapMaybeWithKeyTM :: (k -> a -> Maybe b) -> m a -> m b

    membersTM :: TrieMap m k => m a -> [a]
    membersTM :: forall (m :: * -> *) k a. TrieMap m k => m a -> [a]
    membersTM  = ((k, a) -> a) -> [(k, a)] -> [a]
    forall a b. (a -> b) -> [a] -> [b]
    map (k, a) -> a
    forall a b. (a, b) -> b
    snd ([(k, a)] -> [a]) -> (m a -> [(k, a)]) -> m a -> [a]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . m a -> [(k, a)]
    forall a. m a -> [(k, a)]
    forall (m :: * -> *) k a. TrieMap m k => m a -> [(k, a)]
    toListTM

    insertTM :: TrieMap m k => k -> a -> m a -> m a
    insertTM :: forall (m :: * -> *) k a. TrieMap m k => k -> a -> m a -> m a
    insertTM k
    t a
    a = k -> (Maybe a -> Maybe a) -> m a -> m a
    forall a. k -> (Maybe a -> Maybe a) -> m a -> m a
    forall (m :: * -> *) k a.
    TrieMap m k =>
    k -> (Maybe a -> Maybe a) -> m a -> m a
    alterTM k
    t (\Maybe a
    _ -> a -> Maybe a
    forall a. a -> Maybe a
    Just a
    a)

    insertWithTM :: TrieMap m k => (a -> a -> a) -> k -> a -> m a -> m a
    insertWithTM :: forall (m :: * -> *) k a.
    TrieMap m k =>
    (a -> a -> a) -> k -> a -> m a -> m a
    insertWithTM a -> a -> a
    f k
    t a
    new = k -> (Maybe a -> Maybe a) -> m a -> m a
    forall a. k -> (Maybe a -> Maybe a) -> m a -> m a
    forall (m :: * -> *) k a.
    TrieMap m k =>
    k -> (Maybe a -> Maybe a) -> m a -> m a
    alterTM k
    t ((Maybe a -> Maybe a) -> m a -> m a)
    -> (Maybe a -> Maybe a) -> m a -> m a
    forall a b. (a -> b) -> a -> b
    $ \Maybe a
    mb -> a -> Maybe a
    forall a. a -> Maybe a
    Just (a -> Maybe a) -> a -> Maybe a
    forall a b. (a -> b) -> a -> b
    $ case Maybe a
    mb of
                                                       Maybe a
    Nothing  -> a
    new
                                                       Just a
    old -> a -> a -> a
    f a
    old a
    new

    {-# INLINE mapTM #-}
    mapTM :: TrieMap m k => (a -> b) -> m a -> m b
    mapTM :: forall (m :: * -> *) k a b. TrieMap m k => (a -> b) -> m a -> m b
    mapTM a -> b
    f = (k -> a -> Maybe b) -> m a -> m b
    forall a b. (k -> a -> Maybe b) -> m a -> m b
    forall (m :: * -> *) k a b.
    TrieMap m k =>
    (k -> a -> Maybe b) -> m a -> m b
    mapMaybeWithKeyTM (\ k
    _ a
    a -> b -> Maybe b
    forall a. a -> Maybe a
    Just (a -> b
    f a
    a))

    {-# INLINE mapWithKeyTM #-}
    mapWithKeyTM :: TrieMap m k => (k -> a -> b) -> m a -> m b
    mapWithKeyTM :: forall (m :: * -> *) k a b.
    TrieMap m k =>
    (k -> a -> b) -> m a -> m b
    mapWithKeyTM k -> a -> b
    f = (k -> a -> Maybe b) -> m a -> m b
    forall a b. (k -> a -> Maybe b) -> m a -> m b
    forall (m :: * -> *) k a b.
    TrieMap m k =>
    (k -> a -> Maybe b) -> m a -> m b
    mapMaybeWithKeyTM (\ k
    k a
    a -> b -> Maybe b
    forall a. a -> Maybe a
    Just (k -> a -> b
    f k
    k a
    a))

    {-# INLINE mapMaybeTM #-}
    mapMaybeTM :: TrieMap m k => (a -> Maybe b) -> m a -> m b
    mapMaybeTM :: forall (m :: * -> *) k a b.
    TrieMap m k =>
    (a -> Maybe b) -> m a -> m b
    mapMaybeTM a -> Maybe b
    f = (k -> a -> Maybe b) -> m a -> m b
    forall a b. (k -> a -> Maybe b) -> m a -> m b
    forall (m :: * -> *) k a b.
    TrieMap m k =>
    (k -> a -> Maybe b) -> m a -> m b
    mapMaybeWithKeyTM (\k
    _ -> a -> Maybe b
    f)

    data List m a  = L { forall (m :: * -> *) a. List m a -> Maybe a
    nil  :: Maybe a
                       , forall (m :: * -> *) a. List m a -> m (List m a)
    cons :: m (List m a)
                       } deriving ((forall a b. (a -> b) -> List m a -> List m b)
    -> (forall a b. a -> List m b -> List m a) -> Functor (List m)
    forall a b. a -> List m b -> List m a
    forall a b. (a -> b) -> List m a -> List m b
    forall (m :: * -> *) a b. Functor m => a -> List m b -> List m a
    forall (m :: * -> *) a b.
    Functor m =>
    (a -> b) -> List m a -> List m b
    forall (f :: * -> *).
    (forall a b. (a -> b) -> f a -> f b)
    -> (forall a b. a -> f b -> f a) -> Functor f
    $cfmap :: forall (m :: * -> *) a b.
    Functor m =>
    (a -> b) -> List m a -> List m b
    fmap :: forall a b. (a -> b) -> List m a -> List m b
    $c<$ :: forall (m :: * -> *) a b. Functor m => a -> List m b -> List m a
    <$ :: forall a b. a -> List m b -> List m a
    Functor, (forall m. Monoid m => List m m -> m)
    -> (forall m a. Monoid m => (a -> m) -> List m a -> m)
    -> (forall m a. Monoid m => (a -> m) -> List m a -> m)
    -> (forall a b. (a -> b -> b) -> b -> List m a -> b)
    -> (forall a b. (a -> b -> b) -> b -> List m a -> b)
    -> (forall b a. (b -> a -> b) -> b -> List m a -> b)
    -> (forall b a. (b -> a -> b) -> b -> List m a -> b)
    -> (forall a. (a -> a -> a) -> List m a -> a)
    -> (forall a. (a -> a -> a) -> List m a -> a)
    -> (forall a. List m a -> [a])
    -> (forall a. List m a -> Bool)
    -> (forall a. List m a -> Int)
    -> (forall a. Eq a => a -> List m a -> Bool)
    -> (forall a. Ord a => List m a -> a)
    -> (forall a. Ord a => List m a -> a)
    -> (forall a. Num a => List m a -> a)
    -> (forall a. Num a => List m a -> a)
    -> Foldable (List m)
    forall a. Eq a => a -> List m a -> Bool
    forall a. Num a => List m a -> a
    forall a. Ord a => List m a -> a
    forall m. Monoid m => List m m -> m
    forall a. List m a -> Bool
    forall a. List m a -> Int
    forall a. List m a -> [a]
    forall a. (a -> a -> a) -> List m a -> a
    forall m a. Monoid m => (a -> m) -> List m a -> m
    forall b a. (b -> a -> b) -> b -> List m a -> b
    forall a b. (a -> b -> b) -> b -> List m a -> b
    forall (m :: * -> *) a. (Foldable m, Eq a) => a -> List m a -> Bool
    forall (m :: * -> *) a. (Foldable m, Num a) => List m a -> a
    forall (m :: * -> *) a. (Foldable m, Ord a) => List m a -> a
    forall (m :: * -> *) m. (Foldable m, Monoid m) => List m m -> m
    forall (m :: * -> *) a. Foldable m => List m a -> Bool
    forall (m :: * -> *) a. Foldable m => List m a -> Int
    forall (m :: * -> *) a. Foldable m => List m a -> [a]
    forall (m :: * -> *) a.
    Foldable m =>
    (a -> a -> a) -> List m a -> a
    forall (m :: * -> *) m a.
    (Foldable m, Monoid m) =>
    (a -> m) -> List m a -> m
    forall (m :: * -> *) b a.
    Foldable m =>
    (b -> a -> b) -> b -> List m a -> b
    forall (m :: * -> *) a b.
    Foldable m =>
    (a -> b -> b) -> b -> List m a -> b
    forall (t :: * -> *).
    (forall m. Monoid m => t m -> m)
    -> (forall m a. Monoid m => (a -> m) -> t a -> m)
    -> (forall m a. Monoid m => (a -> m) -> t a -> m)
    -> (forall a b. (a -> b -> b) -> b -> t a -> b)
    -> (forall a b. (a -> b -> b) -> b -> t a -> b)
    -> (forall b a. (b -> a -> b) -> b -> t a -> b)
    -> (forall b a. (b -> a -> b) -> b -> t a -> b)
    -> (forall a. (a -> a -> a) -> t a -> a)
    -> (forall a. (a -> a -> a) -> t a -> a)
    -> (forall a. t a -> [a])
    -> (forall a. t a -> Bool)
    -> (forall a. t a -> Int)
    -> (forall a. Eq a => a -> t a -> Bool)
    -> (forall a. Ord a => t a -> a)
    -> (forall a. Ord a => t a -> a)
    -> (forall a. Num a => t a -> a)
    -> (forall a. Num a => t a -> a)
    -> Foldable t
    $cfold :: forall (m :: * -> *) m. (Foldable m, Monoid m) => List m m -> m
    fold :: forall m. Monoid m => List m m -> m
    $cfoldMap :: forall (m :: * -> *) m a.
    (Foldable m, Monoid m) =>
    (a -> m) -> List m a -> m
    foldMap :: forall m a. Monoid m => (a -> m) -> List m a -> m
    $cfoldMap' :: forall (m :: * -> *) m a.
    (Foldable m, Monoid m) =>
    (a -> m) -> List m a -> m
    foldMap' :: forall m a. Monoid m => (a -> m) -> List m a -> m
    $cfoldr :: forall (m :: * -> *) a b.
    Foldable m =>
    (a -> b -> b) -> b -> List m a -> b
    foldr :: forall a b. (a -> b -> b) -> b -> List m a -> b
    $cfoldr' :: forall (m :: * -> *) a b.
    Foldable m =>
    (a -> b -> b) -> b -> List m a -> b
    foldr' :: forall a b. (a -> b -> b) -> b -> List m a -> b
    $cfoldl :: forall (m :: * -> *) b a.
    Foldable m =>
    (b -> a -> b) -> b -> List m a -> b
    foldl :: forall b a. (b -> a -> b) -> b -> List m a -> b
    $cfoldl' :: forall (m :: * -> *) b a.
    Foldable m =>
    (b -> a -> b) -> b -> List m a -> b
    foldl' :: forall b a. (b -> a -> b) -> b -> List m a -> b
    $cfoldr1 :: forall (m :: * -> *) a.
    Foldable m =>
    (a -> a -> a) -> List m a -> a
    foldr1 :: forall a. (a -> a -> a) -> List m a -> a
    $cfoldl1 :: forall (m :: * -> *) a.
    Foldable m =>
    (a -> a -> a) -> List m a -> a
    foldl1 :: forall a. (a -> a -> a) -> List m a -> a
    $ctoList :: forall (m :: * -> *) a. Foldable m => List m a -> [a]
    toList :: forall a. List m a -> [a]
    $cnull :: forall (m :: * -> *) a. Foldable m => List m a -> Bool
    null :: forall a. List m a -> Bool
    $clength :: forall (m :: * -> *) a. Foldable m => List m a -> Int
    length :: forall a. List m a -> Int
    $celem :: forall (m :: * -> *) a. (Foldable m, Eq a) => a -> List m a -> Bool
    elem :: forall a. Eq a => a -> List m a -> Bool
    $cmaximum :: forall (m :: * -> *) a. (Foldable m, Ord a) => List m a -> a
    maximum :: forall a. Ord a => List m a -> a
    $cminimum :: forall (m :: * -> *) a. (Foldable m, Ord a) => List m a -> a
    minimum :: forall a. Ord a => List m a -> a
    $csum :: forall (m :: * -> *) a. (Foldable m, Num a) => List m a -> a
    sum :: forall a. Num a => List m a -> a
    $cproduct :: forall (m :: * -> *) a. (Foldable m, Num a) => List m a -> a
    product :: forall a. Num a => List m a -> a
    Foldable, Functor (List m)
    Foldable (List m)
    Functor (List m)
    -> Foldable (List m)
    -> (forall (f :: * -> *) a b.
        Applicative f =>
        (a -> f b) -> List m a -> f (List m b))
    -> (forall (f :: * -> *) a.
        Applicative f =>
        List m (f a) -> f (List m a))
    -> (forall (m :: * -> *) a b.
        Monad m =>
        (a -> m b) -> List m a -> m (List m b))
    -> (forall (m :: * -> *) a.
        Monad m =>
        List m (m a) -> m (List m a))
    -> Traversable (List m)
    forall (t :: * -> *).
    Functor t
    -> Foldable t
    -> (forall (f :: * -> *) a b.
        Applicative f =>
        (a -> f b) -> t a -> f (t b))
    -> (forall (f :: * -> *) a. Applicative f => t (f a) -> f (t a))
    -> (forall (m :: * -> *) a b.
        Monad m =>
        (a -> m b) -> t a -> m (t b))
    -> (forall (m :: * -> *) a. Monad m => t (m a) -> m (t a))
    -> Traversable t
    forall {m :: * -> *}. Traversable m => Functor (List m)
    forall {m :: * -> *}. Traversable m => Foldable (List m)
    forall (m :: * -> *) (m :: * -> *) a.
    (Traversable m, Monad m) =>
    List m (m a) -> m (List m a)
    forall (m :: * -> *) (f :: * -> *) a.
    (Traversable m, Applicative f) =>
    List m (f a) -> f (List m a)
    forall (m :: * -> *) (m :: * -> *) a b.
    (Traversable m, Monad m) =>
    (a -> m b) -> List m a -> m (List m b)
    forall (m :: * -> *) (f :: * -> *) a b.
    (Traversable m, Applicative f) =>
    (a -> f b) -> List m a -> f (List m b)
    forall (m :: * -> *) a. Monad m => List m (m a) -> m (List m a)
    forall (f :: * -> *) a.
    Applicative f =>
    List m (f a) -> f (List m a)
    forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> List m a -> m (List m b)
    forall (f :: * -> *) a b.
    Applicative f =>
    (a -> f b) -> List m a -> f (List m b)
    $ctraverse :: forall (m :: * -> *) (f :: * -> *) a b.
    (Traversable m, Applicative f) =>
    (a -> f b) -> List m a -> f (List m b)
    traverse :: forall (f :: * -> *) a b.
    Applicative f =>
    (a -> f b) -> List m a -> f (List m b)
    $csequenceA :: forall (m :: * -> *) (f :: * -> *) a.
    (Traversable m, Applicative f) =>
    List m (f a) -> f (List m a)
    sequenceA :: forall (f :: * -> *) a.
    Applicative f =>
    List m (f a) -> f (List m a)
    $cmapM :: forall (m :: * -> *) (m :: * -> *) a b.
    (Traversable m, Monad m) =>
    (a -> m b) -> List m a -> m (List m b)
    mapM :: forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> List m a -> m (List m b)
    $csequence :: forall (m :: * -> *) (m :: * -> *) a.
    (Traversable m, Monad m) =>
    List m (m a) -> m (List m a)
    sequence :: forall (m :: * -> *) a. Monad m => List m (m a) -> m (List m a)
    Traversable)

    instance TrieMap m a => TrieMap (List m) [a] where
      emptyTM :: forall a. List m a
    emptyTM = L { nil :: Maybe a
    nil = Maybe a
    forall a. Maybe a
    Nothing, cons :: m (List m a)
    cons = m (List m a)
    forall a. m a
    forall (m :: * -> *) k a. TrieMap m k => m a
    emptyTM }

      nullTM :: forall a. List m a -> Bool
    nullTM List m a
    k = Maybe a -> Bool
    forall a. Maybe a -> Bool
    isNothing (List m a -> Maybe a
    forall (m :: * -> *) a. List m a -> Maybe a
    nil List m a
    k) Bool -> Bool -> Bool
    && m (List m a) -> Bool
    forall a. m a -> Bool
    forall (m :: * -> *) k a. TrieMap m k => m a -> Bool
    nullTM (List m a -> m (List m a)
    forall (m :: * -> *) a. List m a -> m (List m a)
    cons List m a
    k)

      lookupTM :: forall a. [a] -> List m a -> Maybe a
    lookupTM [a]
    k =
        case [a]
    k of
          []     -> List m a -> Maybe a
    forall (m :: * -> *) a. List m a -> Maybe a
    nil
          a
    x : [a]
    xs -> [a] -> List m a -> Maybe a
    forall a. [a] -> List m a -> Maybe a
    forall (m :: * -> *) k a. TrieMap m k => k -> m a -> Maybe a
    lookupTM [a]
    xs (List m a -> Maybe a)
    -> (List m a -> Maybe (List m a)) -> List m a -> Maybe a
    forall (m :: * -> *) b c a.
    Monad m =>
    (b -> m c) -> (a -> m b) -> a -> m c
    <=< a -> m (List m a) -> Maybe (List m a)
    forall a. a -> m a -> Maybe a
    forall (m :: * -> *) k a. TrieMap m k => k -> m a -> Maybe a
    lookupTM a
    x (m (List m a) -> Maybe (List m a))
    -> (List m a -> m (List m a)) -> List m a -> Maybe (List m a)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . List m a -> m (List m a)
    forall (m :: * -> *) a. List m a -> m (List m a)
    cons

      alterTM :: forall a. [a] -> (Maybe a -> Maybe a) -> List m a -> List m a
    alterTM [a]
    k Maybe a -> Maybe a
    f List m a
    m =
        case [a]
    k of
          []    -> List m a
    m { nil :: Maybe a
    nil = Maybe a -> Maybe a
    f (List m a -> Maybe a
    forall (m :: * -> *) a. List m a -> Maybe a
    nil List m a
    m) }
          a
    x:[a]
    xs  -> List m a
    m { cons :: m (List m a)
    cons = a
    -> (Maybe (List m a) -> Maybe (List m a))
    -> m (List m a)
    -> m (List m a)
    forall a. a -> (Maybe a -> Maybe a) -> m a -> m a
    forall (m :: * -> *) k a.
    TrieMap m k =>
    k -> (Maybe a -> Maybe a) -> m a -> m a
    alterTM a
    x ([a] -> (Maybe a -> Maybe a) -> Maybe (List m a) -> Maybe (List m a)
    forall (m :: * -> *) k a.
    TrieMap m k =>
    k -> (Maybe a -> Maybe a) -> Maybe (m a) -> Maybe (m a)
    updSub [a]
    xs Maybe a -> Maybe a
    f) (List m a -> m (List m a)
    forall (m :: * -> *) a. List m a -> m (List m a)
    cons List m a
    m) }

      toListTM :: forall a. List m a -> [([a], a)]
    toListTM List m a
    m =
        [ ([], a
    v)  | a
    v <- Maybe a -> [a]
    forall a. Maybe a -> [a]
    maybeToList (List m a -> Maybe a
    forall (m :: * -> *) a. List m a -> Maybe a
    nil List m a
    m) ] [([a], a)] -> [([a], a)] -> [([a], a)]
    forall a. [a] -> [a] -> [a]
    ++
        [ (a
    xa -> [a] -> [a]
    forall a. a -> [a] -> [a]
    :[a]
    xs,a
    v) | (a
    x,List m a
    m1) <- m (List m a) -> [(a, List m a)]
    forall a. m a -> [(a, a)]
    forall (m :: * -> *) k a. TrieMap m k => m a -> [(k, a)]
    toListTM (List m a -> m (List m a)
    forall (m :: * -> *) a. List m a -> m (List m a)
    cons List m a
    m), ([a]
    xs,a
    v) <- List m a -> [([a], a)]
    forall a. List m a -> [([a], a)]
    forall (m :: * -> *) k a. TrieMap m k => m a -> [(k, a)]
    toListTM List m a
    m1 ]

      unionTM :: forall a. (a -> a -> a) -> List m a -> List m a -> List m a
    unionTM a -> a -> a
    f List m a
    m1 List m a
    m2 = L { nil :: Maybe a
    nil  = case (List m a -> Maybe a
    forall (m :: * -> *) a. List m a -> Maybe a
    nil List m a
    m1, List m a -> Maybe a
    forall (m :: * -> *) a. List m a -> Maybe a
    nil List m a
    m2) of
                                     (Just a
    x, Just a
    y) -> a -> Maybe a
    forall a. a -> Maybe a
    Just (a -> a -> a
    f a
    x a
    y)
                                     (Just a
    x, Maybe a
    _)      -> a -> Maybe a
    forall a. a -> Maybe a
    Just a
    x
                                     (Maybe a
    _, Just a
    y)      -> a -> Maybe a
    forall a. a -> Maybe a
    Just a
    y
                                     (Maybe a, Maybe a)
    _                -> Maybe a
    forall a. Maybe a
    Nothing
                          , cons :: m (List m a)
    cons = (List m a -> List m a -> List m a)
    -> m (List m a) -> m (List m a) -> m (List m a)
    forall a. (a -> a -> a) -> m a -> m a -> m a
    forall (m :: * -> *) k a.
    TrieMap m k =>
    (a -> a -> a) -> m a -> m a -> m a
    unionTM ((a -> a -> a) -> List m a -> List m a -> List m a
    forall a. (a -> a -> a) -> List m a -> List m a -> List m a
    forall (m :: * -> *) k a.
    TrieMap m k =>
    (a -> a -> a) -> m a -> m a -> m a
    unionTM a -> a -> a
    f) (List m a -> m (List m a)
    forall (m :: * -> *) a. List m a -> m (List m a)
    cons List m a
    m1) (List m a -> m (List m a)
    forall (m :: * -> *) a. List m a -> m (List m a)
    cons List m a
    m2)
                          }

      mapMaybeWithKeyTM :: forall a b. ([a] -> a -> Maybe b) -> List m a -> List m b
    mapMaybeWithKeyTM [a] -> a -> Maybe b
    f = [a] -> List m a -> List m b
    forall {m :: * -> *}. TrieMap m a => [a] -> List m a -> List m b
    go []
        where
        go :: [a] -> List m a -> List m b
    go [a]
    acc List m a
    l = L { nil :: Maybe b
    nil  = [a] -> a -> Maybe b
    f ([a] -> [a]
    forall a. [a] -> [a]
    reverse [a]
    acc) (a -> Maybe b) -> Maybe a -> Maybe b
    forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
    =<< List m a -> Maybe a
    forall (m :: * -> *) a. List m a -> Maybe a
    nil List m a
    l
                     , cons :: m (List m b)
    cons = (a -> List m a -> Maybe (List m b)) -> m (List m a) -> m (List m b)
    forall a b. (a -> a -> Maybe b) -> m a -> m b
    forall (m :: * -> *) k a b.
    TrieMap m k =>
    (k -> a -> Maybe b) -> m a -> m b
    mapMaybeWithKeyTM (\a
    k List m a
    a -> List m b -> Maybe (List m b)
    forall a. a -> Maybe a
    Just ([a] -> List m a -> List m b
    go (a
    ka -> [a] -> [a]
    forall a. a -> [a] -> [a]
    :[a]
    acc) List m a
    a)) (List m a -> m (List m a)
    forall (m :: * -> *) a. List m a -> m (List m a)
    cons List m a
    l)
                     }

    instance Ord a => TrieMap (Map a) a where
      emptyTM :: forall a. Map a a
    emptyTM  = Map a a
    forall k a. Map k a
    Map.empty
      nullTM :: forall a. Map a a -> Bool
    nullTM   = Map a a -> Bool
    forall k a. Map k a -> Bool
    Map.null
      lookupTM :: forall a. a -> Map a a -> Maybe a
    lookupTM = a -> Map a a -> Maybe a
    forall k a. Ord k => k -> Map k a -> Maybe a
    Map.lookup
      alterTM :: forall a. a -> (Maybe a -> Maybe a) -> Map a a -> Map a a
    alterTM  = ((Maybe a -> Maybe a) -> a -> Map a a -> Map a a)
    -> a -> (Maybe a -> Maybe a) -> Map a a -> Map a a
    forall a b c. (a -> b -> c) -> b -> a -> c
    flip (Maybe a -> Maybe a) -> a -> Map a a -> Map a a
    forall k a.
    Ord k =>
    (Maybe a -> Maybe a) -> k -> Map k a -> Map k a
    Map.alter
      toListTM :: forall a. Map a a -> [(a, a)]
    toListTM = Map a a -> [(a, a)]
    forall k a. Map k a -> [(k, a)]
    Map.toList
      unionTM :: forall a. (a -> a -> a) -> Map a a -> Map a a -> Map a a
    unionTM  = (a -> a -> a) -> Map a a -> Map a a -> Map a a
    forall k a. Ord k => (a -> a -> a) -> Map k a -> Map k a -> Map k a
    Map.unionWith

      mapMaybeWithKeyTM :: forall a b. (a -> a -> Maybe b) -> Map a a -> Map a b
    mapMaybeWithKeyTM = (a -> a -> Maybe b) -> Map a a -> Map a b
    forall k a b. (k -> a -> Maybe b) -> Map k a -> Map k b
    Map.mapMaybeWithKey

    type TypesMap = List TypeMap

    data TypeMap a = TM { forall a. TypeMap a -> Map TVar a
    tvar :: Map TVar a
                        , forall a. TypeMap a -> Map TCon (List TypeMap a)
    tcon :: Map TCon    (List TypeMap a)
                        , forall a. TypeMap a -> Map [Ident] (List TypeMap a)
    trec :: Map [Ident] (List TypeMap a)
                        , forall a. TypeMap a -> Map Newtype (List TypeMap a)
    tnewtype :: Map Newtype (List TypeMap a)
                        } deriving ((forall a b. (a -> b) -> TypeMap a -> TypeMap b)
    -> (forall a b. a -> TypeMap b -> TypeMap a) -> Functor TypeMap
    forall a b. a -> TypeMap b -> TypeMap a
    forall a b. (a -> b) -> TypeMap a -> TypeMap b
    forall (f :: * -> *).
    (forall a b. (a -> b) -> f a -> f b)
    -> (forall a b. a -> f b -> f a) -> Functor f
    $cfmap :: forall a b. (a -> b) -> TypeMap a -> TypeMap b
    fmap :: forall a b. (a -> b) -> TypeMap a -> TypeMap b
    $c<$ :: forall a b. a -> TypeMap b -> TypeMap a
    <$ :: forall a b. a -> TypeMap b -> TypeMap a
    Functor, (forall m. Monoid m => TypeMap m -> m)
    -> (forall m a. Monoid m => (a -> m) -> TypeMap a -> m)
    -> (forall m a. Monoid m => (a -> m) -> TypeMap a -> m)
    -> (forall a b. (a -> b -> b) -> b -> TypeMap a -> b)
    -> (forall a b. (a -> b -> b) -> b -> TypeMap a -> b)
    -> (forall b a. (b -> a -> b) -> b -> TypeMap a -> b)
    -> (forall b a. (b -> a -> b) -> b -> TypeMap a -> b)
    -> (forall a. (a -> a -> a) -> TypeMap a -> a)
    -> (forall a. (a -> a -> a) -> TypeMap a -> a)
    -> (forall a. TypeMap a -> [a])
    -> (forall a. TypeMap a -> Bool)
    -> (forall a. TypeMap a -> Int)
    -> (forall a. Eq a => a -> TypeMap a -> Bool)
    -> (forall a. Ord a => TypeMap a -> a)
    -> (forall a. Ord a => TypeMap a -> a)
    -> (forall a. Num a => TypeMap a -> a)
    -> (forall a. Num a => TypeMap a -> a)
    -> Foldable TypeMap
    forall a. Eq a => a -> TypeMap a -> Bool
    forall a. Num a => TypeMap a -> a
    forall a. Ord a => TypeMap a -> a
    forall m. Monoid m => TypeMap m -> m
    forall a. TypeMap a -> Bool
    forall a. TypeMap a -> Int
    forall a. TypeMap a -> [a]
    forall a. (a -> a -> a) -> TypeMap a -> a
    forall m a. Monoid m => (a -> m) -> TypeMap a -> m
    forall b a. (b -> a -> b) -> b -> TypeMap a -> b
    forall a b. (a -> b -> b) -> b -> TypeMap a -> b
    forall (t :: * -> *).
    (forall m. Monoid m => t m -> m)
    -> (forall m a. Monoid m => (a -> m) -> t a -> m)
    -> (forall m a. Monoid m => (a -> m) -> t a -> m)
    -> (forall a b. (a -> b -> b) -> b -> t a -> b)
    -> (forall a b. (a -> b -> b) -> b -> t a -> b)
    -> (forall b a. (b -> a -> b) -> b -> t a -> b)
    -> (forall b a. (b -> a -> b) -> b -> t a -> b)
    -> (forall a. (a -> a -> a) -> t a -> a)
    -> (forall a. (a -> a -> a) -> t a -> a)
    -> (forall a. t a -> [a])
    -> (forall a. t a -> Bool)
    -> (forall a. t a -> Int)
    -> (forall a. Eq a => a -> t a -> Bool)
    -> (forall a. Ord a => t a -> a)
    -> (forall a. Ord a => t a -> a)
    -> (forall a. Num a => t a -> a)
    -> (forall a. Num a => t a -> a)
    -> Foldable t
    $cfold :: forall m. Monoid m => TypeMap m -> m
    fold :: forall m. Monoid m => TypeMap m -> m
    $cfoldMap :: forall m a. Monoid m => (a -> m) -> TypeMap a -> m
    foldMap :: forall m a. Monoid m => (a -> m) -> TypeMap a -> m
    $cfoldMap' :: forall m a. Monoid m => (a -> m) -> TypeMap a -> m
    foldMap' :: forall m a. Monoid m => (a -> m) -> TypeMap a -> m
    $cfoldr :: forall a b. (a -> b -> b) -> b -> TypeMap a -> b
    foldr :: forall a b. (a -> b -> b) -> b -> TypeMap a -> b
    $cfoldr' :: forall a b. (a -> b -> b) -> b -> TypeMap a -> b
    foldr' :: forall a b. (a -> b -> b) -> b -> TypeMap a -> b
    $cfoldl :: forall b a. (b -> a -> b) -> b -> TypeMap a -> b
    foldl :: forall b a. (b -> a -> b) -> b -> TypeMap a -> b
    $cfoldl' :: forall b a. (b -> a -> b) -> b -> TypeMap a -> b
    foldl' :: forall b a. (b -> a -> b) -> b -> TypeMap a -> b
    $cfoldr1 :: forall a. (a -> a -> a) -> TypeMap a -> a
    foldr1 :: forall a. (a -> a -> a) -> TypeMap a -> a
    $cfoldl1 :: forall a. (a -> a -> a) -> TypeMap a -> a
    foldl1 :: forall a. (a -> a -> a) -> TypeMap a -> a
    $ctoList :: forall a. TypeMap a -> [a]
    toList :: forall a. TypeMap a -> [a]
    $cnull :: forall a. TypeMap a -> Bool
    null :: forall a. TypeMap a -> Bool
    $clength :: forall a. TypeMap a -> Int
    length :: forall a. TypeMap a -> Int
    $celem :: forall a. Eq a => a -> TypeMap a -> Bool
    elem :: forall a. Eq a => a -> TypeMap a -> Bool
    $cmaximum :: forall a. Ord a => TypeMap a -> a
    maximum :: forall a. Ord a => TypeMap a -> a
    $cminimum :: forall a. Ord a => TypeMap a -> a
    minimum :: forall a. Ord a => TypeMap a -> a
    $csum :: forall a. Num a => TypeMap a -> a
    sum :: forall a. Num a => TypeMap a -> a
    $cproduct :: forall a. Num a => TypeMap a -> a
    product :: forall a. Num a => TypeMap a -> a
    Foldable, Functor TypeMap
    Foldable TypeMap
    Functor TypeMap
    -> Foldable TypeMap
    -> (forall (f :: * -> *) a b.
        Applicative f =>
        (a -> f b) -> TypeMap a -> f (TypeMap b))
    -> (forall (f :: * -> *) a.
        Applicative f =>
        TypeMap (f a) -> f (TypeMap a))
    -> (forall (m :: * -> *) a b.
        Monad m =>
        (a -> m b) -> TypeMap a -> m (TypeMap b))
    -> (forall (m :: * -> *) a.
        Monad m =>
        TypeMap (m a) -> m (TypeMap a))
    -> Traversable TypeMap
    forall (t :: * -> *).
    Functor t
    -> Foldable t
    -> (forall (f :: * -> *) a b.
        Applicative f =>
        (a -> f b) -> t a -> f (t b))
    -> (forall (f :: * -> *) a. Applicative f => t (f a) -> f (t a))
    -> (forall (m :: * -> *) a b.
        Monad m =>
        (a -> m b) -> t a -> m (t b))
    -> (forall (m :: * -> *) a. Monad m => t (m a) -> m (t a))
    -> Traversable t
    forall (m :: * -> *) a. Monad m => TypeMap (m a) -> m (TypeMap a)
    forall (f :: * -> *) a.
    Applicative f =>
    TypeMap (f a) -> f (TypeMap a)
    forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> TypeMap a -> m (TypeMap b)
    forall (f :: * -> *) a b.
    Applicative f =>
    (a -> f b) -> TypeMap a -> f (TypeMap b)
    $ctraverse :: forall (f :: * -> *) a b.
    Applicative f =>
    (a -> f b) -> TypeMap a -> f (TypeMap b)
    traverse :: forall (f :: * -> *) a b.
    Applicative f =>
    (a -> f b) -> TypeMap a -> f (TypeMap b)
    $csequenceA :: forall (f :: * -> *) a.
    Applicative f =>
    TypeMap (f a) -> f (TypeMap a)
    sequenceA :: forall (f :: * -> *) a.
    Applicative f =>
    TypeMap (f a) -> f (TypeMap a)
    $cmapM :: forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> TypeMap a -> m (TypeMap b)
    mapM :: forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> TypeMap a -> m (TypeMap b)
    $csequence :: forall (m :: * -> *) a. Monad m => TypeMap (m a) -> m (TypeMap a)
    sequence :: forall (m :: * -> *) a. Monad m => TypeMap (m a) -> m (TypeMap a)
    Traversable)

    instance TrieMap TypeMap Type where
      emptyTM :: forall a. TypeMap a
    emptyTM = TM { tvar :: Map TVar a
    tvar = Map TVar a
    forall a. Map TVar a
    forall (m :: * -> *) k a. TrieMap m k => m a
    emptyTM, tcon :: Map TCon (List TypeMap a)
    tcon = Map TCon (List TypeMap a)
    forall a. Map TCon a
    forall (m :: * -> *) k a. TrieMap m k => m a
    emptyTM, trec :: Map [Ident] (List TypeMap a)
    trec = Map [Ident] (List TypeMap a)
    forall a. Map [Ident] a
    forall (m :: * -> *) k a. TrieMap m k => m a
    emptyTM, tnewtype :: Map Newtype (List TypeMap a)
    tnewtype = Map Newtype (List TypeMap a)
    forall a. Map Newtype a
    forall (m :: * -> *) k a. TrieMap m k => m a
    emptyTM }

      nullTM :: forall a. TypeMap a -> Bool
    nullTM TypeMap a
    ty = [Bool] -> Bool
    forall (t :: * -> *). Foldable t => t Bool -> Bool
    and [ Map TVar a -> Bool
    forall a. Map TVar a -> Bool
    forall (m :: * -> *) k a. TrieMap m k => m a -> Bool
    nullTM (TypeMap a -> Map TVar a
    forall a. TypeMap a -> Map TVar a
    tvar TypeMap a
    ty)
                      , Map TCon (List TypeMap a) -> Bool
    forall a. Map TCon a -> Bool
    forall (m :: * -> *) k a. TrieMap m k => m a -> Bool
    nullTM (TypeMap a -> Map TCon (List TypeMap a)
    forall a. TypeMap a -> Map TCon (List TypeMap a)
    tcon TypeMap a
    ty)
                      , Map [Ident] (List TypeMap a) -> Bool
    forall a. Map [Ident] a -> Bool
    forall (m :: * -> *) k a. TrieMap m k => m a -> Bool
    nullTM (TypeMap a -> Map [Ident] (List TypeMap a)
    forall a. TypeMap a -> Map [Ident] (List TypeMap a)
    trec TypeMap a
    ty)
                      , Map Newtype (List TypeMap a) -> Bool
    forall a. Map Newtype a -> Bool
    forall (m :: * -> *) k a. TrieMap m k => m a -> Bool
    nullTM (TypeMap a -> Map Newtype (List TypeMap a)
    forall a. TypeMap a -> Map Newtype (List TypeMap a)
    tnewtype TypeMap a
    ty)
                      ]

      lookupTM :: forall a. Type -> TypeMap a -> Maybe a
    lookupTM Type
    ty =
        case Type
    ty of
          TUser Name
    _ [Type]
    _ Type
    t -> Type -> TypeMap a -> Maybe a
    forall a. Type -> TypeMap a -> Maybe a
    forall (m :: * -> *) k a. TrieMap m k => k -> m a -> Maybe a
    lookupTM Type
    t
          TVar TVar
    x      -> TVar -> Map TVar a -> Maybe a
    forall a. TVar -> Map TVar a -> Maybe a
    forall (m :: * -> *) k a. TrieMap m k => k -> m a -> Maybe a
    lookupTM TVar
    x (Map TVar a -> Maybe a)
    -> (TypeMap a -> Map TVar a) -> TypeMap a -> Maybe a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . TypeMap a -> Map TVar a
    forall a. TypeMap a -> Map TVar a
    tvar
          TCon TCon
    c [Type]
    ts   -> [Type] -> List TypeMap a -> Maybe a
    forall a. [Type] -> List TypeMap a -> Maybe a
    forall (m :: * -> *) k a. TrieMap m k => k -> m a -> Maybe a
    lookupTM [Type]
    ts (List TypeMap a -> Maybe a)
    -> (TypeMap a -> Maybe (List TypeMap a)) -> TypeMap a -> Maybe a
    forall (m :: * -> *) b c a.
    Monad m =>
    (b -> m c) -> (a -> m b) -> a -> m c
    <=< TCon -> Map TCon (List TypeMap a) -> Maybe (List TypeMap a)
    forall a. TCon -> Map TCon a -> Maybe a
    forall (m :: * -> *) k a. TrieMap m k => k -> m a -> Maybe a
    lookupTM TCon
    c (Map TCon (List TypeMap a) -> Maybe (List TypeMap a))
    -> (TypeMap a -> Map TCon (List TypeMap a))
    -> TypeMap a
    -> Maybe (List TypeMap a)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . TypeMap a -> Map TCon (List TypeMap a)
    forall a. TypeMap a -> Map TCon (List TypeMap a)
    tcon
          TRec RecordMap Ident Type
    fs     -> let ([Ident]
    xs,[Type]
    ts) = [(Ident, Type)] -> ([Ident], [Type])
    forall a b. [(a, b)] -> ([a], [b])
    unzip ([(Ident, Type)] -> ([Ident], [Type]))
    -> [(Ident, Type)] -> ([Ident], [Type])
    forall a b. (a -> b) -> a -> b
    $ RecordMap Ident Type -> [(Ident, Type)]
    forall a b. RecordMap a b -> [(a, b)]
    canonicalFields RecordMap Ident Type
    fs
                         in [Type] -> List TypeMap a -> Maybe a
    forall a. [Type] -> List TypeMap a -> Maybe a
    forall (m :: * -> *) k a. TrieMap m k => k -> m a -> Maybe a
    lookupTM [Type]
    ts (List TypeMap a -> Maybe a)
    -> (TypeMap a -> Maybe (List TypeMap a)) -> TypeMap a -> Maybe a
    forall (m :: * -> *) b c a.
    Monad m =>
    (b -> m c) -> (a -> m b) -> a -> m c
    <=< [Ident] -> Map [Ident] (List TypeMap a) -> Maybe (List TypeMap a)
    forall a. [Ident] -> Map [Ident] a -> Maybe a
    forall (m :: * -> *) k a. TrieMap m k => k -> m a -> Maybe a
    lookupTM [Ident]
    xs (Map [Ident] (List TypeMap a) -> Maybe (List TypeMap a))
    -> (TypeMap a -> Map [Ident] (List TypeMap a))
    -> TypeMap a
    -> Maybe (List TypeMap a)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . TypeMap a -> Map [Ident] (List TypeMap a)
    forall a. TypeMap a -> Map [Ident] (List TypeMap a)
    trec
          TNewtype Newtype
    nt [Type]
    ts -> [Type] -> List TypeMap a -> Maybe a
    forall a. [Type] -> List TypeMap a -> Maybe a
    forall (m :: * -> *) k a. TrieMap m k => k -> m a -> Maybe a
    lookupTM [Type]
    ts (List TypeMap a -> Maybe a)
    -> (TypeMap a -> Maybe (List TypeMap a)) -> TypeMap a -> Maybe a
    forall (m :: * -> *) b c a.
    Monad m =>
    (b -> m c) -> (a -> m b) -> a -> m c
    <=< Newtype -> Map Newtype (List TypeMap a) -> Maybe (List TypeMap a)
    forall a. Newtype -> Map Newtype a -> Maybe a
    forall (m :: * -> *) k a. TrieMap m k => k -> m a -> Maybe a
    lookupTM Newtype
    nt (Map Newtype (List TypeMap a) -> Maybe (List TypeMap a))
    -> (TypeMap a -> Map Newtype (List TypeMap a))
    -> TypeMap a
    -> Maybe (List TypeMap a)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . TypeMap a -> Map Newtype (List TypeMap a)
    forall a. TypeMap a -> Map Newtype (List TypeMap a)
    tnewtype

      alterTM :: forall a. Type -> (Maybe a -> Maybe a) -> TypeMap a -> TypeMap a
    alterTM Type
    ty Maybe a -> Maybe a
    f TypeMap a
    m =
        case Type
    ty of
          TUser Name
    _ [Type]
    _ Type
    t -> Type -> (Maybe a -> Maybe a) -> TypeMap a -> TypeMap a
    forall a. Type -> (Maybe a -> Maybe a) -> TypeMap a -> TypeMap a
    forall (m :: * -> *) k a.
    TrieMap m k =>
    k -> (Maybe a -> Maybe a) -> m a -> m a
    alterTM Type
    t Maybe a -> Maybe a
    f TypeMap a
    m
          TVar TVar
    x      -> TypeMap a
    m { tvar :: Map TVar a
    tvar = TVar -> (Maybe a -> Maybe a) -> Map TVar a -> Map TVar a
    forall a. TVar -> (Maybe a -> Maybe a) -> Map TVar a -> Map TVar a
    forall (m :: * -> *) k a.
    TrieMap m k =>
    k -> (Maybe a -> Maybe a) -> m a -> m a
    alterTM TVar
    x Maybe a -> Maybe a
    f (TypeMap a -> Map TVar a
    forall a. TypeMap a -> Map TVar a
    tvar TypeMap a
    m) }
          TCon TCon
    c [Type]
    ts   -> TypeMap a
    m { tcon :: Map TCon (List TypeMap a)
    tcon = TCon
    -> (Maybe (List TypeMap a) -> Maybe (List TypeMap a))
    -> Map TCon (List TypeMap a)
    -> Map TCon (List TypeMap a)
    forall a. TCon -> (Maybe a -> Maybe a) -> Map TCon a -> Map TCon a
    forall (m :: * -> *) k a.
    TrieMap m k =>
    k -> (Maybe a -> Maybe a) -> m a -> m a
    alterTM TCon
    c ([Type]
    -> (Maybe a -> Maybe a)
    -> Maybe (List TypeMap a)
    -> Maybe (List TypeMap a)
    forall (m :: * -> *) k a.
    TrieMap m k =>
    k -> (Maybe a -> Maybe a) -> Maybe (m a) -> Maybe (m a)
    updSub [Type]
    ts Maybe a -> Maybe a
    f) (TypeMap a -> Map TCon (List TypeMap a)
    forall a. TypeMap a -> Map TCon (List TypeMap a)
    tcon TypeMap a
    m) }
          TRec RecordMap Ident Type
    fs     -> let ([Ident]
    xs,[Type]
    ts) = [(Ident, Type)] -> ([Ident], [Type])
    forall a b. [(a, b)] -> ([a], [b])
    unzip ([(Ident, Type)] -> ([Ident], [Type]))
    -> [(Ident, Type)] -> ([Ident], [Type])
    forall a b. (a -> b) -> a -> b
    $ RecordMap Ident Type -> [(Ident, Type)]
    forall a b. RecordMap a b -> [(a, b)]
    canonicalFields RecordMap Ident Type
    fs
                         in TypeMap a
    m { trec :: Map [Ident] (List TypeMap a)
    trec = [Ident]
    -> (Maybe (List TypeMap a) -> Maybe (List TypeMap a))
    -> Map [Ident] (List TypeMap a)
    -> Map [Ident] (List TypeMap a)
    forall a.
    [Ident] -> (Maybe a -> Maybe a) -> Map [Ident] a -> Map [Ident] a
    forall (m :: * -> *) k a.
    TrieMap m k =>
    k -> (Maybe a -> Maybe a) -> m a -> m a
    alterTM [Ident]
    xs ([Type]
    -> (Maybe a -> Maybe a)
    -> Maybe (List TypeMap a)
    -> Maybe (List TypeMap a)
    forall (m :: * -> *) k a.
    TrieMap m k =>
    k -> (Maybe a -> Maybe a) -> Maybe (m a) -> Maybe (m a)
    updSub [Type]
    ts Maybe a -> Maybe a
    f) (TypeMap a -> Map [Ident] (List TypeMap a)
    forall a. TypeMap a -> Map [Ident] (List TypeMap a)
    trec TypeMap a
    m) }
          TNewtype Newtype
    nt [Type]
    ts -> TypeMap a
    m { tnewtype :: Map Newtype (List TypeMap a)
    tnewtype = Newtype
    -> (Maybe (List TypeMap a) -> Maybe (List TypeMap a))
    -> Map Newtype (List TypeMap a)
    -> Map Newtype (List TypeMap a)
    forall a.
    Newtype -> (Maybe a -> Maybe a) -> Map Newtype a -> Map Newtype a
    forall (m :: * -> *) k a.
    TrieMap m k =>
    k -> (Maybe a -> Maybe a) -> m a -> m a
    alterTM Newtype
    nt ([Type]
    -> (Maybe a -> Maybe a)
    -> Maybe (List TypeMap a)
    -> Maybe (List TypeMap a)
    forall (m :: * -> *) k a.
    TrieMap m k =>
    k -> (Maybe a -> Maybe a) -> Maybe (m a) -> Maybe (m a)
    updSub [Type]
    ts Maybe a -> Maybe a
    f) (TypeMap a -> Map Newtype (List TypeMap a)
    forall a. TypeMap a -> Map Newtype (List TypeMap a)
    tnewtype TypeMap a
    m) }

      toListTM :: forall a. TypeMap a -> [(Type, a)]
    toListTM TypeMap a
    m =
        [ (TVar -> Type
    TVar TVar
    x,           a
    v) | (TVar
    x,a
    v)   <- Map TVar a -> [(TVar, a)]
    forall a. Map TVar a -> [(TVar, a)]
    forall (m :: * -> *) k a. TrieMap m k => m a -> [(k, a)]
    toListTM (TypeMap a -> Map TVar a
    forall a. TypeMap a -> Map TVar a
    tvar TypeMap a
    m) ] [(Type, a)] -> [(Type, a)] -> [(Type, a)]
    forall a. [a] -> [a] -> [a]
    ++
        [ (TCon -> [Type] -> Type
    TCon TCon
    c [Type]
    ts,        a
    v) | (TCon
    c,List TypeMap a
    m1)  <- Map TCon (List TypeMap a) -> [(TCon, List TypeMap a)]
    forall a. Map TCon a -> [(TCon, a)]
    forall (m :: * -> *) k a. TrieMap m k => m a -> [(k, a)]
    toListTM (TypeMap a -> Map TCon (List TypeMap a)
    forall a. TypeMap a -> Map TCon (List TypeMap a)
    tcon TypeMap a
    m)
                                , ([Type]
    ts,a
    v)  <- List TypeMap a -> [([Type], a)]
    forall a. List TypeMap a -> [([Type], a)]
    forall (m :: * -> *) k a. TrieMap m k => m a -> [(k, a)]
    toListTM List TypeMap a
    m1 ] [(Type, a)] -> [(Type, a)] -> [(Type, a)]
    forall a. [a] -> [a] -> [a]
    ++

        -- NB: this step loses 'displayOrder' information.
        --  It's not clear if we should try to fix this.
        [ (RecordMap Ident Type -> Type
    TRec ([(Ident, Type)] -> RecordMap Ident Type
    forall a b. (Show a, Ord a) => [(a, b)] -> RecordMap a b
    recordFromFields ([Ident] -> [Type] -> [(Ident, Type)]
    forall a b. [a] -> [b] -> [(a, b)]
    zip [Ident]
    fs [Type]
    ts)), a
    v)
              | ([Ident]
    fs,List TypeMap a
    m1) <- Map [Ident] (List TypeMap a) -> [([Ident], List TypeMap a)]
    forall a. Map [Ident] a -> [([Ident], a)]
    forall (m :: * -> *) k a. TrieMap m k => m a -> [(k, a)]
    toListTM (TypeMap a -> Map [Ident] (List TypeMap a)
    forall a. TypeMap a -> Map [Ident] (List TypeMap a)
    trec TypeMap a
    m)
              , ([Type]
    ts,a
    v)  <- List TypeMap a -> [([Type], a)]
    forall a. List TypeMap a -> [([Type], a)]
    forall (m :: * -> *) k a. TrieMap m k => m a -> [(k, a)]
    toListTM List TypeMap a
    m1 ] [(Type, a)] -> [(Type, a)] -> [(Type, a)]
    forall a. [a] -> [a] -> [a]
    ++

        [ (Newtype -> [Type] -> Type
    TNewtype Newtype
    nt [Type]
    ts, a
    v) | (Newtype
    nt,List TypeMap a
    m1) <- Map Newtype (List TypeMap a) -> [(Newtype, List TypeMap a)]
    forall a. Map Newtype a -> [(Newtype, a)]
    forall (m :: * -> *) k a. TrieMap m k => m a -> [(k, a)]
    toListTM (TypeMap a -> Map Newtype (List TypeMap a)
    forall a. TypeMap a -> Map Newtype (List TypeMap a)
    tnewtype TypeMap a
    m)
                              , ([Type]
    ts,a
    v)  <- List TypeMap a -> [([Type], a)]
    forall a. List TypeMap a -> [([Type], a)]
    forall (m :: * -> *) k a. TrieMap m k => m a -> [(k, a)]
    toListTM List TypeMap a
    m1
        ]

      unionTM :: forall a. (a -> a -> a) -> TypeMap a -> TypeMap a -> TypeMap a
    unionTM a -> a -> a
    f TypeMap a
    m1 TypeMap a
    m2 = TM { tvar :: Map TVar a
    tvar = (a -> a -> a) -> Map TVar a -> Map TVar a -> Map TVar a
    forall a. (a -> a -> a) -> Map TVar a -> Map TVar a -> Map TVar a
    forall (m :: * -> *) k a.
    TrieMap m k =>
    (a -> a -> a) -> m a -> m a -> m a
    unionTM a -> a -> a
    f (TypeMap a -> Map TVar a
    forall a. TypeMap a -> Map TVar a
    tvar TypeMap a
    m1) (TypeMap a -> Map TVar a
    forall a. TypeMap a -> Map TVar a
    tvar TypeMap a
    m2)
                           , tcon :: Map TCon (List TypeMap a)
    tcon = (List TypeMap a -> List TypeMap a -> List TypeMap a)
    -> Map TCon (List TypeMap a)
    -> Map TCon (List TypeMap a)
    -> Map TCon (List TypeMap a)
    forall a. (a -> a -> a) -> Map TCon a -> Map TCon a -> Map TCon a
    forall (m :: * -> *) k a.
    TrieMap m k =>
    (a -> a -> a) -> m a -> m a -> m a
    unionTM ((a -> a -> a) -> List TypeMap a -> List TypeMap a -> List TypeMap a
    forall a.
    (a -> a -> a) -> List TypeMap a -> List TypeMap a -> List TypeMap a
    forall (m :: * -> *) k a.
    TrieMap m k =>
    (a -> a -> a) -> m a -> m a -> m a
    unionTM a -> a -> a
    f) (TypeMap a -> Map TCon (List TypeMap a)
    forall a. TypeMap a -> Map TCon (List TypeMap a)
    tcon TypeMap a
    m1) (TypeMap a -> Map TCon (List TypeMap a)
    forall a. TypeMap a -> Map TCon (List TypeMap a)
    tcon TypeMap a
    m2)
                           , trec :: Map [Ident] (List TypeMap a)
    trec = (List TypeMap a -> List TypeMap a -> List TypeMap a)
    -> Map [Ident] (List TypeMap a)
    -> Map [Ident] (List TypeMap a)
    -> Map [Ident] (List TypeMap a)
    forall a.
    (a -> a -> a) -> Map [Ident] a -> Map [Ident] a -> Map [Ident] a
    forall (m :: * -> *) k a.
    TrieMap m k =>
    (a -> a -> a) -> m a -> m a -> m a
    unionTM ((a -> a -> a) -> List TypeMap a -> List TypeMap a -> List TypeMap a
    forall a.
    (a -> a -> a) -> List TypeMap a -> List TypeMap a -> List TypeMap a
    forall (m :: * -> *) k a.
    TrieMap m k =>
    (a -> a -> a) -> m a -> m a -> m a
    unionTM a -> a -> a
    f) (TypeMap a -> Map [Ident] (List TypeMap a)
    forall a. TypeMap a -> Map [Ident] (List TypeMap a)
    trec TypeMap a
    m1) (TypeMap a -> Map [Ident] (List TypeMap a)
    forall a. TypeMap a -> Map [Ident] (List TypeMap a)
    trec TypeMap a
    m2)
                           , tnewtype :: Map Newtype (List TypeMap a)
    tnewtype = (List TypeMap a -> List TypeMap a -> List TypeMap a)
    -> Map Newtype (List TypeMap a)
    -> Map Newtype (List TypeMap a)
    -> Map Newtype (List TypeMap a)
    forall a.
    (a -> a -> a) -> Map Newtype a -> Map Newtype a -> Map Newtype a
    forall (m :: * -> *) k a.
    TrieMap m k =>
    (a -> a -> a) -> m a -> m a -> m a
    unionTM ((a -> a -> a) -> List TypeMap a -> List TypeMap a -> List TypeMap a
    forall a.
    (a -> a -> a) -> List TypeMap a -> List TypeMap a -> List TypeMap a
    forall (m :: * -> *) k a.
    TrieMap m k =>
    (a -> a -> a) -> m a -> m a -> m a
    unionTM a -> a -> a
    f) (TypeMap a -> Map Newtype (List TypeMap a)
    forall a. TypeMap a -> Map Newtype (List TypeMap a)
    tnewtype TypeMap a
    m1) (TypeMap a -> Map Newtype (List TypeMap a)
    forall a. TypeMap a -> Map Newtype (List TypeMap a)
    tnewtype TypeMap a
    m2)
                           }

      mapMaybeWithKeyTM :: forall a b. (Type -> a -> Maybe b) -> TypeMap a -> TypeMap b
    mapMaybeWithKeyTM Type -> a -> Maybe b
    f TypeMap a
    m =
        TM { tvar :: Map TVar b
    tvar = (TVar -> a -> Maybe b) -> Map TVar a -> Map TVar b
    forall a b. (TVar -> a -> Maybe b) -> Map TVar a -> Map TVar b
    forall (m :: * -> *) k a b.
    TrieMap m k =>
    (k -> a -> Maybe b) -> m a -> m b
    mapMaybeWithKeyTM (\TVar
    v -> Type -> a -> Maybe b
    f (TVar -> Type
    TVar TVar
    v)) (TypeMap a -> Map TVar a
    forall a. TypeMap a -> Map TVar a
    tvar TypeMap a
    m)
           , tcon :: Map TCon (List TypeMap b)
    tcon = (TCon -> List TypeMap a -> List TypeMap b)
    -> Map TCon (List TypeMap a) -> Map TCon (List TypeMap b)
    forall (m :: * -> *) k a b.
    TrieMap m k =>
    (k -> a -> b) -> m a -> m b
    mapWithKeyTM (\TCon
    c  List TypeMap a
    l -> ([Type] -> a -> Maybe b) -> List TypeMap a -> List TypeMap b
    forall a b.
    ([Type] -> a -> Maybe b) -> List TypeMap a -> List TypeMap b
    forall (m :: * -> *) k a b.
    TrieMap m k =>
    (k -> a -> Maybe b) -> m a -> m b
    mapMaybeWithKeyTM
                                 (\[Type]
    ts a
    a -> Type -> a -> Maybe b
    f (TCon -> [Type] -> Type
    TCon TCon
    c [Type]
    ts) a
    a) List TypeMap a
    l) (TypeMap a -> Map TCon (List TypeMap a)
    forall a. TypeMap a -> Map TCon (List TypeMap a)
    tcon TypeMap a
    m)
           , trec :: Map [Ident] (List TypeMap b)
    trec = ([Ident] -> List TypeMap a -> List TypeMap b)
    -> Map [Ident] (List TypeMap a) -> Map [Ident] (List TypeMap b)
    forall (m :: * -> *) k a b.
    TrieMap m k =>
    (k -> a -> b) -> m a -> m b
    mapWithKeyTM (\[Ident]
    fs List TypeMap a
    l -> ([Type] -> a -> Maybe b) -> List TypeMap a -> List TypeMap b
    forall a b.
    ([Type] -> a -> Maybe b) -> List TypeMap a -> List TypeMap b
    forall (m :: * -> *) k a b.
    TrieMap m k =>
    (k -> a -> Maybe b) -> m a -> m b
    mapMaybeWithKeyTM
                                 (\[Type]
    ts a
    a -> Type -> a -> Maybe b
    f (RecordMap Ident Type -> Type
    TRec ([(Ident, Type)] -> RecordMap Ident Type
    forall a b. (Show a, Ord a) => [(a, b)] -> RecordMap a b
    recordFromFields ([Ident] -> [Type] -> [(Ident, Type)]
    forall a b. [a] -> [b] -> [(a, b)]
    zip [Ident]
    fs [Type]
    ts))) a
    a) List TypeMap a
    l) (TypeMap a -> Map [Ident] (List TypeMap a)
    forall a. TypeMap a -> Map [Ident] (List TypeMap a)
    trec TypeMap a
    m)
                                   -- NB: this step loses 'displayOrder' information.
                                   --  It's not clear if we should try to fix this.
           , tnewtype :: Map Newtype (List TypeMap b)
    tnewtype = (Newtype -> List TypeMap a -> List TypeMap b)
    -> Map Newtype (List TypeMap a) -> Map Newtype (List TypeMap b)
    forall (m :: * -> *) k a b.
    TrieMap m k =>
    (k -> a -> b) -> m a -> m b
    mapWithKeyTM (\Newtype
    nt List TypeMap a
    l -> ([Type] -> a -> Maybe b) -> List TypeMap a -> List TypeMap b
    forall a b.
    ([Type] -> a -> Maybe b) -> List TypeMap a -> List TypeMap b
    forall (m :: * -> *) k a b.
    TrieMap m k =>
    (k -> a -> Maybe b) -> m a -> m b
    mapMaybeWithKeyTM
                                     (\[Type]
    ts a
    a -> Type -> a -> Maybe b
    f (Newtype -> [Type] -> Type
    TNewtype Newtype
    nt [Type]
    ts) a
    a) List TypeMap a
    l) (TypeMap a -> Map Newtype (List TypeMap a)
    forall a. TypeMap a -> Map Newtype (List TypeMap a)
    tnewtype TypeMap a
    m)
           }

    updSub :: TrieMap m k => k -> (Maybe a -> Maybe a) -> Maybe (m a) -> Maybe (m a)
    updSub :: forall (m :: * -> *) k a.
    TrieMap m k =>
    k -> (Maybe a -> Maybe a) -> Maybe (m a) -> Maybe (m a)
    updSub k
    k Maybe a -> Maybe a
    f = m a -> Maybe (m a)
    forall a. a -> Maybe a
    Just (m a -> Maybe (m a))
    -> (Maybe (m a) -> m a) -> Maybe (m a) -> Maybe (m a)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . k -> (Maybe a -> Maybe a) -> m a -> m a
    forall a. k -> (Maybe a -> Maybe a) -> m a -> m a
    forall (m :: * -> *) k a.
    TrieMap m k =>
    k -> (Maybe a -> Maybe a) -> m a -> m a
    alterTM k
    k Maybe a -> Maybe a
    f (m a -> m a) -> (Maybe (m a) -> m a) -> Maybe (m a) -> m a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . m a -> Maybe (m a) -> m a
    forall a. a -> Maybe a -> a
    fromMaybe m a
    forall a. m a
    forall (m :: * -> *) k a. TrieMap m k => m a
    emptyTM

    instance Show a => Show (TypeMap a) where
      showsPrec :: Int -> TypeMap a -> ShowS
    showsPrec Int
    p TypeMap a
    xs = Int -> [(Type, a)] -> ShowS
    forall a. Show a => Int -> a -> ShowS
    showsPrec Int
    p (TypeMap a -> [(Type, a)]
    forall a. TypeMap a -> [(Type, a)]
    forall (m :: * -> *) k a. TrieMap m k => m a -> [(k, a)]
    toListTM TypeMap a
    xs)