{-# LANGUAGE DeriveFoldable    #-}
{-# LANGUAGE DeriveFunctor     #-}
{-# LANGUAGE DeriveTraversable #-}
{-# LANGUAGE CPP         #-}
#if __GLASGOW_HASKELL__ >=704
{-# LANGUAGE Safe        #-}
#elif __GLASGOW_HASKELL__ >=702
{-# LANGUAGE Trustworthy #-}
#endif
-- | Variables, de Bruijn indices and names.
module RERE.Var where

import Data.String (IsString (..))

#if !MIN_VERSION_base(4,8,0)
import Data.Foldable (Foldable)
import Data.Traversable (Traversable)
#endif

-- | 'Var' is essentially 'Maybe'.
data Var a
    = B    -- ^ bound
    | F a  -- ^ free variable.
  deriving (Var a -> Var a -> Bool
(Var a -> Var a -> Bool) -> (Var a -> Var a -> Bool) -> Eq (Var a)
forall a. Eq a => Var a -> Var a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: Var a -> Var a -> Bool
$c/= :: forall a. Eq a => Var a -> Var a -> Bool
== :: Var a -> Var a -> Bool
$c== :: forall a. Eq a => Var a -> Var a -> Bool
Eq, Eq (Var a)
Eq (Var a)
-> (Var a -> Var a -> Ordering)
-> (Var a -> Var a -> Bool)
-> (Var a -> Var a -> Bool)
-> (Var a -> Var a -> Bool)
-> (Var a -> Var a -> Bool)
-> (Var a -> Var a -> Var a)
-> (Var a -> Var a -> Var a)
-> Ord (Var a)
Var a -> Var a -> Bool
Var a -> Var a -> Ordering
Var a -> Var a -> Var a
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
forall a. Ord a => Eq (Var a)
forall a. Ord a => Var a -> Var a -> Bool
forall a. Ord a => Var a -> Var a -> Ordering
forall a. Ord a => Var a -> Var a -> Var a
min :: Var a -> Var a -> Var a
$cmin :: forall a. Ord a => Var a -> Var a -> Var a
max :: Var a -> Var a -> Var a
$cmax :: forall a. Ord a => Var a -> Var a -> Var a
>= :: Var a -> Var a -> Bool
$c>= :: forall a. Ord a => Var a -> Var a -> Bool
> :: Var a -> Var a -> Bool
$c> :: forall a. Ord a => Var a -> Var a -> Bool
<= :: Var a -> Var a -> Bool
$c<= :: forall a. Ord a => Var a -> Var a -> Bool
< :: Var a -> Var a -> Bool
$c< :: forall a. Ord a => Var a -> Var a -> Bool
compare :: Var a -> Var a -> Ordering
$ccompare :: forall a. Ord a => Var a -> Var a -> Ordering
$cp1Ord :: forall a. Ord a => Eq (Var a)
Ord, Int -> Var a -> ShowS
[Var a] -> ShowS
Var a -> String
(Int -> Var a -> ShowS)
-> (Var a -> String) -> ([Var a] -> ShowS) -> Show (Var a)
forall a. Show a => Int -> Var a -> ShowS
forall a. Show a => [Var a] -> ShowS
forall a. Show a => Var a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [Var a] -> ShowS
$cshowList :: forall a. Show a => [Var a] -> ShowS
show :: Var a -> String
$cshow :: forall a. Show a => Var a -> String
showsPrec :: Int -> Var a -> ShowS
$cshowsPrec :: forall a. Show a => Int -> Var a -> ShowS
Show, a -> Var b -> Var a
(a -> b) -> Var a -> Var b
(forall a b. (a -> b) -> Var a -> Var b)
-> (forall a b. a -> Var b -> Var a) -> Functor Var
forall a b. a -> Var b -> Var a
forall a b. (a -> b) -> Var a -> Var b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
<$ :: a -> Var b -> Var a
$c<$ :: forall a b. a -> Var b -> Var a
fmap :: (a -> b) -> Var a -> Var b
$cfmap :: forall a b. (a -> b) -> Var a -> Var b
Functor, Var a -> Bool
(a -> m) -> Var a -> m
(a -> b -> b) -> b -> Var a -> b
(forall m. Monoid m => Var m -> m)
-> (forall m a. Monoid m => (a -> m) -> Var a -> m)
-> (forall m a. Monoid m => (a -> m) -> Var a -> m)
-> (forall a b. (a -> b -> b) -> b -> Var a -> b)
-> (forall a b. (a -> b -> b) -> b -> Var a -> b)
-> (forall b a. (b -> a -> b) -> b -> Var a -> b)
-> (forall b a. (b -> a -> b) -> b -> Var a -> b)
-> (forall a. (a -> a -> a) -> Var a -> a)
-> (forall a. (a -> a -> a) -> Var a -> a)
-> (forall a. Var a -> [a])
-> (forall a. Var a -> Bool)
-> (forall a. Var a -> Int)
-> (forall a. Eq a => a -> Var a -> Bool)
-> (forall a. Ord a => Var a -> a)
-> (forall a. Ord a => Var a -> a)
-> (forall a. Num a => Var a -> a)
-> (forall a. Num a => Var a -> a)
-> Foldable Var
forall a. Eq a => a -> Var a -> Bool
forall a. Num a => Var a -> a
forall a. Ord a => Var a -> a
forall m. Monoid m => Var m -> m
forall a. Var a -> Bool
forall a. Var a -> Int
forall a. Var a -> [a]
forall a. (a -> a -> a) -> Var a -> a
forall m a. Monoid m => (a -> m) -> Var a -> m
forall b a. (b -> a -> b) -> b -> Var a -> b
forall a b. (a -> b -> b) -> b -> Var 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
product :: Var a -> a
$cproduct :: forall a. Num a => Var a -> a
sum :: Var a -> a
$csum :: forall a. Num a => Var a -> a
minimum :: Var a -> a
$cminimum :: forall a. Ord a => Var a -> a
maximum :: Var a -> a
$cmaximum :: forall a. Ord a => Var a -> a
elem :: a -> Var a -> Bool
$celem :: forall a. Eq a => a -> Var a -> Bool
length :: Var a -> Int
$clength :: forall a. Var a -> Int
null :: Var a -> Bool
$cnull :: forall a. Var a -> Bool
toList :: Var a -> [a]
$ctoList :: forall a. Var a -> [a]
foldl1 :: (a -> a -> a) -> Var a -> a
$cfoldl1 :: forall a. (a -> a -> a) -> Var a -> a
foldr1 :: (a -> a -> a) -> Var a -> a
$cfoldr1 :: forall a. (a -> a -> a) -> Var a -> a
foldl' :: (b -> a -> b) -> b -> Var a -> b
$cfoldl' :: forall b a. (b -> a -> b) -> b -> Var a -> b
foldl :: (b -> a -> b) -> b -> Var a -> b
$cfoldl :: forall b a. (b -> a -> b) -> b -> Var a -> b
foldr' :: (a -> b -> b) -> b -> Var a -> b
$cfoldr' :: forall a b. (a -> b -> b) -> b -> Var a -> b
foldr :: (a -> b -> b) -> b -> Var a -> b
$cfoldr :: forall a b. (a -> b -> b) -> b -> Var a -> b
foldMap' :: (a -> m) -> Var a -> m
$cfoldMap' :: forall m a. Monoid m => (a -> m) -> Var a -> m
foldMap :: (a -> m) -> Var a -> m
$cfoldMap :: forall m a. Monoid m => (a -> m) -> Var a -> m
fold :: Var m -> m
$cfold :: forall m. Monoid m => Var m -> m
Foldable, Functor Var
Foldable Var
Functor Var
-> Foldable Var
-> (forall (f :: * -> *) a b.
    Applicative f =>
    (a -> f b) -> Var a -> f (Var b))
-> (forall (f :: * -> *) a.
    Applicative f =>
    Var (f a) -> f (Var a))
-> (forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> Var a -> m (Var b))
-> (forall (m :: * -> *) a. Monad m => Var (m a) -> m (Var a))
-> Traversable Var
(a -> f b) -> Var a -> f (Var b)
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 => Var (m a) -> m (Var a)
forall (f :: * -> *) a. Applicative f => Var (f a) -> f (Var a)
forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> Var a -> m (Var b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Var a -> f (Var b)
sequence :: Var (m a) -> m (Var a)
$csequence :: forall (m :: * -> *) a. Monad m => Var (m a) -> m (Var a)
mapM :: (a -> m b) -> Var a -> m (Var b)
$cmapM :: forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> Var a -> m (Var b)
sequenceA :: Var (f a) -> f (Var a)
$csequenceA :: forall (f :: * -> *) a. Applicative f => Var (f a) -> f (Var a)
traverse :: (a -> f b) -> Var a -> f (Var b)
$ctraverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Var a -> f (Var b)
$cp2Traversable :: Foldable Var
$cp1Traversable :: Functor Var
Traversable)

-- | Analogue of 'maybe' for 'Var'.
unvar :: r -> (a -> r) -> Var a -> r
unvar :: r -> (a -> r) -> Var a -> r
unvar r
n a -> r
_ Var a
B     = r
n
unvar r
_ a -> r
j (F a
x) = a -> r
j a
x

-- | Swap variables.
swapVar :: Var (Var a) -> Var (Var a)
swapVar :: Var (Var a) -> Var (Var a)
swapVar (F (F a
a)) = Var a -> Var (Var a)
forall a. a -> Var a
F (a -> Var a
forall a. a -> Var a
F a
a)
swapVar (F Var a
B)     = Var (Var a)
forall a. Var a
B
swapVar Var (Var a)
B         = Var a -> Var (Var a)
forall a. a -> Var a
F Var a
forall a. Var a
B

instance IsString a => IsString (Var a) where fromString :: String -> Var a
fromString = a -> Var a
forall a. a -> Var a
F (a -> Var a) -> (String -> a) -> String -> Var a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. String -> a
forall a. IsString a => String -> a
fromString

-- | Names carry information used in pretty-printing,
-- but otherwise they all 'compare' 'EQ'ual.
data Name = N String [Char]

instance Show Name where
    showsPrec :: Int -> Name -> ShowS
showsPrec Int
d (N String
n String
sfx)
        | String -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null String
sfx = Int -> String -> ShowS
forall a. Show a => Int -> a -> ShowS
showsPrec Int
d String
n
        | Bool
otherwise
        = Bool -> ShowS -> ShowS
showParen (Int
d Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
10)
        (ShowS -> ShowS) -> ShowS -> ShowS
forall a b. (a -> b) -> a -> b
$ String -> ShowS
showString String
"N "
        ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> String -> ShowS
forall a. Show a => Int -> a -> ShowS
showsPrec Int
11 String
n
        ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Char -> ShowS
showChar Char
' '
        ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> String -> ShowS
forall a. Show a => Int -> a -> ShowS
showsPrec Int
11 String
sfx

instance Eq Name where Name
_ == :: Name -> Name -> Bool
== Name
_ = Bool
True
instance Ord Name where compare :: Name -> Name -> Ordering
compare Name
_ Name
_ = Ordering
EQ
instance IsString Name where fromString :: String -> Name
fromString String
n = String -> String -> Name
N String
n []

-- | Make a name for derivative binding (adds subindex).
derivativeName :: Char -> Name -> Name
derivativeName :: Char -> Name -> Name
derivativeName Char
c (N String
n String
cs) = String -> String -> Name
N String
n (String
cs String -> ShowS
forall a. [a] -> [a] -> [a]
++ [Char
c])