-- derive Traversable, Functor, Foldable
{-# LANGUAGE DeriveTraversable #-}

module L3.Core.Expr where

import Data.Char (isDigit)
import Data.List (intercalate)

-- | An expression in the calculus of constructions.
data Expr a
  = Star
  | Box
  | Var a
  | Lam a (Expr a) (Expr a)
  | Pi a (Expr a) (Expr a)
  | App (Expr a) (Expr a)
  deriving (Expr a -> Expr a -> Bool
(Expr a -> Expr a -> Bool)
-> (Expr a -> Expr a -> Bool) -> Eq (Expr a)
forall a. Eq a => Expr a -> Expr a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: Expr a -> Expr a -> Bool
$c/= :: forall a. Eq a => Expr a -> Expr a -> Bool
== :: Expr a -> Expr a -> Bool
$c== :: forall a. Eq a => Expr a -> Expr a -> Bool
Eq, Functor Expr
Foldable Expr
Functor Expr
-> Foldable Expr
-> (forall (f :: * -> *) a b.
    Applicative f =>
    (a -> f b) -> Expr a -> f (Expr b))
-> (forall (f :: * -> *) a.
    Applicative f =>
    Expr (f a) -> f (Expr a))
-> (forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> Expr a -> m (Expr b))
-> (forall (m :: * -> *) a. Monad m => Expr (m a) -> m (Expr a))
-> Traversable Expr
(a -> f b) -> Expr a -> f (Expr 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 => Expr (m a) -> m (Expr a)
forall (f :: * -> *) a. Applicative f => Expr (f a) -> f (Expr a)
forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> Expr a -> m (Expr b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Expr a -> f (Expr b)
sequence :: Expr (m a) -> m (Expr a)
$csequence :: forall (m :: * -> *) a. Monad m => Expr (m a) -> m (Expr a)
mapM :: (a -> m b) -> Expr a -> m (Expr b)
$cmapM :: forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> Expr a -> m (Expr b)
sequenceA :: Expr (f a) -> f (Expr a)
$csequenceA :: forall (f :: * -> *) a. Applicative f => Expr (f a) -> f (Expr a)
traverse :: (a -> f b) -> Expr a -> f (Expr b)
$ctraverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Expr a -> f (Expr b)
$cp2Traversable :: Foldable Expr
$cp1Traversable :: Functor Expr
Traversable, a -> Expr b -> Expr a
(a -> b) -> Expr a -> Expr b
(forall a b. (a -> b) -> Expr a -> Expr b)
-> (forall a b. a -> Expr b -> Expr a) -> Functor Expr
forall a b. a -> Expr b -> Expr a
forall a b. (a -> b) -> Expr a -> Expr b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
<$ :: a -> Expr b -> Expr a
$c<$ :: forall a b. a -> Expr b -> Expr a
fmap :: (a -> b) -> Expr a -> Expr b
$cfmap :: forall a b. (a -> b) -> Expr a -> Expr b
Functor, Expr a -> Bool
(a -> m) -> Expr a -> m
(a -> b -> b) -> b -> Expr a -> b
(forall m. Monoid m => Expr m -> m)
-> (forall m a. Monoid m => (a -> m) -> Expr a -> m)
-> (forall m a. Monoid m => (a -> m) -> Expr a -> m)
-> (forall a b. (a -> b -> b) -> b -> Expr a -> b)
-> (forall a b. (a -> b -> b) -> b -> Expr a -> b)
-> (forall b a. (b -> a -> b) -> b -> Expr a -> b)
-> (forall b a. (b -> a -> b) -> b -> Expr a -> b)
-> (forall a. (a -> a -> a) -> Expr a -> a)
-> (forall a. (a -> a -> a) -> Expr a -> a)
-> (forall a. Expr a -> [a])
-> (forall a. Expr a -> Bool)
-> (forall a. Expr a -> Int)
-> (forall a. Eq a => a -> Expr a -> Bool)
-> (forall a. Ord a => Expr a -> a)
-> (forall a. Ord a => Expr a -> a)
-> (forall a. Num a => Expr a -> a)
-> (forall a. Num a => Expr a -> a)
-> Foldable Expr
forall a. Eq a => a -> Expr a -> Bool
forall a. Num a => Expr a -> a
forall a. Ord a => Expr a -> a
forall m. Monoid m => Expr m -> m
forall a. Expr a -> Bool
forall a. Expr a -> Int
forall a. Expr a -> [a]
forall a. (a -> a -> a) -> Expr a -> a
forall m a. Monoid m => (a -> m) -> Expr a -> m
forall b a. (b -> a -> b) -> b -> Expr a -> b
forall a b. (a -> b -> b) -> b -> Expr 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 :: Expr a -> a
$cproduct :: forall a. Num a => Expr a -> a
sum :: Expr a -> a
$csum :: forall a. Num a => Expr a -> a
minimum :: Expr a -> a
$cminimum :: forall a. Ord a => Expr a -> a
maximum :: Expr a -> a
$cmaximum :: forall a. Ord a => Expr a -> a
elem :: a -> Expr a -> Bool
$celem :: forall a. Eq a => a -> Expr a -> Bool
length :: Expr a -> Int
$clength :: forall a. Expr a -> Int
null :: Expr a -> Bool
$cnull :: forall a. Expr a -> Bool
toList :: Expr a -> [a]
$ctoList :: forall a. Expr a -> [a]
foldl1 :: (a -> a -> a) -> Expr a -> a
$cfoldl1 :: forall a. (a -> a -> a) -> Expr a -> a
foldr1 :: (a -> a -> a) -> Expr a -> a
$cfoldr1 :: forall a. (a -> a -> a) -> Expr a -> a
foldl' :: (b -> a -> b) -> b -> Expr a -> b
$cfoldl' :: forall b a. (b -> a -> b) -> b -> Expr a -> b
foldl :: (b -> a -> b) -> b -> Expr a -> b
$cfoldl :: forall b a. (b -> a -> b) -> b -> Expr a -> b
foldr' :: (a -> b -> b) -> b -> Expr a -> b
$cfoldr' :: forall a b. (a -> b -> b) -> b -> Expr a -> b
foldr :: (a -> b -> b) -> b -> Expr a -> b
$cfoldr :: forall a b. (a -> b -> b) -> b -> Expr a -> b
foldMap' :: (a -> m) -> Expr a -> m
$cfoldMap' :: forall m a. Monoid m => (a -> m) -> Expr a -> m
foldMap :: (a -> m) -> Expr a -> m
$cfoldMap :: forall m a. Monoid m => (a -> m) -> Expr a -> m
fold :: Expr m -> m
$cfold :: forall m. Monoid m => Expr m -> m
Foldable)

-- | A context is a stack, mapping names to bound values.
data Context a = Ctx [(a, Expr a)]