{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE DefaultSignatures #-}
{-# LANGUAGE DeriveAnyClass #-}
{-# LANGUAGE DeriveFunctor #-}
{-# LANGUAGE DeriveGeneric #-}
{-# LANGUAGE DerivingStrategies #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE GADTs #-}
{-# LANGUAGE GeneralizedNewtypeDeriving #-}
{-# LANGUAGE KindSignatures #-}
{-# LANGUAGE NamedFieldPuns #-}
{-# LANGUAGE RankNTypes #-}
{-# LANGUAGE RecordWildCards #-}
{-# LANGUAGE StandaloneDeriving #-}
{-# LANGUAGE TupleSections #-}
{-# LANGUAGE TypeFamilyDependencies #-}
{-# LANGUAGE TypeOperators #-}
{-# LANGUAGE UndecidableInstances #-}
{-# OPTIONS_GHC -Wno-redundant-constraints #-}
module Kanren.Core (
Logical (..),
VarId,
Term (..),
Atomic (..),
unify',
walk',
occursCheck',
inject',
extract',
Normalizable (..),
normalize',
runNormalize,
Disequalities,
disequality,
State,
disequalities,
empty,
makeVariable,
makeVariables,
freshVarId,
) where
import Control.DeepSeq
import Control.Monad (ap)
import Data.Coerce (coerce)
import Data.Foldable (foldrM)
import Data.IntMap.Strict (IntMap)
import qualified Data.IntMap.Strict as IntMap
import Data.List (intercalate)
import Data.Maybe (fromMaybe)
import GHC.Exts (IsList (..))
import GHC.Generics (Generic)
import StrictList (StrictList (Cons, Nil), mapReversed, toListReversed)
import Unsafe.Coerce (unsafeCoerce)
class Logical a where
type Logic a = r | r -> a
type Logic a = a
unify :: Logic a -> Logic a -> State -> Maybe State
default unify :: (Eq (Logic a)) => Logic a -> Logic a -> State -> Maybe State
unify Logic a
x Logic a
y State
state
| Logic a
x Logic a -> Logic a -> Bool
forall a. Eq a => a -> a -> Bool
== Logic a
y = State -> Maybe State
forall a. a -> Maybe a
Just State
state
| Bool
otherwise = Maybe State
forall a. Maybe a
Nothing
walk :: State -> Logic a -> Logic a
default walk :: (a ~ Logic a) => State -> Logic a -> Logic a
walk State
_ = a -> a
Logic a -> Logic a
forall a. a -> a
id
occursCheck :: VarId b -> Logic a -> State -> Bool
default occursCheck :: (a ~ Logic a) => VarId b -> Logic a -> State -> Bool
occursCheck VarId b
_ Logic a
_ State
_ = Bool
False
inject :: a -> Logic a
default inject :: (a ~ Logic a) => a -> Logic a
inject = a -> a
a -> Logic a
forall a. a -> a
id
:: Logic a -> Maybe a
default :: (a ~ Logic a) => Logic a -> Maybe a
extract = a -> Maybe a
Logic a -> Maybe a
forall a. a -> Maybe a
Just
newtype VarId a = VarId Int
deriving newtype (VarId a -> VarId a -> Bool
(VarId a -> VarId a -> Bool)
-> (VarId a -> VarId a -> Bool) -> Eq (VarId a)
forall a. VarId a -> VarId a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: forall a. VarId a -> VarId a -> Bool
== :: VarId a -> VarId a -> Bool
$c/= :: forall a. VarId a -> VarId a -> Bool
/= :: VarId a -> VarId a -> Bool
Eq, VarId a -> ()
(VarId a -> ()) -> NFData (VarId a)
forall a. VarId a -> ()
forall a. (a -> ()) -> NFData a
$crnf :: forall a. VarId a -> ()
rnf :: VarId a -> ()
NFData)
instance Show (VarId a) where
show :: VarId a -> String
show (VarId Int
varId) = String
"_." String -> ShowS
forall a. [a] -> [a] -> [a]
++ Int -> String
forall a. Show a => a -> String
show Int
varId
data Term a
= Var !(VarId a)
| Value !(Logic a)
deriving ((forall x. Term a -> Rep (Term a) x)
-> (forall x. Rep (Term a) x -> Term a) -> Generic (Term a)
forall x. Rep (Term a) x -> Term a
forall x. Term a -> Rep (Term a) x
forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
forall a x. Rep (Term a) x -> Term a
forall a x. Term a -> Rep (Term a) x
$cfrom :: forall a x. Term a -> Rep (Term a) x
from :: forall x. Term a -> Rep (Term a) x
$cto :: forall a x. Rep (Term a) x -> Term a
to :: forall x. Rep (Term a) x -> Term a
Generic)
deriving instance (NFData (Logic a)) => NFData (Term a)
deriving instance (Eq (Logic a)) => Eq (Term a)
instance (Show (Logic a)) => Show (Term a) where
showsPrec :: Int -> Term a -> ShowS
showsPrec Int
d (Var VarId a
var) = Int -> VarId a -> ShowS
forall a. Show a => Int -> a -> ShowS
showsPrec Int
d VarId a
var
showsPrec Int
d (Value Logic a
value) = Int -> Logic a -> ShowS
forall a. Show a => Int -> a -> ShowS
showsPrec Int
d Logic a
value
instance (IsList (Logic a)) => IsList (Term a) where
type Item (Term a) = Item (Logic a)
fromList :: [Item (Term a)] -> Term a
fromList = Logic a -> Term a
forall a. Logic a -> Term a
Value (Logic a -> Term a)
-> ([Item (Logic a)] -> Logic a) -> [Item (Logic a)] -> Term a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Item (Logic a)] -> Logic a
forall l. IsList l => [Item l] -> l
fromList
toList :: Term a -> [Item (Term a)]
toList (Value Logic a
xs) = Logic a -> [Item (Logic a)]
forall l. IsList l => l -> [Item l]
toList Logic a
xs
toList (Var VarId a
x) = String -> [Item (Logic a)]
forall a. HasCallStack => String -> a
error (String
"cannot convert unification variable " String -> ShowS
forall a. Semigroup a => a -> a -> a
<> VarId a -> String
forall a. Show a => a -> String
show VarId a
x String -> ShowS
forall a. Semigroup a => a -> a -> a
<> String
" to list")
instance (Num (Logic a)) => Num (Term a) where
fromInteger :: Integer -> Term a
fromInteger = Logic a -> Term a
forall a. Logic a -> Term a
Value (Logic a -> Term a) -> (Integer -> Logic a) -> Integer -> Term a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Integer -> Logic a
forall a. Num a => Integer -> a
fromInteger
+ :: Term a -> Term a -> Term a
(+) = String
-> (Logic a -> Logic a -> Logic a) -> Term a -> Term a -> Term a
forall a b c.
String
-> (Logic a -> Logic b -> Logic c) -> Term a -> Term b -> Term c
unsafePromoteBinOp String
"(+)" Logic a -> Logic a -> Logic a
forall a. Num a => a -> a -> a
(+)
(-) = String
-> (Logic a -> Logic a -> Logic a) -> Term a -> Term a -> Term a
forall a b c.
String
-> (Logic a -> Logic b -> Logic c) -> Term a -> Term b -> Term c
unsafePromoteBinOp String
"(-)" (-)
* :: Term a -> Term a -> Term a
(*) = String
-> (Logic a -> Logic a -> Logic a) -> Term a -> Term a -> Term a
forall a b c.
String
-> (Logic a -> Logic b -> Logic c) -> Term a -> Term b -> Term c
unsafePromoteBinOp String
"(*)" Logic a -> Logic a -> Logic a
forall a. Num a => a -> a -> a
(*)
abs :: Term a -> Term a
abs = String -> (Logic a -> Logic a) -> Term a -> Term a
forall a b. String -> (Logic a -> Logic b) -> Term a -> Term b
unsafePromoteUnaryOp String
"abs" Logic a -> Logic a
forall a. Num a => a -> a
abs
signum :: Term a -> Term a
signum = String -> (Logic a -> Logic a) -> Term a -> Term a
forall a b. String -> (Logic a -> Logic b) -> Term a -> Term b
unsafePromoteUnaryOp String
"signum" Logic a -> Logic a
forall a. Num a => a -> a
signum
negate :: Term a -> Term a
negate = String -> (Logic a -> Logic a) -> Term a -> Term a
forall a b. String -> (Logic a -> Logic b) -> Term a -> Term b
unsafePromoteUnaryOp String
"negate" Logic a -> Logic a
forall a. Num a => a -> a
negate
unsafePromoteUnaryOp :: String -> (Logic a -> Logic b) -> Term a -> Term b
unsafePromoteUnaryOp :: forall a b. String -> (Logic a -> Logic b) -> Term a -> Term b
unsafePromoteUnaryOp String
_name Logic a -> Logic b
f (Value Logic a
x) = Logic b -> Term b
forall a. Logic a -> Term a
Value (Logic a -> Logic b
f Logic a
x)
unsafePromoteUnaryOp String
name Logic a -> Logic b
_f (Var VarId a
x) = String -> Term b
forall a. HasCallStack => String -> a
error (String
"cannot apply " String -> ShowS
forall a. Semigroup a => a -> a -> a
<> String
name String -> ShowS
forall a. Semigroup a => a -> a -> a
<> String
" to the unification variable " String -> ShowS
forall a. Semigroup a => a -> a -> a
<> VarId a -> String
forall a. Show a => a -> String
show VarId a
x)
unsafePromoteBinOp :: String -> (Logic a -> Logic b -> Logic c) -> Term a -> Term b -> Term c
unsafePromoteBinOp :: forall a b c.
String
-> (Logic a -> Logic b -> Logic c) -> Term a -> Term b -> Term c
unsafePromoteBinOp String
_name Logic a -> Logic b -> Logic c
f (Value Logic a
x) (Value Logic b
y) = Logic c -> Term c
forall a. Logic a -> Term a
Value (Logic a -> Logic b -> Logic c
f Logic a
x Logic b
y)
unsafePromoteBinOp String
name Logic a -> Logic b -> Logic c
_f (Var VarId a
x) Term b
_ = String -> Term c
forall a. HasCallStack => String -> a
error (String
"cannot apply " String -> ShowS
forall a. Semigroup a => a -> a -> a
<> String
name String -> ShowS
forall a. Semigroup a => a -> a -> a
<> String
" to the unification variable " String -> ShowS
forall a. Semigroup a => a -> a -> a
<> VarId a -> String
forall a. Show a => a -> String
show VarId a
x)
unsafePromoteBinOp String
name Logic a -> Logic b -> Logic c
_f Term a
_ (Var VarId b
x) = String -> Term c
forall a. HasCallStack => String -> a
error (String
"cannot apply " String -> ShowS
forall a. Semigroup a => a -> a -> a
<> String
name String -> ShowS
forall a. Semigroup a => a -> a -> a
<> String
" to the unification variable " String -> ShowS
forall a. Semigroup a => a -> a -> a
<> VarId b -> String
forall a. Show a => a -> String
show VarId b
x)
newtype Atomic a = Atomic a
deriving newtype (Atomic a -> Atomic a -> Bool
(Atomic a -> Atomic a -> Bool)
-> (Atomic a -> Atomic a -> Bool) -> Eq (Atomic a)
forall a. Eq a => Atomic a -> Atomic a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: forall a. Eq a => Atomic a -> Atomic a -> Bool
== :: Atomic a -> Atomic a -> Bool
$c/= :: forall a. Eq a => Atomic a -> Atomic a -> Bool
/= :: Atomic a -> Atomic a -> Bool
Eq, Atomic a -> ()
(Atomic a -> ()) -> NFData (Atomic a)
forall a. NFData a => Atomic a -> ()
forall a. (a -> ()) -> NFData a
$crnf :: forall a. NFData a => Atomic a -> ()
rnf :: Atomic a -> ()
NFData)
instance (Eq a) => Logical (Atomic a)
instance (Show a) => Show (Atomic a) where
show :: Atomic a -> String
show (Atomic a
x) = a -> String
forall a. Show a => a -> String
show a
x
instance (Eq a) => Normalizable (Atomic a)
unify' :: (Logical a) => Term a -> Term a -> State -> Maybe State
unify' :: forall a. Logical a => Term a -> Term a -> State -> Maybe State
unify' Term a
l Term a
r State
state =
case (State -> Term a -> Term a
forall a. Logical a => State -> Term a -> Term a
shallowWalk State
state Term a
l, State -> Term a -> Term a
forall a. Logical a => State -> Term a -> Term a
shallowWalk State
state Term a
r) of
(Var VarId a
x, Var VarId a
y)
| VarId a
x VarId a -> VarId a -> Bool
forall a. Eq a => a -> a -> Bool
== VarId a
y -> State -> Maybe State
forall a. a -> Maybe a
Just State
state
(Var VarId a
x, Term a
r')
| VarId a -> Term a -> State -> Bool
forall a b. Logical a => VarId b -> Term a -> State -> Bool
occursCheck' VarId a
x Term a
r' State
state -> Maybe State
forall a. Maybe a
Nothing
| Bool
otherwise -> VarId a -> Term a -> State -> Maybe State
forall a. Logical a => VarId a -> Term a -> State -> Maybe State
addSubst VarId a
x Term a
r' State
state
(Term a
l', Var VarId a
y)
| VarId a -> Term a -> State -> Bool
forall a b. Logical a => VarId b -> Term a -> State -> Bool
occursCheck' VarId a
y Term a
l' State
state -> Maybe State
forall a. Maybe a
Nothing
| Bool
otherwise -> VarId a -> Term a -> State -> Maybe State
forall a. Logical a => VarId a -> Term a -> State -> Maybe State
addSubst VarId a
y Term a
l' State
state
(Value Logic a
l', Value Logic a
r') -> Logic a -> Logic a -> State -> Maybe State
forall a. Logical a => Logic a -> Logic a -> State -> Maybe State
unify Logic a
l' Logic a
r' State
state
occursCheck' :: (Logical a) => VarId b -> Term a -> State -> Bool
occursCheck' :: forall a b. Logical a => VarId b -> Term a -> State -> Bool
occursCheck' VarId b
x Term a
t State
state =
case State -> Term a -> Term a
forall a. Logical a => State -> Term a -> Term a
shallowWalk State
state Term a
t of
Var VarId a
y -> VarId b -> VarId a
forall a b. Coercible a b => a -> b
coerce VarId b
x VarId a -> VarId a -> Bool
forall a. Eq a => a -> a -> Bool
== VarId a
y
Value Logic a
v -> VarId b -> Logic a -> State -> Bool
forall b. VarId b -> Logic a -> State -> Bool
forall a b. Logical a => VarId b -> Logic a -> State -> Bool
occursCheck VarId b
x Logic a
v State
state
walk' :: (Logical a) => State -> Term a -> Term a
walk' :: forall a. Logical a => State -> Term a -> Term a
walk' State
state Term a
x = case State -> Term a -> Term a
forall a. Logical a => State -> Term a -> Term a
shallowWalk State
state Term a
x of
t :: Term a
t@Var{} -> Term a
t
Value Logic a
v -> Logic a -> Term a
forall a. Logic a -> Term a
Value (State -> Logic a -> Logic a
forall a. Logical a => State -> Logic a -> Logic a
walk State
state Logic a
v)
inject' :: (Logical a) => a -> Term a
inject' :: forall a. Logical a => a -> Term a
inject' = Logic a -> Term a
forall a. Logic a -> Term a
Value (Logic a -> Term a) -> (a -> Logic a) -> a -> Term a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Logic a
forall a. Logical a => a -> Logic a
inject
extract' :: (Logical a) => Term a -> Maybe a
Var{} = Maybe a
forall a. Maybe a
Nothing
extract' (Value Logic a
x) = Logic a -> Maybe a
forall a. Logical a => Logic a -> Maybe a
extract Logic a
x
data Normalization = Normalization (IntMap Int) Int
newtype Normalizer a = Normalizer (Normalization -> (Normalization, a)) deriving ((forall a b. (a -> b) -> Normalizer a -> Normalizer b)
-> (forall a b. a -> Normalizer b -> Normalizer a)
-> Functor Normalizer
forall a b. a -> Normalizer b -> Normalizer a
forall a b. (a -> b) -> Normalizer a -> Normalizer 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) -> Normalizer a -> Normalizer b
fmap :: forall a b. (a -> b) -> Normalizer a -> Normalizer b
$c<$ :: forall a b. a -> Normalizer b -> Normalizer a
<$ :: forall a b. a -> Normalizer b -> Normalizer a
Functor)
instance Applicative Normalizer where
pure :: forall a. a -> Normalizer a
pure a
x = (Normalization -> (Normalization, a)) -> Normalizer a
forall a. (Normalization -> (Normalization, a)) -> Normalizer a
Normalizer (,a
x)
<*> :: forall a b. Normalizer (a -> b) -> Normalizer a -> Normalizer b
(<*>) = Normalizer (a -> b) -> Normalizer a -> Normalizer b
forall (m :: * -> *) a b. Monad m => m (a -> b) -> m a -> m b
ap
instance Monad Normalizer where
return :: forall a. a -> Normalizer a
return = a -> Normalizer a
forall a. a -> Normalizer a
forall (f :: * -> *) a. Applicative f => a -> f a
pure
Normalizer Normalization -> (Normalization, a)
f >>= :: forall a b. Normalizer a -> (a -> Normalizer b) -> Normalizer b
>>= a -> Normalizer b
g = (Normalization -> (Normalization, b)) -> Normalizer b
forall a. (Normalization -> (Normalization, a)) -> Normalizer a
Normalizer ((Normalization -> (Normalization, b)) -> Normalizer b)
-> (Normalization -> (Normalization, b)) -> Normalizer b
forall a b. (a -> b) -> a -> b
$ \Normalization
state ->
let (Normalization
state', a
x) = Normalization -> (Normalization, a)
f Normalization
state
Normalizer Normalization -> (Normalization, b)
h = a -> Normalizer b
g a
x
in Normalization -> (Normalization, b)
h Normalization
state'
class (Logical a) => Normalizable a where
normalize :: (forall i. VarId i -> Normalizer (VarId i)) -> Logic a -> Normalizer (Logic a)
default normalize :: (a ~ Logic a) => (forall i. VarId i -> Normalizer (VarId i)) -> Logic a -> Normalizer (Logic a)
normalize forall i. VarId i -> Normalizer (VarId i)
_ = a -> Normalizer a
Logic a -> Normalizer (Logic a)
forall a. a -> Normalizer a
forall (f :: * -> *) a. Applicative f => a -> f a
pure
normalize' :: (Normalizable a) => (forall i. VarId i -> Normalizer (VarId i)) -> Term a -> Normalizer (Term a)
normalize' :: forall a.
Normalizable a =>
(forall i. VarId i -> Normalizer (VarId i))
-> Term a -> Normalizer (Term a)
normalize' forall i. VarId i -> Normalizer (VarId i)
f (Var VarId a
varId) = VarId a -> Term a
forall a. VarId a -> Term a
Var (VarId a -> Term a) -> Normalizer (VarId a) -> Normalizer (Term a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> VarId a -> Normalizer (VarId a)
forall i. VarId i -> Normalizer (VarId i)
f VarId a
varId
normalize' forall i. VarId i -> Normalizer (VarId i)
f (Value Logic a
x) = Logic a -> Term a
forall a. Logic a -> Term a
Value (Logic a -> Term a) -> Normalizer (Logic a) -> Normalizer (Term a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (forall i. VarId i -> Normalizer (VarId i))
-> Logic a -> Normalizer (Logic a)
forall a.
Normalizable a =>
(forall i. VarId i -> Normalizer (VarId i))
-> Logic a -> Normalizer (Logic a)
normalize VarId i -> Normalizer (VarId i)
forall i. VarId i -> Normalizer (VarId i)
f Logic a
x
runNormalize :: (Normalizable a) => Term a -> Term a
runNormalize :: forall a. Normalizable a => Term a -> Term a
runNormalize Term a
x = Term a
normalized
where
Normalizer Normalization -> (Normalization, Term a)
g = (forall i. VarId i -> Normalizer (VarId i))
-> Term a -> Normalizer (Term a)
forall a.
Normalizable a =>
(forall i. VarId i -> Normalizer (VarId i))
-> Term a -> Normalizer (Term a)
normalize' VarId i -> Normalizer (VarId i)
forall i. VarId i -> Normalizer (VarId i)
forall {a} {a}. VarId a -> Normalizer (VarId a)
addVar Term a
x
(Normalization
_, Term a
normalized) = Normalization -> (Normalization, Term a)
g (IntMap Int -> Int -> Normalization
Normalization IntMap Int
forall a. IntMap a
IntMap.empty Int
0)
addVar :: VarId a -> Normalizer (VarId a)
addVar (VarId Int
varId) = (Normalization -> (Normalization, VarId a)) -> Normalizer (VarId a)
forall a. (Normalization -> (Normalization, a)) -> Normalizer a
Normalizer ((Normalization -> (Normalization, VarId a))
-> Normalizer (VarId a))
-> (Normalization -> (Normalization, VarId a))
-> Normalizer (VarId a)
forall a b. (a -> b) -> a -> b
$ \n :: Normalization
n@(Normalization IntMap Int
vars Int
maxId) ->
case Int -> IntMap Int -> Maybe Int
forall a. Int -> IntMap a -> Maybe a
IntMap.lookup Int
varId IntMap Int
vars of
Just Int
varId' -> (Normalization
n, Int -> VarId a
forall a. Int -> VarId a
VarId Int
varId')
Maybe Int
Nothing -> (IntMap Int -> Int -> Normalization
Normalization IntMap Int
vars' Int
maxId', Int -> VarId a
forall a. Int -> VarId a
VarId Int
maxId)
where
maxId' :: Int
maxId' = Int
maxId Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1
vars' :: IntMap Int
vars' = Int -> Int -> IntMap Int -> IntMap Int
forall a. Int -> a -> IntMap a -> IntMap a
IntMap.insert Int
varId Int
maxId IntMap Int
vars
disequality :: (Logical a) => Term a -> Term a -> State -> Maybe State
disequality :: forall a. Logical a => Term a -> Term a -> State -> Maybe State
disequality Term a
left Term a
right State
state = case Term a -> Term a -> State -> Maybe Subst
forall a. Logical a => Term a -> Term a -> State -> Maybe Subst
addedSubst Term a
left Term a
right State
state of
Maybe Subst
Nothing -> State -> Maybe State
forall a. a -> Maybe a
Just State
state
Just Subst
added -> Subst -> State -> Maybe State
stateInsertDisequality Subst
added State
state
data ErasedTerm where
ErasedTerm :: (Logical a) => Term a -> ErasedTerm
instance Show ErasedTerm where
show :: ErasedTerm -> String
show (ErasedTerm (Var VarId a
varId)) = VarId a -> String
forall a. Show a => a -> String
show VarId a
varId
show (ErasedTerm (Value Logic a
_)) = String
"<term of erased type>"
unsafeReconstructTerm :: ErasedTerm -> Term a
unsafeReconstructTerm :: forall a. ErasedTerm -> Term a
unsafeReconstructTerm (ErasedTerm Term a
x) = Term a -> Term a
forall a b. a -> b
unsafeCoerce Term a
x
newtype Subst = Subst (IntMap ErasedTerm) deriving (Int -> Subst -> ShowS
[Subst] -> ShowS
Subst -> String
(Int -> Subst -> ShowS)
-> (Subst -> String) -> ([Subst] -> ShowS) -> Show Subst
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: Int -> Subst -> ShowS
showsPrec :: Int -> Subst -> ShowS
$cshow :: Subst -> String
show :: Subst -> String
$cshowList :: [Subst] -> ShowS
showList :: [Subst] -> ShowS
Show)
substEmpty :: Subst
substEmpty :: Subst
substEmpty = IntMap ErasedTerm -> Subst
Subst IntMap ErasedTerm
forall a. IntMap a
IntMap.empty
substNull :: Subst -> Bool
substNull :: Subst -> Bool
substNull (Subst IntMap ErasedTerm
m) = IntMap ErasedTerm -> Bool
forall a. IntMap a -> Bool
IntMap.null IntMap ErasedTerm
m
substLookupArbitraryId :: Subst -> Maybe Int
substLookupArbitraryId :: Subst -> Maybe Int
substLookupArbitraryId (Subst IntMap ErasedTerm
m) = (Int, ErasedTerm) -> Int
forall a b. (a, b) -> a
fst ((Int, ErasedTerm) -> Int) -> Maybe (Int, ErasedTerm) -> Maybe Int
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> IntMap ErasedTerm -> Maybe (Int, ErasedTerm)
forall a. IntMap a -> Maybe (Int, a)
IntMap.lookupMin IntMap ErasedTerm
m
substExtractArbitrary :: Subst -> Maybe ((Int, ErasedTerm), Subst)
(Subst IntMap ErasedTerm
m) = (IntMap ErasedTerm -> Subst)
-> ((Int, ErasedTerm), IntMap ErasedTerm)
-> ((Int, ErasedTerm), Subst)
forall a b.
(a -> b) -> ((Int, ErasedTerm), a) -> ((Int, ErasedTerm), b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap IntMap ErasedTerm -> Subst
Subst (((Int, ErasedTerm), IntMap ErasedTerm)
-> ((Int, ErasedTerm), Subst))
-> Maybe ((Int, ErasedTerm), IntMap ErasedTerm)
-> Maybe ((Int, ErasedTerm), Subst)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> IntMap ErasedTerm -> Maybe ((Int, ErasedTerm), IntMap ErasedTerm)
forall a. IntMap a -> Maybe ((Int, a), IntMap a)
IntMap.minViewWithKey IntMap ErasedTerm
m
addedSubst :: (Logical a) => Term a -> Term a -> State -> Maybe Subst
addedSubst :: forall a. Logical a => Term a -> Term a -> State -> Maybe Subst
addedSubst Term a
left Term a
right State
state = State -> Subst
knownSubst (State -> Subst) -> Maybe State -> Maybe Subst
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Term a -> Term a -> State -> Maybe State
forall a. Logical a => Term a -> Term a -> State -> Maybe State
unify' Term a
left' Term a
right' State
empty
where
left' :: Term a
left' = State -> Term a -> Term a
forall a. Logical a => State -> Term a -> Term a
walk' State
state Term a
left
right' :: Term a
right' = State -> Term a -> Term a
forall a. Logical a => State -> Term a -> Term a
walk' State
state Term a
right
instance Semigroup Subst where
Subst IntMap ErasedTerm
l <> :: Subst -> Subst -> Subst
<> Subst IntMap ErasedTerm
r = IntMap ErasedTerm -> Subst
Subst (IntMap ErasedTerm
l IntMap ErasedTerm -> IntMap ErasedTerm -> IntMap ErasedTerm
forall a. Semigroup a => a -> a -> a
<> IntMap ErasedTerm
r)
newtype Disequalities = Disequalities (IntMap (StrictList (DisequalityHead ErasedTerm)))
nullDisequalities :: Disequalities -> Bool
nullDisequalities :: Disequalities -> Bool
nullDisequalities (Disequalities IntMap (StrictList (DisequalityHead ErasedTerm))
d) = IntMap (StrictList (DisequalityHead ErasedTerm)) -> Bool
forall a. IntMap a -> Bool
IntMap.null IntMap (StrictList (DisequalityHead ErasedTerm))
d
instance Show Disequalities where
show :: Disequalities -> String
show (Disequalities IntMap (StrictList (DisequalityHead ErasedTerm))
disequalities)
| IntMap (StrictList (DisequalityHead ErasedTerm)) -> Bool
forall a. IntMap a -> Bool
IntMap.null IntMap (StrictList (DisequalityHead ErasedTerm))
disequalities = String
"∅"
| [ShowDisjunction
disjunction] <- [ShowDisjunction]
disjunctions = String
"{ " String -> ShowS
forall a. Semigroup a => a -> a -> a
<> ShowDisjunction -> String
forall a. Show a => a -> String
show ShowDisjunction
disjunction String -> ShowS
forall a. Semigroup a => a -> a -> a
<> String
" }"
| Bool
otherwise = String
"{ " String -> ShowS
forall a. Semigroup a => a -> a -> a
<> String -> [String] -> String
forall a. [a] -> [[a]] -> [a]
intercalate String
" && " [String]
shownDisjunctions String -> ShowS
forall a. Semigroup a => a -> a -> a
<> String
" }"
where
shownDisjunctions :: [String]
shownDisjunctions = (ShowDisjunction -> String) -> [ShowDisjunction] -> [String]
forall a b. (a -> b) -> [a] -> [b]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (\ShowDisjunction
disjunction -> String
"(" String -> ShowS
forall a. Semigroup a => a -> a -> a
<> ShowDisjunction -> String
forall a. Show a => a -> String
show ShowDisjunction
disjunction String -> ShowS
forall a. Semigroup a => a -> a -> a
<> String
")") [ShowDisjunction]
disjunctions
disjunctions :: [ShowDisjunction]
disjunctions = (Int, StrictList (DisequalityHead ErasedTerm)) -> [ShowDisjunction]
showHeads ((Int, StrictList (DisequalityHead ErasedTerm))
-> [ShowDisjunction])
-> [(Int, StrictList (DisequalityHead ErasedTerm))]
-> [ShowDisjunction]
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< IntMap (StrictList (DisequalityHead ErasedTerm))
-> [(Int, StrictList (DisequalityHead ErasedTerm))]
forall a. IntMap a -> [(Int, a)]
IntMap.toList IntMap (StrictList (DisequalityHead ErasedTerm))
disequalities
showHeads :: (Int, StrictList (DisequalityHead ErasedTerm)) -> [ShowDisjunction]
showHeads (Int
varId, StrictList (DisequalityHead ErasedTerm)
heads) =
[(Int, ErasedTerm)] -> ShowDisjunction
ShowDisjunction ([(Int, ErasedTerm)] -> ShowDisjunction)
-> [[(Int, ErasedTerm)]] -> [ShowDisjunction]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (Int -> DisequalityHead ErasedTerm -> [(Int, ErasedTerm)]
headToList Int
varId (DisequalityHead ErasedTerm -> [(Int, ErasedTerm)])
-> [DisequalityHead ErasedTerm] -> [[(Int, ErasedTerm)]]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> StrictList (DisequalityHead ErasedTerm)
-> [DisequalityHead ErasedTerm]
forall a. StrictList a -> [a]
toListReversed StrictList (DisequalityHead ErasedTerm)
heads)
headToList :: Int -> DisequalityHead ErasedTerm -> [(Int, ErasedTerm)]
headToList Int
varId (DisequalityHead ErasedTerm
term (Subst IntMap ErasedTerm
rest)) = (Int
varId, ErasedTerm
term) (Int, ErasedTerm) -> [(Int, ErasedTerm)] -> [(Int, ErasedTerm)]
forall a. a -> [a] -> [a]
: IntMap ErasedTerm -> [(Int, ErasedTerm)]
forall a. IntMap a -> [(Int, a)]
IntMap.toList IntMap ErasedTerm
rest
newtype ShowDisjunction = ShowDisjunction [(Int, ErasedTerm)]
instance Show ShowDisjunction where
show :: ShowDisjunction -> String
show (ShowDisjunction [(Int, ErasedTerm)]
parts) = String -> [String] -> String
forall a. [a] -> [[a]] -> [a]
intercalate String
" || " (((Int, ErasedTerm) -> String) -> [(Int, ErasedTerm)] -> [String]
forall a b. (a -> b) -> [a] -> [b]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (Int, ErasedTerm) -> String
forall {a} {a}. (Show a, Show a) => (a, a) -> String
showPart [(Int, ErasedTerm)]
parts)
where
showPart :: (a, a) -> String
showPart (a
varId, a
term) = String
"_." String -> ShowS
forall a. Semigroup a => a -> a -> a
<> a -> String
forall a. Show a => a -> String
show a
varId String -> ShowS
forall a. Semigroup a => a -> a -> a
<> String
" /= " String -> ShowS
forall a. Semigroup a => a -> a -> a
<> a -> String
forall a. Show a => a -> String
show a
term
data DisequalityHead term = DisequalityHead !term !Subst deriving (Int -> DisequalityHead term -> ShowS
[DisequalityHead term] -> ShowS
DisequalityHead term -> String
(Int -> DisequalityHead term -> ShowS)
-> (DisequalityHead term -> String)
-> ([DisequalityHead term] -> ShowS)
-> Show (DisequalityHead term)
forall term. Show term => Int -> DisequalityHead term -> ShowS
forall term. Show term => [DisequalityHead term] -> ShowS
forall term. Show term => DisequalityHead term -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: forall term. Show term => Int -> DisequalityHead term -> ShowS
showsPrec :: Int -> DisequalityHead term -> ShowS
$cshow :: forall term. Show term => DisequalityHead term -> String
show :: DisequalityHead term -> String
$cshowList :: forall term. Show term => [DisequalityHead term] -> ShowS
showList :: [DisequalityHead term] -> ShowS
Show)
unsafeReconstructDisequalityHead :: DisequalityHead ErasedTerm -> DisequalityHead (Term a)
unsafeReconstructDisequalityHead :: forall a. DisequalityHead ErasedTerm -> DisequalityHead (Term a)
unsafeReconstructDisequalityHead (DisequalityHead ErasedTerm
term Subst
subst) = Term a -> Subst -> DisequalityHead (Term a)
forall term. term -> Subst -> DisequalityHead term
DisequalityHead (ErasedTerm -> Term a
forall a. ErasedTerm -> Term a
unsafeReconstructTerm ErasedTerm
term) Subst
subst
disequalitiesInsert :: Subst -> Disequalities -> Maybe Disequalities
disequalitiesInsert :: Subst -> Disequalities -> Maybe Disequalities
disequalitiesInsert Subst
subst (Disequalities IntMap (StrictList (DisequalityHead ErasedTerm))
d) = do
((varId, value), subst') <- Subst -> Maybe ((Int, ErasedTerm), Subst)
substExtractArbitrary Subst
subst
let entry' = DisequalityHead ErasedTerm
-> StrictList (DisequalityHead ErasedTerm)
-> StrictList (DisequalityHead ErasedTerm)
forall a. a -> StrictList a -> StrictList a
Cons (ErasedTerm -> Subst -> DisequalityHead ErasedTerm
forall term. term -> Subst -> DisequalityHead term
DisequalityHead ErasedTerm
value Subst
subst') (StrictList (DisequalityHead ErasedTerm)
-> Maybe (StrictList (DisequalityHead ErasedTerm))
-> StrictList (DisequalityHead ErasedTerm)
forall a. a -> Maybe a -> a
fromMaybe StrictList (DisequalityHead ErasedTerm)
forall a. StrictList a
Nil (Int
-> IntMap (StrictList (DisequalityHead ErasedTerm))
-> Maybe (StrictList (DisequalityHead ErasedTerm))
forall a. Int -> IntMap a -> Maybe a
IntMap.lookup Int
varId IntMap (StrictList (DisequalityHead ErasedTerm))
d))
return (Disequalities (IntMap.insert varId entry' d))
disequalitiesExtract
:: VarId a
-> Disequalities
-> Maybe (StrictList (DisequalityHead (Term a)), Disequalities)
(VarId Int
varId) (Disequalities IntMap (StrictList (DisequalityHead ErasedTerm))
d) = do
entry <- Int
-> IntMap (StrictList (DisequalityHead ErasedTerm))
-> Maybe (StrictList (DisequalityHead ErasedTerm))
forall a. Int -> IntMap a -> Maybe a
IntMap.lookup Int
varId IntMap (StrictList (DisequalityHead ErasedTerm))
d
let entry' = (DisequalityHead ErasedTerm -> DisequalityHead (Term a))
-> StrictList (DisequalityHead ErasedTerm)
-> StrictList (DisequalityHead (Term a))
forall a b. (a -> b) -> StrictList a -> StrictList b
mapReversed DisequalityHead ErasedTerm -> DisequalityHead (Term a)
forall a. DisequalityHead ErasedTerm -> DisequalityHead (Term a)
unsafeReconstructDisequalityHead StrictList (DisequalityHead ErasedTerm)
entry
let withoutEntry = IntMap (StrictList (DisequalityHead ErasedTerm)) -> Disequalities
Disequalities (Int
-> IntMap (StrictList (DisequalityHead ErasedTerm))
-> IntMap (StrictList (DisequalityHead ErasedTerm))
forall a. Int -> IntMap a -> IntMap a
IntMap.delete Int
varId IntMap (StrictList (DisequalityHead ErasedTerm))
d)
return (entry', withoutEntry)
disequalitiesUpdate
:: (Logical a)
=> State
-> VarId a
-> Term a
-> Disequalities
-> Maybe Disequalities
disequalitiesUpdate :: forall a.
Logical a =>
State -> VarId a -> Term a -> Disequalities -> Maybe Disequalities
disequalitiesUpdate State
state VarId a
varId Term a
value Disequalities
d =
case VarId a
-> Disequalities
-> Maybe (StrictList (DisequalityHead (Term a)), Disequalities)
forall a.
VarId a
-> Disequalities
-> Maybe (StrictList (DisequalityHead (Term a)), Disequalities)
disequalitiesExtract VarId a
varId Disequalities
d of
Maybe (StrictList (DisequalityHead (Term a)), Disequalities)
Nothing -> Disequalities -> Maybe Disequalities
forall a. a -> Maybe a
Just Disequalities
d
Just (StrictList (DisequalityHead (Term a))
varDisequalities, Disequalities
d') ->
(DisequalityHead (Term a) -> Disequalities -> Maybe Disequalities)
-> Disequalities
-> StrictList (DisequalityHead (Term a))
-> Maybe Disequalities
forall (t :: * -> *) (m :: * -> *) a b.
(Foldable t, Monad m) =>
(a -> b -> m b) -> b -> t a -> m b
foldrM DisequalityHead (Term a) -> Disequalities -> Maybe Disequalities
updateDisequality Disequalities
d' StrictList (DisequalityHead (Term a))
varDisequalities
where
value' :: Term a
value' = State -> Term a -> Term a
forall a. Logical a => State -> Term a -> Term a
walk' State
state Term a
value
updateDisequality :: DisequalityHead (Term a) -> Disequalities -> Maybe Disequalities
updateDisequality (DisequalityHead Term a
disallowedValue Subst
subst) Disequalities
d' =
case Term a -> Term a -> State -> Maybe Subst
forall a. Logical a => Term a -> Term a -> State -> Maybe Subst
addedSubst Term a
value' Term a
disallowedValue State
state of
Maybe Subst
Nothing -> Disequalities -> Maybe Disequalities
forall a. a -> Maybe a
Just Disequalities
d'
Just Subst
added
| Subst -> Bool
substNull Subst
subst' -> Maybe Disequalities
forall a. Maybe a
Nothing
| Bool
otherwise -> Subst -> Disequalities -> Maybe Disequalities
disequalitiesInsert Subst
subst' Disequalities
d'
where
subst' :: Subst
subst' = State -> Subst -> Subst
updateComponents State
state (Subst
subst Subst -> Subst -> Subst
forall a. Semigroup a => a -> a -> a
<> Subst
added)
updateComponents :: State -> Subst -> Subst
updateComponents :: State -> Subst -> Subst
updateComponents State
state Subst
subst = case Subst -> Maybe ((Int, ErasedTerm), Subst)
substExtractArbitrary Subst
subst of
Maybe ((Int, ErasedTerm), Subst)
Nothing -> Subst
subst
Just ((Int
varId, ErasedTerm Term a
value), Subst
subst') ->
case Subst -> Maybe Int
substLookupArbitraryId Subst
subst'' of
Just Int
varId' | Int
varId Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
varId' -> Subst
subst''
Maybe Int
_ -> State -> Subst -> Subst
updateComponents State
state Subst
subst''
where
added :: Subst
added = Subst -> Maybe Subst -> Subst
forall a. a -> Maybe a -> a
fromMaybe Subst
substEmpty (Term a -> Term a -> State -> Maybe Subst
forall a. Logical a => Term a -> Term a -> State -> Maybe Subst
addedSubst (VarId a -> Term a
forall a. VarId a -> Term a
Var (Int -> VarId a
forall a. Int -> VarId a
VarId Int
varId)) Term a
value State
state)
subst'' :: Subst
subst'' = Subst
subst' Subst -> Subst -> Subst
forall a. Semigroup a => a -> a -> a
<> Subst
added
data State = State
{ State -> Subst
knownSubst :: !Subst
, State -> Disequalities
disequalities :: !Disequalities
, State -> Int
maxVarId :: !Int
}
deriving (Int -> State -> ShowS
[State] -> ShowS
State -> String
(Int -> State -> ShowS)
-> (State -> String) -> ([State] -> ShowS) -> Show State
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: Int -> State -> ShowS
showsPrec :: Int -> State -> ShowS
$cshow :: State -> String
show :: State -> String
$cshowList :: [State] -> ShowS
showList :: [State] -> ShowS
Show)
empty :: State
empty :: State
empty =
State
{ knownSubst :: Subst
knownSubst = Subst
substEmpty
, disequalities :: Disequalities
disequalities = IntMap (StrictList (DisequalityHead ErasedTerm)) -> Disequalities
Disequalities IntMap (StrictList (DisequalityHead ErasedTerm))
forall a. IntMap a
IntMap.empty
, maxVarId :: Int
maxVarId = Int
0
}
makeVariable :: State -> (State, Term a)
makeVariable :: forall a. State -> (State, Term a)
makeVariable = (Int -> (Int, Term a)) -> State -> (State, Term a)
forall v. (Int -> (Int, v)) -> State -> (State, v)
makeVariables Int -> (Int, Term a)
forall a. Int -> (Int, Term a)
freshVarId
makeVariables :: (Int -> (Int, v)) -> State -> (State, v)
makeVariables :: forall v. (Int -> (Int, v)) -> State -> (State, v)
makeVariables Int -> (Int, v)
mk state :: State
state@State{Int
maxVarId :: State -> Int
maxVarId :: Int
maxVarId} = (State
state{maxVarId = maxVarId'}, v
vars)
where
(Int
maxVarId', v
vars) = Int -> (Int, v)
mk Int
maxVarId
freshVarId :: Int -> (Int, Term a)
freshVarId :: forall a. Int -> (Int, Term a)
freshVarId Int
i = (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1, VarId a -> Term a
forall a. VarId a -> Term a
Var (Int -> VarId a
forall a. Int -> VarId a
VarId Int
i))
shallowWalk :: (Logical a) => State -> Term a -> Term a
shallowWalk :: forall a. Logical a => State -> Term a -> Term a
shallowWalk State
_ t :: Term a
t@Value{} = Term a
t
shallowWalk state :: State
state@State{knownSubst :: State -> Subst
knownSubst = Subst IntMap ErasedTerm
m} t :: Term a
t@(Var (VarId Int
i)) =
case Int -> IntMap ErasedTerm -> Maybe ErasedTerm
forall a. Int -> IntMap a -> Maybe a
IntMap.lookup Int
i IntMap ErasedTerm
m of
Maybe ErasedTerm
Nothing -> Term a
t
Just ErasedTerm
v -> State -> Term a -> Term a
forall a. Logical a => State -> Term a -> Term a
shallowWalk State
state (ErasedTerm -> Term a
forall a. ErasedTerm -> Term a
unsafeReconstructTerm ErasedTerm
v)
addSubst :: (Logical a) => VarId a -> Term a -> State -> Maybe State
addSubst :: forall a. Logical a => VarId a -> Term a -> State -> Maybe State
addSubst (VarId Int
i) Term a
value state :: State
state@State{knownSubst :: State -> Subst
knownSubst = Subst IntMap ErasedTerm
m, disequalities :: State -> Disequalities
disequalities = Disequalities
d}
| Disequalities -> Bool
nullDisequalities Disequalities
d = State -> Maybe State
forall a. a -> Maybe a
Just State
state'
| Bool
otherwise = VarId a -> Term a -> State -> Maybe State
forall a. Logical a => VarId a -> Term a -> State -> Maybe State
stateUpdateDisequalities (Int -> VarId a
forall a. Int -> VarId a
VarId Int
i) Term a
value State
state'
where
state' :: State
state' = State
state{knownSubst = Subst (IntMap.insert i (ErasedTerm value) m)}
stateInsertDisequality :: Subst -> State -> Maybe State
stateInsertDisequality :: Subst -> State -> Maybe State
stateInsertDisequality Subst
subst state :: State
state@State{Disequalities
disequalities :: State -> Disequalities
disequalities :: Disequalities
disequalities} = do
disequalities' <- Subst -> Disequalities -> Maybe Disequalities
disequalitiesInsert Subst
subst Disequalities
disequalities
return state{disequalities = disequalities'}
stateUpdateDisequalities
:: (Logical a)
=> VarId a
-> Term a
-> State
-> Maybe State
stateUpdateDisequalities :: forall a. Logical a => VarId a -> Term a -> State -> Maybe State
stateUpdateDisequalities VarId a
varId Term a
value state :: State
state@State{Disequalities
disequalities :: State -> Disequalities
disequalities :: Disequalities
disequalities} = do
disequalities' <- State -> VarId a -> Term a -> Disequalities -> Maybe Disequalities
forall a.
Logical a =>
State -> VarId a -> Term a -> Disequalities -> Maybe Disequalities
disequalitiesUpdate State
state VarId a
varId Term a
value Disequalities
disequalities
return (state{disequalities = disequalities'})