{-# LANGUAGE DeriveFoldable    #-}
{-# LANGUAGE DeriveFunctor     #-}
{-# LANGUAGE DeriveTraversable #-}
module Zinza.Expr (
    Expr (..),
    LExpr,
    abstract1,
    instantiate1ret,
    ) where

import Control.Monad (ap)
import Data.Maybe    (fromMaybe)

import Zinza.Pos
import Zinza.Var

-------------------------------------------------------------------------------
-- Node syntax
-------------------------------------------------------------------------------

-- | Expressions in templates.
--
-- Note: there are only eliminators; we cannot construct "bigger" expressions.
data Expr a
    = EVar (Located a)                -- ^ variable
    | EField (LExpr a) (Located Var)  -- ^ field accessor
    | EApp (LExpr a) (LExpr a)        -- ^ function application
  deriving (Int -> Expr a -> ShowS
[Expr a] -> ShowS
Expr a -> String
(Int -> Expr a -> ShowS)
-> (Expr a -> String) -> ([Expr a] -> ShowS) -> Show (Expr a)
forall a. Show a => Int -> Expr a -> ShowS
forall a. Show a => [Expr a] -> ShowS
forall a. Show a => Expr a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: forall a. Show a => Int -> Expr a -> ShowS
showsPrec :: Int -> Expr a -> ShowS
$cshow :: forall a. Show a => Expr a -> String
show :: Expr a -> String
$cshowList :: forall a. Show a => [Expr a] -> ShowS
showList :: [Expr a] -> ShowS
Show, (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
$cfmap :: forall a b. (a -> b) -> Expr a -> Expr b
fmap :: forall a b. (a -> b) -> Expr a -> Expr b
$c<$ :: forall a b. a -> Expr b -> Expr a
<$ :: forall a b. a -> Expr b -> Expr a
Functor, (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
$cfold :: forall m. Monoid m => Expr m -> m
fold :: forall m. Monoid m => Expr m -> m
$cfoldMap :: forall m a. Monoid m => (a -> m) -> Expr a -> m
foldMap :: forall m a. Monoid m => (a -> m) -> Expr a -> m
$cfoldMap' :: forall m a. Monoid m => (a -> m) -> Expr a -> m
foldMap' :: forall m a. Monoid m => (a -> m) -> Expr a -> m
$cfoldr :: forall a b. (a -> b -> b) -> b -> Expr a -> b
foldr :: forall a b. (a -> b -> b) -> b -> Expr a -> b
$cfoldr' :: forall a b. (a -> b -> b) -> b -> Expr a -> b
foldr' :: forall a b. (a -> b -> b) -> b -> Expr a -> b
$cfoldl :: forall b a. (b -> a -> b) -> b -> Expr a -> b
foldl :: forall b a. (b -> a -> b) -> b -> Expr a -> b
$cfoldl' :: forall b a. (b -> a -> b) -> b -> Expr a -> b
foldl' :: forall b a. (b -> a -> b) -> b -> Expr a -> b
$cfoldr1 :: forall a. (a -> a -> a) -> Expr a -> a
foldr1 :: forall a. (a -> a -> a) -> Expr a -> a
$cfoldl1 :: forall a. (a -> a -> a) -> Expr a -> a
foldl1 :: forall a. (a -> a -> a) -> Expr a -> a
$ctoList :: forall a. Expr a -> [a]
toList :: forall a. Expr a -> [a]
$cnull :: forall a. Expr a -> Bool
null :: forall a. Expr a -> Bool
$clength :: forall a. Expr a -> Int
length :: forall a. Expr a -> Int
$celem :: forall a. Eq a => a -> Expr a -> Bool
elem :: forall a. Eq a => a -> Expr a -> Bool
$cmaximum :: forall a. Ord a => Expr a -> a
maximum :: forall a. Ord a => Expr a -> a
$cminimum :: forall a. Ord a => Expr a -> a
minimum :: forall a. Ord a => Expr a -> a
$csum :: forall a. Num a => Expr a -> a
sum :: forall a. Num a => Expr a -> a
$cproduct :: forall a. Num a => Expr a -> a
product :: forall a. Num a => Expr a -> a
Foldable, 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
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)
$ctraverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Expr a -> f (Expr b)
traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Expr a -> f (Expr b)
$csequenceA :: forall (f :: * -> *) a. Applicative f => Expr (f a) -> f (Expr a)
sequenceA :: forall (f :: * -> *) a. Applicative f => Expr (f a) -> f (Expr a)
$cmapM :: forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> Expr a -> m (Expr b)
mapM :: forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> Expr a -> m (Expr b)
$csequence :: forall (m :: * -> *) a. Monad m => Expr (m a) -> m (Expr a)
sequence :: forall (m :: * -> *) a. Monad m => Expr (m a) -> m (Expr a)
Traversable)

-- | Located expression.
type LExpr a = Located (Expr a)

instance TraversableWithLoc Expr where
    traverseWithLoc :: forall (f :: * -> *) a b.
Applicative f =>
(Loc -> a -> f b) -> Expr a -> f (Expr b)
traverseWithLoc Loc -> a -> f b
f (EVar (L Loc
l a
x)) = Located b -> Expr b
forall a. Located a -> Expr a
EVar (Located b -> Expr b) -> (b -> Located b) -> b -> Expr b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Loc -> b -> Located b
forall a. Loc -> a -> Located a
L Loc
l
        (b -> Expr b) -> f b -> f (Expr b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Loc -> a -> f b
f Loc
l a
x
    traverseWithLoc Loc -> a -> f b
f (EField (L Loc
l Expr a
e) Located String
v) = (\Expr b
e' -> LExpr b -> Located String -> Expr b
forall a. LExpr a -> Located String -> Expr a
EField (Loc -> Expr b -> LExpr b
forall a. Loc -> a -> Located a
L Loc
l Expr b
e') Located String
v)
        (Expr b -> Expr b) -> f (Expr b) -> f (Expr b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (Loc -> a -> f b) -> Expr a -> f (Expr b)
forall (t :: * -> *) (f :: * -> *) a b.
(TraversableWithLoc t, Applicative f) =>
(Loc -> a -> f b) -> t a -> f (t b)
forall (f :: * -> *) a b.
Applicative f =>
(Loc -> a -> f b) -> Expr a -> f (Expr b)
traverseWithLoc Loc -> a -> f b
f Expr a
e
    traverseWithLoc Loc -> a -> f b
f (EApp (L Loc
lx Expr a
x) (L Loc
ly Expr a
y)) =
        (\Expr b
x' Expr b
y' -> LExpr b -> LExpr b -> Expr b
forall a. LExpr a -> LExpr a -> Expr a
EApp (Loc -> Expr b -> LExpr b
forall a. Loc -> a -> Located a
L Loc
lx Expr b
x') (Loc -> Expr b -> LExpr b
forall a. Loc -> a -> Located a
L Loc
ly Expr b
y'))
        (Expr b -> Expr b -> Expr b) -> f (Expr b) -> f (Expr b -> Expr b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (Loc -> a -> f b) -> Expr a -> f (Expr b)
forall (t :: * -> *) (f :: * -> *) a b.
(TraversableWithLoc t, Applicative f) =>
(Loc -> a -> f b) -> t a -> f (t b)
forall (f :: * -> *) a b.
Applicative f =>
(Loc -> a -> f b) -> Expr a -> f (Expr b)
traverseWithLoc Loc -> a -> f b
f Expr a
x
        f (Expr b -> Expr b) -> f (Expr b) -> f (Expr b)
forall a b. f (a -> b) -> f a -> f b
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> (Loc -> a -> f b) -> Expr a -> f (Expr b)
forall (t :: * -> *) (f :: * -> *) a b.
(TraversableWithLoc t, Applicative f) =>
(Loc -> a -> f b) -> t a -> f (t b)
forall (f :: * -> *) a b.
Applicative f =>
(Loc -> a -> f b) -> Expr a -> f (Expr b)
traverseWithLoc Loc -> a -> f b
f Expr a
y

-- | 'Monad' instance gives substitution.
instance Monad Expr where
    return :: forall a. a -> Expr a
return = Located a -> Expr a
forall a. Located a -> Expr a
EVar (Located a -> Expr a) -> (a -> Located a) -> a -> Expr a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Loc -> a -> Located a
forall a. Loc -> a -> Located a
L Loc
zeroLoc

    EVar (L Loc
_ a
x)           >>= :: forall a b. Expr a -> (a -> Expr b) -> Expr b
>>= a -> Expr b
k = a -> Expr b
k a
x
    EField (L Loc
l Expr a
expr) Located String
var  >>= a -> Expr b
k = LExpr b -> Located String -> Expr b
forall a. LExpr a -> Located String -> Expr a
EField (Loc -> Expr b -> LExpr b
forall a. Loc -> a -> Located a
L Loc
l (Expr a
expr Expr a -> (a -> Expr b) -> Expr b
forall a b. Expr a -> (a -> Expr b) -> Expr b
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= a -> Expr b
k)) Located String
var
    EApp (L Loc
lx Expr a
x) (L Loc
ly Expr a
y) >>= a -> Expr b
k = LExpr b -> LExpr b -> Expr b
forall a. LExpr a -> LExpr a -> Expr a
EApp (Loc -> Expr b -> LExpr b
forall a. Loc -> a -> Located a
L Loc
lx (Expr a
x Expr a -> (a -> Expr b) -> Expr b
forall a b. Expr a -> (a -> Expr b) -> Expr b
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= a -> Expr b
k)) (Loc -> Expr b -> LExpr b
forall a. Loc -> a -> Located a
L Loc
ly (Expr a
y Expr a -> (a -> Expr b) -> Expr b
forall a b. Expr a -> (a -> Expr b) -> Expr b
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= a -> Expr b
k))

instance Applicative Expr where
    pure :: forall a. a -> Expr a
pure = a -> Expr a
forall a. a -> Expr a
forall (m :: * -> *) a. Monad m => a -> m a
return
    <*> :: forall a b. Expr (a -> b) -> Expr a -> Expr b
(<*>) = Expr (a -> b) -> Expr a -> Expr b
forall (m :: * -> *) a b. Monad m => m (a -> b) -> m a -> m b
ap

-------------------------------------------------------------------------------
-- "bound"
-------------------------------------------------------------------------------

-- | Abstraction.
abstract1 :: (Functor f, Eq a) => a -> f a -> f (Maybe a)
abstract1 :: forall (f :: * -> *) a.
(Functor f, Eq a) =>
a -> f a -> f (Maybe a)
abstract1 a
x = (a -> Maybe a) -> f a -> f (Maybe a)
forall a b. (a -> b) -> f a -> f b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((a -> Maybe a) -> f a -> f (Maybe a))
-> (a -> Maybe a) -> f a -> f (Maybe a)
forall a b. (a -> b) -> a -> b
$ \a
y ->
    if a
x a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
y
    then Maybe a
forall a. Maybe a
Nothing
    else a -> Maybe a
forall a. a -> Maybe a
Just a
y

-- | Instantiate with a variable type
instantiate1ret :: Functor f => a -> f (Maybe a) -> f a
instantiate1ret :: forall (f :: * -> *) a. Functor f => a -> f (Maybe a) -> f a
instantiate1ret = (Maybe a -> a) -> f (Maybe a) -> f a
forall a b. (a -> b) -> f a -> f b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((Maybe a -> a) -> f (Maybe a) -> f a)
-> (a -> Maybe a -> a) -> a -> f (Maybe a) -> f a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Maybe a -> a
forall a. a -> Maybe a -> a
fromMaybe