packages feed

lattest-lib-0.2: src/Lattest/Model/Symbolic/Internal/ExprImpls.hs

{-
This is a modified version of:
TorXakis - Model Based Testing
See LICENSE in the parent Symbolic folder.
-}
{-# LANGUAGE FlexibleContexts    #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE GADTs #-}
{-# LANGUAGE LambdaCase #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE OverloadedLists     #-}
{-# LANGUAGE OverloadedStrings   #-}
{-# LANGUAGE PatternSynonyms #-}
{-# LANGUAGE RankNTypes #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE TupleSections #-}
{-# LANGUAGE TypeApplications #-}
{-# LANGUAGE UndecidableInstances #-}
{-# LANGUAGE ViewPatterns        #-}
{-# OPTIONS_GHC -Wno-redundant-constraints #-}

module Lattest.Model.Symbolic.Internal.ExprImpls
( -- * Constructors to create Value Expressions
  -- ** Constant value
  sConst
, sTrue
, sFalse
  -- ** VarRef
, sVar
  -- ** General Operators to create Value Expressions
  -- *** Equal
, (.==)
  -- *** If Then Else
, sIfThenElse
  -- *** Function Call
--, cstrFunc
  -- ** Boolean Operators to create Value Expressions
  -- *** Not
, sNot
  -- *** And
, sAnd
  -- *** Sum
, sSum
  -- *** Product
, sProduct
  -- *** Divide
, (./)
  -- *** Modulo
, (.%)
  -- *** Comparisons GEZ
, sIsNonNegative
  -- ** List operations
, sLength
, sConcat
, sCons
, sNil
, sAppend
, sElem
, sTake
, sDrop
, sHead
, sTail
, sMap
, sFilter
, sFoldr
, sFoldl
  -- ** Pair operations
, sFirst
, sSecond
, sPair
, pattern SPair
, ETriple, pattern STriple
, EQuadruple, pattern SQuadruple
  -- ** Either
, sEither, sLeft, sRight
  -- ** Nested sums
  -- In Lattest, we only have binary sum (Either) and product (Tuple) types, but you might be interested in a sum or product with three or more subtypes instead.
  -- Here, we provide a few functions that may relieve some of the burden of using nested binary splits to represent such types.
, EThree, sFirstOfThree, sSecondOfThree, sThirdOfThree, sThree
, EFour, sFirstOfFour, sSecondOfFour, sThirdOfFour, sFourthOfFour, sFour
  -- ** Enums
, SEnum (..), SEnum2 (..), SEnum3 (..), SEnum4 (..), SEnum5 (..)
, SEnumThree, sEnum3, SEnumFour, sEnum4, SEnumFive, sEnum5
-- * Quantifiers
, sForall
, sExists
-- * Substitution of var by value
, VarModel(..)
, assign
, Valuation(..)
, varUnion
, mapVars
, mapVarExprs
, valuationToVarModel
, emptyValuation
, assignValues
, assignValue
, getVariables
, identityVarModel
, varsToGuard
, insertIntoValuation
, substConst
, subst
, substVarModel
, assignedExpr
, assignment
, noAssignment
, (=:)
, eval
, reduce
, mapExpressionVars
)
where

import           Control.Arrow   (first)
import qualified Data.Set        as Set

import qualified Lattest.Model.Symbolic.Internal.Boute as Boute
import qualified Lattest.Model.Symbolic.Internal.FreeMonoidX        as FMX
import           Lattest.Model.Symbolic.Internal.Product as Product
import           Lattest.Model.Symbolic.Internal.Sum as Sum
import           Lattest.Model.Symbolic.Internal.ExprDefs
import Data.Dependent.Map (DMap)
import qualified Data.Dependent.Map as DMap
import Data.Constraint.Extras (Has (..))
import Data.Constraint.Compose (ComposeC)
import qualified Data.List as List
import Data.SBV (AlgReal)
import Lattest.Model.Symbolic.Internal.FreeMonoidX (mapFreeMonoidX, allFreeMonoidX)
import GHC.Integer (divInteger)
import Data.Maybe (catMaybes)
import Data.Some (Some (..))
import Data.Dependent.Sum (DSum(..))

sConst :: ExprConstraints t => t -> Expr t
sConst = Expr . Const

sTrue :: Expr Bool
sTrue = sConst True

sFalse :: Expr Bool
sFalse = sConst False

sVar :: Variable t -> Expr t
sVar = Expr . Var

-- | Apply operator ITE (IF THEN ELSE) on the provided value expressions.
-- Preconditions are /not/ checked.
sIfThenElse :: Expr Bool -> Expr t -> Expr t -> Expr t
sIfThenElse (view -> Const True) t _ = t
sIfThenElse (view -> Const False) _ f = f
sIfThenElse (view -> c) (view -> t) (view -> f) = Expr $ Ite c t f

(.==) :: ExprConstraints t => Expr t -> Expr t -> Expr Bool
x .== y = Expr $ Equal (typeOf' x) (view x) (view y)
infix 4 .==

{-
-- | Apply operator Equal on the provided value expressions.
-- Preconditions are /not/ checked.
(.==) :: Expr -> Expr -> Expr
-- Simplification a == a <==> True
(.==) ve1 ve2 | ve1 == ve2                      = sConst (Cbool True)
-- Simplification Different Values <==> False : use Same Values are already detected in previous step
(.==) (view -> Vconst _) (view -> Vconst _)     = sConst (Cbool False)
-- Simplification True == e <==> e (twice)
(.==) (view -> Vconst (Cbool True)) e           = e
(.==) e (view -> Vconst (Cbool True))           = e

-- Simplification False == e <==> not e (twice)
(.==) (view -> Vconst (Cbool False)) e              = sNot e
(.==) e (view -> Vconst (Cbool False))              = sNot e
-- Not x == x <==> false (twice)
(.==) e (view -> Vnot n) | e == n                   = sConst (Cbool False)
(.==) (view -> Vnot n) e | e == n                   = sConst (Cbool False)
-- Not x == Not y <==> x == y   -- same representation
(.==) (view -> Vnot n1) (view -> Vnot n2)     = (.==) n1 n2
-- Not a == b <==> a == Not b -- same representation (twice)
(.==) x@(view -> Vnot n) e                = if n <= e
                                                        then Expr (Vequal x e)
                                                        else Expr (Vequal (sNot e) n)
(.==) e x@(view -> Vnot n)                = if n <= e
                                                        then Expr (Vequal x e)
                                                        else Expr (Vequal (sNot e) n)
-- a == b <==> b == a -- same representation
(.==) ve1 ve2                                   = if ve1 <= ve2
                                                        then Expr (Vequal ve1 ve2)
                                                        else Expr (Vequal ve2 ve1)
-}

-- | Apply operator Not on the provided value expression.
-- Preconditions are /not/ checked.
sNot :: Expr Bool -> Expr Bool
sNot (view -> Const b)      = sConst (not b) -- constant fold: ¬True ≡ False, ¬False ≡ True
sNot (view -> Not ve)       = Expr ve -- eliminate double negation: ¬¬e ≡ e
-- push the negation into the branches: ¬(if cs then tb else fb) ≡ if cs then ¬tb else ¬fb
sNot (view -> Ite cs tb fb) = Expr (Ite cs (view $ sNot (Expr tb)) (view $ sNot (Expr fb)))
sNot (view -> ve)           = Expr $ Not ve

-- | Apply operator And on the provided set of value expressions.
-- Preconditions are /not/ checked.
sAnd :: Set.Set (Expr Bool) -> Expr Bool
--sAnd = sAnd' . flattenAnd
sAnd = mkAnd . flattenAnd
    where
        flattenAnd :: Set.Set (Expr Bool) -> Set.Set (ExprView Bool)
        flattenAnd = Set.unions . map fromExpr . Set.toList

        fromExpr :: Expr Bool -> Set.Set (ExprView Bool)
        fromExpr (view -> And a) = a
        fromExpr (view -> x) = Set.singleton x

        -- annihilation (x ∧ False ≡ False) and identity (x ∧ True ≡ x); a single conjunct needs no wrapping
        mkAnd :: Set.Set (ExprView Bool) -> Expr Bool
        mkAnd (absorb -> vs)
            | Set.member (Const False) vs = sFalse
            | hasComplements vs           = sFalse -- contradiction: x ∧ ¬x ≡ False
            | otherwise = case Set.toList vs' of
                []  -> sTrue
                [v] -> Expr v
                _   -> Expr (And vs')
            where vs' = Set.delete (Const True) vs

        -- absorption under negation: e ∧ ¬(e ∧ rest) ≡ e ∧ ¬rest. A conjunct that is
        -- already asserted at the top level of the conjunction is redundant inside a
        -- negated conjunction, so it can be dropped from it. If every conjunct of the
        -- negated cube is dropped this yields ¬True ≡ False, which the checks above catch.
        absorb :: Set.Set (ExprView Bool) -> Set.Set (ExprView Bool)
        absorb vs = Set.map simplify vs
            where
                simplify (Not (And s))
                    | not (Set.null (Set.intersection s vs)) = view $ sNot $ sAnd $ Set.map Expr $ s Set.\\ vs
                simplify v = v

        -- does the conjunction contain both some e and its negation ¬e?
        hasComplements :: Set.Set (ExprView Bool) -> Bool
        hasComplements vs = any ((`Set.member` vs) . negated) (Set.toList vs)
            where
                negated (Not e) = e
                negated e       = Not e
{-
-- And doesn't contain elements of type Vand.
sAnd' :: Set.Set Expr Bool -> Expr Bool
sAnd' s =
    if Set.member (sConst (Cbool False)) s
        then sConst (Cbool False)
        else let s' = Set.delete (sConst (Cbool True)) s in
                case Set.size s' of
                    0   -> sConst (Cbool True)
                    1   -> head (Set.toList s')
                    _   ->  -- not(x) and x == False
                            let nots = filterNot (Set.toList s') in
                                if any (contains s') nots
                                    then sConst (Cbool False)
--                                    else let ts = isCstrTuples (Set.toList s') in
--                                            if sameExpr ts
--                                                then sConst (Cbool False)
                                                else Expr (Vand s')
    where
        filterNot :: [Expr] -> [Expr]
        filterNot [] = []
        filterNot (x:xs) = case view x of
                            Vnot n -> n : filterNot xs
                            _      ->     filterNot xs
        
        contains :: Set.Set Expr -> Expr -> Bool
        contains set (view -> Vand a) = all (`Set.member` set) (Set.toList a)
        contains set a                = Set.member a set
{-
        isCstrTuples :: [Expr] -> [(CstrId, Expr)]
        isCstrTuples [] = []
        isCstrTuples (x:xs) = case view x of
                                Viscstr c v -> (c,v) : isCstrTuples xs
                                _           ->         isCstrTuples xs
-}
        sameExpr :: [(CstrId, Expr)] ->  Bool
        sameExpr []     = False
        sameExpr (x:xs) = containExpr x xs
            where
                containExpr :: (CstrId, Expr) -> [(CstrId, Expr)] ->  Bool
                containExpr _      []             = False
                containExpr (c1,x1) ((c2,x2):cxs) = if x1 == x2 
                                                        then assert (c1 /= c2) True
                                                        else containExpr (c1,x1) cxs
-}

-- * Sum
isSum :: ExprView Integer -> Bool
isSum (Sum IntType _) = True
isSum _ = False

getSum :: ExprView Integer -> FreeSum (ExprView Integer)
getSum (Sum IntType s) = s
getSum _ = error "ExprImpls.hs - getSum - Unexpected Expr "

sSumInt :: FreeSum (Expr Integer) -> Expr Integer
sSumInt = Expr . cstrSum . FMX.mapTerms (SumTerm . view . summand)

-- | Apply operator sum on the provided sum of value expressions.
-- Preconditions are /not/ checked.
cstrSum :: FreeSum (ExprView Integer) -> ExprView Integer
-- implementation details:
-- Properties incorporated
--    at most one value: the value is the sum of all values
--         special case if the sum is zero, no value is inserted since v == v+0
--    remove all nested sums, since (a+b) + (c+d) == (a+b+c+d)
cstrSum ms = cstrSum' $ nonadds <> FMX.flatten sumOfAdds
    where
      (adds, nonadds) = FMX.partitionT isSum ms
      sumOfAdds :: FMX.FreeMonoidX (FMX.FreeMonoidX (SumTerm (ExprView Integer)))
      sumOfAdds = FMX.mapTerms (getSum . summand) adds

-- Sum doesn't contain elements of type VExprSum
cstrSum' :: FreeSum (ExprView Integer) -> ExprView Integer
cstrSum' ms =
    let (vals, nonvals) = FMX.partitionT isConst ms
        valueSum = FMX.mapTerms (SumTerm . getConst . summand) vals
        sumVals = summand $ FMX.foldFMX valueSum
        retMS = case sumVals of
                    0 -> nonvals                                      -- 0 + x == x
                    _ -> Sum.add (Const sumVals) nonvals
    in
        case FMX.toOccurList retMS of
            []         -> Const 0 -- sum of nothing equal zero
            [(term,1)] -> summand term
            _          -> Sum IntType retMS

getConst :: ExprView e -> e
getConst (Const c) = c
getConst _ = error "Not Const"

isSumF :: ExprView Double -> Bool
isSumF (Sum FloatType _) = True
isSumF _ = False

getSumF :: ExprView Double -> FreeSum (ExprView Double)
getSumF (Sum FloatType s) = s
getSumF _ = error "ExprImpls.hs - getSumF - Unexpected Expr "

isSumR :: ExprView Rational -> Bool
isSumR (Sum RationalType _) = True
isSumR _ = False

getSumR :: ExprView Rational -> FreeSum (ExprView Rational)
getSumR (Sum RationalType s) = s
getSumR _ = error "ExprImpls.hs - getSumF - Unexpected Expr "

isSumReal :: ExprView AlgReal -> Bool
isSumReal (Sum RealType _) = True
isSumReal _ = False

getSumReal :: ExprView AlgReal -> FreeSum (ExprView AlgReal)
getSumReal (Sum RealType s) = s
getSumReal _ = error "ExprImpls.hs - getSumF - Unexpected Expr "

sSumFloat :: FreeSum (Expr Double) -> Expr Double
sSumFloat = Expr . cstrSumF . FMX.mapTerms (SumTerm . view . summand)

-- | Apply operator sum on the provided sum of floating-point values.
cstrSumF :: FreeSum (ExprView Double) -> ExprView Double
cstrSumF ms = cstrSumF' $ nonadds <> FMX.flatten sumOfAdds
    where
      (adds, nonadds) = FMX.partitionT isSumF ms
      sumOfAdds :: FMX.FreeMonoidX (FMX.FreeMonoidX (SumTerm (ExprView Double)))
      sumOfAdds = FMX.mapTerms (getSumF . summand) adds

cstrSumF' :: FreeSum (ExprView Double) -> ExprView Double
cstrSumF' ms =
    let (vals, nonvals) = FMX.partitionT isConst ms
        valueSum = FMX.mapTerms (SumTerm . getConst . summand) vals
        sumVals = summand $ FMX.foldFMX valueSum
        retMS = case sumVals of
                    0.0 -> nonvals                                   -- 0.0 + x == x
                    _   -> Sum.add (Const sumVals) nonvals
    in
        case FMX.toOccurList retMS of
            []         -> Const 0.0 -- sum of nothing equals zero
            [(term,1)] -> summand term
            _          -> Sum FloatType retMS

sSumRational :: FreeSum (Expr Rational) -> Expr Rational
sSumRational = Expr . cstrSumR . FMX.mapTerms (SumTerm . view . summand)

cstrSumR :: FreeSum (ExprView Rational) -> ExprView Rational
cstrSumR ms = cstrSumR' $ nonadds <> FMX.flatten sumOfAdds
    where
      (adds, nonadds) = FMX.partitionT isSumR ms
      sumOfAdds :: FMX.FreeMonoidX (FMX.FreeMonoidX (SumTerm (ExprView Rational)))
      sumOfAdds = FMX.mapTerms (getSumR . summand) adds

cstrSumR' :: FreeSum (ExprView Rational) -> ExprView Rational
cstrSumR' ms =
    let (vals, nonvals) = FMX.partitionT isConst ms
        valueSum = FMX.mapTerms (SumTerm . getConst . summand) vals
        sumVals = summand $ FMX.foldFMX valueSum
        retMS = case sumVals of
                    0.0 -> nonvals                                   -- 0.0 + x == x
                    _   -> Sum.add (Const sumVals) nonvals
    in
        case FMX.toOccurList retMS of
            []         -> Const 0.0 -- sum of nothing equals zero
            [(term,1)] -> summand term
            _          -> Sum RationalType retMS

sSumReal :: FreeSum (Expr AlgReal) -> Expr AlgReal
sSumReal = Expr . cstrSumReal . FMX.mapTerms (SumTerm . view . summand)

cstrSumReal :: FreeSum (ExprView AlgReal) -> ExprView AlgReal
cstrSumReal ms = cstrSumReal' $ nonadds <> FMX.flatten sumOfAdds
    where
      (adds, nonadds) = FMX.partitionT isSumReal ms
      sumOfAdds :: FMX.FreeMonoidX (FMX.FreeMonoidX (SumTerm (ExprView AlgReal)))
      sumOfAdds = FMX.mapTerms (getSumReal . summand) adds

cstrSumReal' :: FreeSum (ExprView AlgReal) -> ExprView AlgReal
cstrSumReal' ms =
    let (vals, nonvals) = FMX.partitionT isConst ms
        valueSum = FMX.mapTerms (SumTerm . getConst . summand) vals
        sumVals = summand $ FMX.foldFMX valueSum
        retMS = case sumVals of
                    0.0 -> nonvals                                   -- 0.0 + x == x
                    _   -> Sum.add (Const sumVals) nonvals
    in
        case FMX.toOccurList retMS of
            []         -> Const 0.0 -- sum of nothing equals zero
            [(term,1)] -> summand term
            _          -> Sum RealType retMS

-- Product

-- | Is Expr a Product Expression?
isProduct :: ExprView Integer -> Bool
isProduct (Product IntType _) = True
isProduct _ = False

getProduct :: ExprView Integer -> FreeProduct (ExprView Integer)
getProduct (Product IntType p) = p
getProduct _ = error "ExprImpls.hs - getProduct - Unexpected Expr "

sProductInt :: FreeProduct (Expr Integer) -> Expr Integer
sProductInt = Expr . cstrPrd . FMX.mapTerms (ProductTerm . view . factor)

-- | Apply operator product on the provided product of value expressions.
-- Be aware that division is not associative for Integer, so only use power >= 0.
-- Preconditions are /not/ checked.
cstrPrd :: FreeProduct (ExprView Integer) -> ExprView Integer
-- implementation details:
-- Properties incorporated
--    at most one value: the value is the product of all values
--         special case if the product is one, no value is inserted since v == v*1
--    remove all nested products, since (a*b) * (c*d) == (a*b*c*d)
cstrPrd ms =
    cstrPrd' $ noprods <> FMX.flatten prodOfProds
    where
      (prods, noprods) = FMX.partitionT isProduct ms
      prodOfProds :: FMX.FreeMonoidX (FMX.FreeMonoidX (ProductTerm (ExprView Integer)))
      prodOfProds = FMX.mapTerms (getProduct . factor) prods

-- Product doesn't contain elements of type VExprProduct
cstrPrd' :: FreeProduct (ExprView Integer) -> ExprView Integer
cstrPrd' ms =
    let (vals, nonvals) = FMX.partitionT isConst ms
        (zeros, _) = FMX.partitionT isZero vals
    in
        case FMX.nrofDistinctTerms zeros of
            0   ->  -- let productVals = Product.foldPower timesVal 1 vals in
                    let intProducts = FMX.mapTerms (getConst <$>) vals
                        productVals = factor (FMX.foldFMX intProducts)
                    in
                        case FMX.toDistinctAscOccurListT nonvals of
                            []          ->  Const productVals
                            [(term, 1)] ->  cstrSum (FMX.fromOccurList [(SumTerm term, productVals)])                           -- term can be Sum -> rewrite needed
                            _           ->  cstrSum (FMX.fromOccurList [(SumTerm (Product IntType nonvals), productVals)])  -- productVals can be 1 -> rewrite possible
            _   ->  let (_, n) = Product.fraction zeros in
                        case FMX.nrofDistinctTerms n of
                            0   ->  Const 0      -- 0 * x == 0
                            _   ->  error "Error in model: Division by Zero in Product (via negative power)"
    where
        isZero :: ExprView Integer -> Bool
        isZero (Const 0) = True
        isZero _         = False

-- Product of floating-point values
isProductF :: ExprView Double -> Bool
isProductF (Product FloatType _) = True
isProductF _ = False

getProductF :: ExprView Double -> FreeProduct (ExprView Double)
getProductF (Product FloatType p) = p
getProductF _ = error "ExprImpls.hs - getProductF - Unexpected Expr "

-- Product of floating-point values
isProductR :: ExprView Rational -> Bool
isProductR (Product RationalType _) = True
isProductR _ = False

getProductR :: ExprView Rational -> FreeProduct (ExprView Rational)
getProductR (Product RationalType p) = p
getProductR _ = error "ExprImpls.hs - getProductF - Unexpected Expr "

-- Product of floating-point values
isProductReal :: ExprView AlgReal -> Bool
isProductReal (Product RealType _) = True
isProductReal _ = False

getProductReal :: ExprView AlgReal -> FreeProduct (ExprView AlgReal)
getProductReal (Product RealType p) = p
getProductReal _ = error "ExprImpls.hs - getProductF - Unexpected Expr "

sProductFloat :: FreeProduct (Expr Double) -> Expr Double
sProductFloat = Expr . cstrPrdF . FMX.mapTerms (ProductTerm . view . factor)

-- | Apply operator product on the provided product of floating-point values.
cstrPrdF :: FreeProduct (ExprView Double) -> ExprView Double
cstrPrdF ms =
    cstrPrdF' $ noprods <> FMX.flatten prodOfProds
    where
      (prods, noprods) = FMX.partitionT isProductF ms
      prodOfProds :: FMX.FreeMonoidX (FMX.FreeMonoidX (ProductTerm (ExprView Double)))
      prodOfProds = FMX.mapTerms (getProductF . factor) prods

-- Product doesn't contain elements of type ProductFloat
cstrPrdF' :: FreeProduct (ExprView Double) -> ExprView Double
cstrPrdF' ms =
    let (vals, nonvals) = FMX.partitionT isConst ms
        (zeros, _) = FMX.partitionT isZeroF vals
    in
        case FMX.nrofDistinctTerms zeros of
            0   ->  let floatProducts = FMX.mapTerms (getConst <$>) vals
                        productVals = factor (FMX.foldFMX floatProducts)
                        withConst = if productVals == 1.0           -- 1.0 * x == x
                                        then nonvals
                                        else Product.multiply (Const productVals) nonvals
                    in
                        case FMX.toDistinctAscOccurListT withConst of
                            []          ->  Const productVals
                            [(term, 1)] ->  term
                            _           ->  Product FloatType withConst
            _   ->  let (_, n) = Product.fraction zeros in
                        case FMX.nrofDistinctTerms n of
                            0   ->  Const 0.0      -- 0.0 * x == 0.0
                            _   ->  error "Error in model: Division by Zero in Product (via negative power)"
    where
        isZeroF :: ExprView Double -> Bool
        isZeroF (Const 0.0) = True
        isZeroF _           = False

sProductRational :: FreeProduct (Expr Rational) -> Expr Rational
sProductRational = Expr . cstrPrdR . FMX.mapTerms (ProductTerm . view . factor)

-- | Apply operator product on the provided product of floating-point values.
cstrPrdR :: FreeProduct (ExprView Rational) -> ExprView Rational
cstrPrdR ms =
    cstrPrdR' $ noprods <> FMX.flatten prodOfProds
    where
      (prods, noprods) = FMX.partitionT isProductR ms
      prodOfProds :: FMX.FreeMonoidX (FMX.FreeMonoidX (ProductTerm (ExprView Rational)))
      prodOfProds = FMX.mapTerms (getProductR . factor) prods

-- Product doesn't contain elements of type ProductFloat
cstrPrdR' :: FreeProduct (ExprView Rational) -> ExprView Rational
cstrPrdR' ms =
    let (vals, nonvals) = FMX.partitionT isConst ms
        (zeros, _) = FMX.partitionT isZeroR vals
    in
        case FMX.nrofDistinctTerms zeros of
            0   ->  let floatProducts = FMX.mapTerms (getConst <$>) vals
                        productVals = factor (FMX.foldFMX floatProducts)
                        withConst = if productVals == 1.0           -- 1.0 * x == x
                                        then nonvals
                                        else Product.multiply (Const productVals) nonvals
                    in
                        case FMX.toDistinctAscOccurListT withConst of
                            []          ->  Const productVals
                            [(term, 1)] ->  term
                            _           ->  Product RationalType withConst
            _   ->  let (_, n) = Product.fraction zeros in
                        case FMX.nrofDistinctTerms n of
                            0   ->  Const 0.0      -- 0.0 * x == 0.0
                            _   ->  error "Error in model: Division by Zero in Product (via negative power)"
    where
        isZeroR :: ExprView Rational -> Bool
        isZeroR (Const 0.0) = True
        isZeroR _           = False

sProductReal :: FreeProduct (Expr AlgReal) -> Expr AlgReal
sProductReal = Expr . cstrPrdReal . FMX.mapTerms (ProductTerm . view . factor)

-- | Apply operator product on the provided product of floating-point values.
cstrPrdReal :: FreeProduct (ExprView AlgReal) -> ExprView AlgReal
cstrPrdReal ms =
    cstrPrdReal' $ noprods <> FMX.flatten prodOfProds
    where
      (prods, noprods) = FMX.partitionT isProductReal ms
      prodOfProds :: FMX.FreeMonoidX (FMX.FreeMonoidX (ProductTerm (ExprView AlgReal)))
      prodOfProds = FMX.mapTerms (getProductReal . factor) prods

-- Product doesn't contain elements of type ProductFloat
cstrPrdReal' :: FreeProduct (ExprView AlgReal) -> ExprView AlgReal
cstrPrdReal' ms =
    let (vals, nonvals) = FMX.partitionT isConst ms
        (zeros, _) = FMX.partitionT isZeroR vals
    in
        case FMX.nrofDistinctTerms zeros of
            0   ->  let floatProducts = FMX.mapTerms (getConst <$>) vals
                        productVals = factor (FMX.foldFMX floatProducts)
                        withConst = if productVals == 1.0           -- 1.0 * x == x
                                        then nonvals
                                        else Product.multiply (Const productVals) nonvals
                    in
                        case FMX.toDistinctAscOccurListT withConst of
                            []          ->  Const productVals
                            [(term, 1)] ->  term
                            _           ->  Product RealType withConst
            _   ->  let (_, n) = Product.fraction zeros in
                        case FMX.nrofDistinctTerms n of
                            0   ->  Const 0.0      -- 0.0 * x == 0.0
                            _   ->  error "Error in model: Division by Zero in Product (via negative power)"
    where
        isZeroR :: ExprView AlgReal -> Bool
        isZeroR (Const 0.0) = True
        isZeroR _           = False

-- Divide

-- | Apply operator Divide on the provided integer value expressions.
-- Preconditions are /not/ checked.
divideInt :: Expr Integer -> Expr Integer -> Expr Integer
divideInt (view ->  Const t) (view -> Const n) | n /= 0 = sConst (t `Boute.div` n) -- leave error case (division by zero) unevaluated
divideInt (view -> vet)         (view -> ven) = Expr (Divide vet ven)

-- | Apply operator Divide on the provided floating-point value expressions.
-- Preconditions are /not/ checked.
divideFloat :: Expr Double -> Expr Double -> Expr Double
divideFloat (view ->  Const t) (view -> Const n) | n /= 0 = sConst (t / n) -- leave error case (division by zero) unevaluated
divideFloat (view -> vet)         (view -> ven) = Expr (DivideFloat vet ven)

-- | Apply operator Divide on the provided floating-point value expressions.
-- Preconditions are /not/ checked.
divideRational :: Expr Rational -> Expr Rational -> Expr Rational
divideRational (view ->  Const t) (view -> Const n) | n /= 0 = sConst (t / n) -- leave error case (division by zero) unevaluated
divideRational (view -> vet)         (view -> ven) = Expr (DivideFloat vet ven)

-- Modulo

-- | Apply operator Modulo on the provided value expressions.
-- Preconditions are /not/ checked.
(.%) :: Expr Integer -> Expr Integer -> Expr Integer
(.%) (view -> Const t) (view -> Const n) | n /= 0 = sConst (t `Boute.mod` n) -- leave error case (division by zero) unevaluated
(.%) (view -> vet)        (view -> ven) = Expr (Modulo vet ven)

infixl 7 .%

-- | Apply operator GEZ (Greater Equal Zero) on the provided integer value expression.
-- Preconditions are /not/ checked.
sIsNonNegativeInt :: Expr Integer -> Expr Bool
-- Simplification Values
sIsNonNegativeInt (view -> Const v) = sConst (0 <= v)
sIsNonNegativeInt (view -> Length _ _)   = sConst True        -- length of list is always Greater or equal to zero
sIsNonNegativeInt (view -> ve)         = Expr (Gez ve)

-- | Apply operator GEZ (Greater Equal Zero) on the provided floating-point value expression.
-- Preconditions are /not/ checked.
sIsNonNegativeFloat :: Num a => Expr a -> Expr Bool
sIsNonNegativeFloat (view -> Const v) = sConst (0 <= v)
sIsNonNegativeFloat (view -> ve)      = Expr (Gez ve)

sSum :: forall a. (Num a, ExprType a) => FreeSum (Expr a) -> Expr a
sSum = case typeOf' (undefined :: Expr a) of
  IntType -> sSumInt
  FloatType -> sSumFloat
  RationalType -> sSumRational
  RealType -> sSumReal
  _ -> error "impossible Num instance"

sProduct :: forall a. (Num a, ExprType a) => FreeProduct (Expr a) -> Expr a
sProduct = case typeOf' (undefined :: Expr a) of
  IntType -> sProductInt
  FloatType -> sProductFloat
  RationalType -> sProductRational
  RealType -> sProductReal
  _ -> error "impossible Num instance"
sIsNonNegative :: Num a => Expr a -> Expr Bool
sIsNonNegative a = case withExprConstraints a $ typeOf' a of
  IntType -> sIsNonNegativeInt a
  FloatType -> sIsNonNegativeFloat a
  RationalType -> sIsNonNegativeFloat a
  RealType -> sIsNonNegativeFloat a
  _ -> error "impossible Num instance"

infixl 7 ./
(./) :: Num a => Expr a -> Expr a -> Expr a
(./) x y = withExprConstraints x $ case typeOf' x of
  IntType -> divideInt x y
  FloatType -> divideFloat x y
  RationalType -> divideRational x y
  _ -> error "impossible Num instance"

sConcat :: ExprConstraints a => Expr [[a]] -> Expr [a]
sConcat = Expr . Concat . view

-- implementation details:
-- Properties incorporated
--    "" ++ x == x          - remove empty strings
--    "a" ++ "b" == "ab"    - concat consecutive string values
--   remove all nested sConcat, since (a ++ b) ++ (c ++ d) == (a ++ b ++ c ++ d)

sLength :: Expr [x] -> Expr Integer
sLength (view -> x) = Expr $ Length (case has @ExprType x $ typeOf' x of ListType t -> t) x

sCons :: Expr x -> Expr [x] -> Expr [x]
sCons (view -> x) (view -> xs) = Expr $ Cons x xs

sNil :: ExprConstraints x => Expr [x]
sNil = Expr $ Const []

sAppend :: Expr [x] -> Expr [x] -> Expr [x]
sAppend (view -> xs) (view -> ys) = Expr $ Append xs ys

sElem :: Expr x -> Expr [x] -> Expr Bool
sElem (view -> x) (view -> xs) = Expr $ LElem (has @ExprType x $ typeOf' x) x xs

sTake :: Expr Integer -> Expr [x] -> Expr [x]
sTake (view -> i) (view -> xs) = Expr $ Take i xs

sDrop :: Expr Integer -> Expr [x] -> Expr [x]
sDrop (view -> i) (view -> xs) = Expr $ Drop i xs

sFirst :: ExprType b => Expr (t, b) -> Expr t
sFirst (view -> i) = Expr $ First (typeOf undefined) i

sSecond :: ExprType a => Expr (a, t) -> Expr t
sSecond (view -> i) = Expr $ Second (typeOf undefined) i

pattern SPair :: (ExprType a, ExprType b) => () => Expr a -> Expr b -> Expr (a,b)
pattern SPair x y <- (\xy -> (sFirst xy, sSecond xy) -> (x, y)) where
  SPair (view -> x) (view -> y) = Expr $ Pair x y

sPair :: Expr a -> Expr b -> Expr (a,b)
sPair x y = withExprConstraints x $ withExprConstraints y $ SPair x y

type ETriple a b c = Expr (a, (b, c))
pattern STriple :: (ExprType a, ExprType b, ExprType c) => () => Expr a -> Expr b -> Expr c -> ETriple a b c
pattern STriple x y z <- (\xyz -> (sFirst xyz, sFirst $ sSecond xyz, sSecond $ sSecond xyz) -> (x, y, z)) where
  STriple (view -> x) (view -> y) (view -> z) = Expr $ Pair x $ Pair y z

type EQuadruple a b c d = Expr (a, (b, (c, d)))
pattern SQuadruple :: (ExprType a, ExprType b, ExprType c, ExprType d) => () => Expr a -> Expr b -> Expr c -> Expr d -> EQuadruple a b c d
pattern SQuadruple w x y z <- (\wxyz -> (sFirst wxyz, sFirst $ sSecond wxyz, sFirst $ sSecond $ sSecond wxyz, sSecond $ sSecond $ sSecond wxyz) -> (w, x, y, z)) where
  SQuadruple (view -> w) (view -> x) (view -> y) (view -> z) = Expr $ Pair w $ Pair x $ Pair y z

sHead :: ExprConstraints x => Expr [x] -> Expr x
sHead (view -> xs) = Expr $ Head xs

sTail :: ExprConstraints x => Expr [x] -> Expr [x]
sTail (view -> xs) = Expr $ Tail xs

-- | Map a function over a list. Think of the variable a and the expression b as morally forming a function a -> b:
-- the variable will, within the expression, represent the argument to the function.
sMap :: (ExprConstraints a, ExprConstraints b) => Variable a -> Expr b -> Expr [a] -> Expr [b]
sMap v (view -> b) (view -> xs) = Expr $ Map v b xs

sFilter :: (ExprConstraints a) => Variable a -> Expr Bool -> Expr [a] -> Expr [a]
sFilter v (view -> b) (view -> xs) = Expr $ Filter v b xs

sFoldr :: (ExprConstraints a) => Variable a -> Variable b -> Expr b -> Expr b -> Expr [a] -> Expr b
sFoldr va vb (view -> b) (view -> i) (view -> xs) = Expr $ Foldr va vb b i xs

sFoldl :: (ExprConstraints a) => Variable b -> Variable a -> Expr b -> Expr b -> Expr [a] -> Expr b
sFoldl vb va (view -> b) (view -> i) (view -> xs) = Expr $ Foldl vb va b i xs

sZip :: (ExprConstraints a, ExprConstraints b) => Expr [a] -> Expr [b] -> Expr [(a,b)]
sZip (view -> xs) (view -> ys) = Expr $ Zip (typeOf undefined) (typeOf undefined) xs ys

-- | Case-of on Either: If sMap can be thought of as having type `(a -> b) -> List a -> List b`,
-- SEither should be considered as having type `(a -> c) -> (b -> c) -> Either a b -> c`.
sEither :: (ExprConstraints a, ExprConstraints b, ExprConstraints c) => Variable a -> Variable b -> Expr c -> Expr c -> Expr (Either a b) -> Expr c
sEither lv rv (view -> le) (view -> re) (view -> e) = Expr $ Either lv rv le re e

sLeft :: (ExprConstraints a, ExprConstraints b) => Expr a -> Expr (Either a b)
sLeft (view -> a) = Expr $ ELeft a

sRight :: (ExprConstraints a, ExprConstraints b) => Expr b -> Expr (Either a b)
sRight (view -> b) = Expr $ ERight b

-- | Sum type with three options
type EThree a b c = Expr (Either a (Either b c))
sFirstOfThree :: (ExprConstraints a, ExprConstraints b, ExprConstraints c) => Expr a -> EThree a b c
sFirstOfThree (view -> a) = Expr $ ELeft a
sSecondOfThree :: (ExprConstraints a, ExprConstraints b, ExprConstraints c) => Expr b -> EThree a b c
sSecondOfThree (view -> b) = Expr $ ERight $ ELeft b
sThirdOfThree :: (ExprConstraints a, ExprConstraints b, ExprConstraints c) => Expr c -> EThree a b c
sThirdOfThree (view -> c) = Expr $ ERight $ ERight c
-- | Case-of on EThree
sThree :: Variable a -> Variable b -> Variable c -> Expr x -> Expr x -> Expr x -> EThree a b c -> Expr x
sThree va vb vc xa xb xc three = let vbc = Variable "sThreeIntermediate" (varType vb `SumType` varType vc) in
  withExprConstraints va $ withExprConstraints vb $ withExprConstraints vc $ withExprConstraints xa $
  sEither va vbc xa (sEither vb vc xb xc (sVar vbc)) three

-- | Sum type with four options
type EFour a b c d = Expr (Either a (Either b (Either c d)))
sFirstOfFour :: (ExprConstraints a, ExprConstraints b, ExprConstraints c, ExprConstraints d) => Expr a -> EFour a b c d
sFirstOfFour (view -> a) = Expr $ ELeft a
sSecondOfFour :: (ExprConstraints a, ExprConstraints b, ExprConstraints c, ExprConstraints d) => Expr b -> EFour a b c d
sSecondOfFour (view -> b) = Expr $ ERight $ ELeft b
sThirdOfFour :: (ExprConstraints a, ExprConstraints b, ExprConstraints c, ExprConstraints d) => Expr c -> EFour a b c d
sThirdOfFour (view -> c) = Expr $ ERight $ ERight $ ELeft c
sFourthOfFour :: (ExprConstraints a, ExprConstraints b, ExprConstraints c, ExprConstraints d) => Expr d -> EFour a b c d
sFourthOfFour (view -> d) = Expr $ ERight $ ERight $ ERight d
-- | Case-of on EFour
sFour :: Variable a -> Variable b -> Variable c -> Variable d -> Expr x -> Expr x -> Expr x -> Expr x -> EFour a b c d -> Expr x
sFour va vb vc vd xa xb xc xd four = let vthree = Variable "sFourIntermediate1" (varType vb `SumType` (varType vc `SumType` varType vd)) in
  withExprConstraints va $ withExprConstraints vb $ withExprConstraints vc $ withExprConstraints vd $ withExprConstraints xa $
  sEither va vthree xa (sThree vb vc vd xb xc xd $ sVar vthree) four

-- | Sum type with five options
type EFive a b c d e = Expr (Either a (Either b (Either c (Either d e))))
-- | Case-of on EFive
sFive :: Variable a -> Variable b -> Variable c -> Variable d -> Variable e -> Expr x -> Expr x -> Expr x -> Expr x -> Expr x -> EFive a b c d e -> Expr x
sFive va vb vc vd ve xa xb xc xd xe five = let vfour = Variable "sFiveIntermediate1" (varType vb `SumType` (varType vc `SumType` (varType vd `SumType` varType ve))) in
  withExprConstraints va $ withExprConstraints vb $ withExprConstraints vc $ withExprConstraints vd $ withExprConstraints ve $ withExprConstraints xa $
  sEither va vfour xa (sFour vb vc vd ve xb xc xd xe $ sVar vfour) five

-- | Symbolic enumerations, represented as sums of units.
class ExprType a => SEnum a where
  sFirstOf :: Expr a
instance SEnum () where
  sFirstOf = sConst ()
instance SEnum a => SEnum (Either () a) where
  sFirstOf = withExprConstraints (typeOf @a undefined) $ sLeft $ sConst ()
-- | Class of enums with at least two options.
class SEnum a => SEnum2 a where
  sSecondOf :: Expr a
instance SEnum a => SEnum2 (Either () a) where
  sSecondOf = withExprConstraints (typeOf @a undefined) $ sRight sFirstOf
class SEnum2 a => SEnum3 a where
  sThirdOf :: Expr a
instance SEnum2 a => SEnum3 (Either () a) where
  sThirdOf = withExprConstraints (typeOf @a undefined) $ sRight sSecondOf
class SEnum3 a => SEnum4 a where
  sFourthOf :: Expr a
instance SEnum3 a => SEnum4 (Either () a) where
  sFourthOf = withExprConstraints (typeOf @a undefined) $ sRight sThirdOf
class SEnum4 a => SEnum5 a where
  sFifthOf :: Expr a
instance SEnum4 a => SEnum5 (Either () a) where
  sFifthOf = withExprConstraints (typeOf @a undefined) $ sRight sFourthOf

type SEnumThree = EThree () () ()
-- | Case-of on Enum with 3 options
sEnum3 :: Expr a -> Expr a -> Expr a -> SEnumThree -> Expr a
sEnum3 = sThree (Variable "1of3" UnitType) (Variable "2of3" UnitType) (Variable "3of3" UnitType)
type SEnumFour = EFour () () () ()
-- | Case-of on Enum with 4 options
sEnum4 :: Expr a -> Expr a -> Expr a -> Expr a -> SEnumFour -> Expr a
sEnum4 = sFour (Variable "1of4" UnitType) (Variable "2of4" UnitType) (Variable "3of4" UnitType) (Variable "4of4" UnitType)
type SEnumFive = EFive () () () () ()
-- | Case-of on Enum with 5 options
sEnum5 :: Expr a -> Expr a -> Expr a -> Expr a -> Expr a -> SEnumFive -> Expr a
sEnum5 = sFive (Variable "1of5" UnitType) (Variable "2of5" UnitType) (Variable "3of5" UnitType) (Variable "4of5" UnitType) (Variable "5of5" UnitType)

sForall :: (ExprConstraints a) => Variable a -> Expr Bool -> Expr Bool
sForall v (view -> x) = Expr $ Forall v x

sExists :: (ExprConstraints a) => Variable a -> Expr Bool -> Expr Bool
sExists v (view -> x) = Expr $ Exists v x

-- | Apply String In Regular Expression operator on the provided value expressions.
-- Preconditions are /not/ checked.
--cstrStrInRe :: Expr -> Expr -> Expr
--cstrStrInRe (view -> Vconst (Cstring s)) (view -> Vconst (Cregex r)) = sConst (Cbool (T.unpack s =~ T.unpack (xsd2posix r) ) )
--cstrStrInRe s r                                                      = Expr (Vstrinre s r)

{-
-- | Create a call to a predefined function as a value expression.
cstrPredef :: PredefKind -> FuncId -> [Expr] -> Expr
cstrPredef p f a = Expr (Vpredef p f a)
-}

newtype Valuation = Valuation { runValuation :: DMap Variable Constant }
  deriving (Eq, Ord)
instance Has (ComposeC Eq Constant) Variable where
  has _ k = k
instance Has (ComposeC Ord Constant) Variable where
  has _ k = k
instance Has (ComposeC Show Constant) Variable where
  has _ k = k

instance Show Valuation where
  show (Valuation val) = "{" ++ List.intercalate "," (printAsAssignments val) ++ "}"
    where
    printAsAssignments :: DMap Variable Constant -> [String]
    printAsAssignments = DMap.foldrWithKey printAsAssignment []
    printAsAssignment v t strs = (varName v ++ ":=" ++ show t) : strs

assignValues :: [Valuation -> Valuation] -> Valuation
assignValues = foldr ($) emptyValuation

emptyValuation :: Valuation
emptyValuation = Valuation DMap.empty

newtype VarModel = VarModel {runVarModel :: DMap Variable Expr}
  deriving (Eq, Ord)
instance Show VarModel where
  show (VarModel vm) = "{" ++ List.intercalate ", " (printAsAssignments vm) ++ "}"
    where
    printAsAssignments :: DMap Variable Expr -> [String]
    printAsAssignments = DMap.foldrWithKey printAsAssignment []
    printAsAssignment v t strs = (varName v ++ ":=" ++ show t) : strs

assignment :: [VarModel -> VarModel] -> VarModel
assignment = foldr ($) noAssignment

valuationToVarModel :: Valuation -> VarModel
valuationToVarModel = VarModel . DMap.map (\(Constant v) -> sConst v) . runValuation

insertIntoValuation :: Variable t -> Constant t -> Valuation -> Valuation
insertIntoValuation v c = withExprConstraints (varType v) $ assignValue v (fromConst c)

getVariables :: Valuation -> [Some Variable]
getVariables = DMap.keys . runValuation

assignIdentity :: Variable a -> VarModel -> VarModel
assignIdentity v = assign v (sVar v)

identityVarModel :: [Some Variable] -> VarModel
identityVarModel vars = assignment $ (\(Some v) -> assignIdentity v) <$> vars

varUnion :: VarModel -> VarModel -> VarModel
varUnion (VarModel vars1) (VarModel vars2) = VarModel $ DMap.union vars1 vars2

mapVars :: (forall a. Variable a -> Variable a) -> VarModel -> VarModel
mapVars f (VarModel vars) = VarModel $ DMap.mapKeysWith (error "mapVars mapped two distinct variables to the same variable") f vars

mapVarExprs :: (forall a. Variable a -> Variable a) -> VarModel -> VarModel
mapVarExprs f (VarModel vars) = VarModel $ DMap.map (mapExpressionVars f) vars

varsToGuard :: VarModel -> Expr Bool
varsToGuard (VarModel vars) = sAnd $ Set.fromList $ map (\(var :=> val) -> has @ExprType val $ withExprConstraints (typeOf' val) $ sVar var .== val) $ DMap.assocs vars


(=:) :: Variable t -> Expr t -> VarModel -> VarModel
(=:) = assign
infixr 0 =:

assign :: Variable t -> Expr t -> VarModel -> VarModel
assign v e = VarModel . DMap.insert v e . runVarModel

assignValue :: ExprConstraints t => Variable t -> t -> Valuation -> Valuation
assignValue v val = Valuation . DMap.insert v (Constant val) . runValuation

assignedExpr :: Variable t -> VarModel -> Maybe (Expr t)
assignedExpr v = DMap.lookup v . runVarModel

assignedExprWithDefault :: Variable t -> VarModel -> Expr t
assignedExprWithDefault v = DMap.findWithDefault (sVar v) v . runVarModel

noAssignment :: VarModel
noAssignment = VarModel DMap.empty

substConst :: Valuation -> Expr t -> Expr t
substConst valuation = subst (valuationToVarModel valuation)

-- | Apply a substitution to the right-hand-side expressions of a 'VarModel', leaving its keys untouched.
-- Composing substitutions this way lets an assignment be resolved against an accumulated substitution:
-- @substVarModel sigma assign@ rewrites every value-expression in @assign@ according to @sigma@.
substVarModel :: VarModel -> VarModel -> VarModel
substVarModel sigma (VarModel vars) = VarModel $ DMap.map (subst sigma) vars

-- | Substitute variables by value expressions in a value expression.
--
-- Preconditions are /not/ checked.
--
subst :: VarModel      -- ^ Map from variables to value expressions.
{-      -> Map.Map FuncId (FuncDef w e) -- ^ Map from identifiers to their
                                    -- definitions, this is used to replace
                                    -- function calls by their bodies if all
                                    -- the arguments of the function are
                                    -- constant.-}
      -> Expr t                -- ^ Value expression where the
                                    -- substitution will take place.
      -> Expr t
--subst ve _ x   | ve == Map.empty = x
subst ve x = subst' ve (view x)

subst' :: VarModel -> ExprView t -> Expr t
subst' _  (Const const')          = sConst const'
subst' ve (Var vid)               = assignedExprWithDefault vid ve
subst' ve (Ite cond vexp1 vexp2)  = sIfThenElse (subst' ve cond) (subst' ve vexp1) (subst' ve vexp2)
subst' ve (Divide t n)            = (./) (subst' ve t) (subst' ve n)
subst' ve (Modulo t n)            = (.%) (subst' ve t) (subst' ve n)
subst' ve (DivideFloat t n)       = (./) (subst' ve t) (subst' ve n)
subst' ve (Sum t s)               = withExprConstraints t $ sSum $ FMX.fromOccurListT $ map (first (subst' ve)) $ FMX.toDistinctAscOccurListT s
subst' ve (Product t p)           = withExprConstraints t $ sProduct $ FMX.fromOccurListT $ map (first (subst' ve)) $ FMX.toDistinctAscOccurListT p
subst' ve (Length _ vexp) = sLength $ subst' ve vexp
subst' ve (Gez v)                = sIsNonNegative (subst' ve v)
subst' ve (Equal _ vexp1 vexp2)    = (.==) (subst' ve vexp1) (subst' ve vexp2)
subst' ve (And vexps)               = sAnd $ Set.map (subst' ve) vexps
subst' ve (Not vexp)                = sNot (subst' ve vexp)
subst' ve (Concat vexps)                = sConcat $ subst' ve vexps
subst' ve (Cons x xs) = has @ExprType x $ sCons (subst' ve x) (subst' ve xs)
subst' ve (Append xs ys) = sAppend (subst' ve xs) (subst' ve ys)
subst' ve (LElem t x xs) = has @ExprType t $ sElem (subst' ve x) (subst' ve xs)
subst' ve (Take x xs) = sTake (subst' ve x) (subst' ve xs)
subst' ve (Drop x xs) = sDrop (subst' ve x) (subst' ve xs)
subst' ve (First t x) = has @ExprType t $ sFirst $ subst' ve x
subst' ve (Second t x) = has @ExprType t $ sSecond $ subst' ve x
subst' ve (Pair x y) = sPair (subst' ve x) (subst' ve y)
subst' ve (Head x) = sHead $ subst' ve x
subst' ve (Tail x) = sTail $ subst' ve x
subst' ve (ELeft x) = sLeft $ subst' ve x
subst' ve (ERight x) = sRight $ subst' ve x
subst' ve (Zip a b x y) = withExprConstraints a $ withExprConstraints b $ sZip (subst' ve x) (subst' ve y)
-- note: we purposely substitute the non-free variables too here. This ensures that any nested higher-order functions (e.g. a Map with an Either in the function)
-- that have shadowing (i.e. the name of the Map variable is also used by one of the Either variables) continue to work as expected:
-- each use of the variable refers to the closest (innermost) binder
subst' ve (Map v f xs) = Expr $ Map (case assignedExprWithDefault v ve of {Expr (Var v') -> v'; _ -> error "impossible"}) (view $ subst' ve f) (view $ subst' ve xs)
subst' ve (Filter v f xs) = Expr $ Filter (case assignedExprWithDefault v ve of {Expr (Var v') -> v'; _ -> error "impossible"}) (view $ subst' ve f) (view $ subst' ve xs)
subst' ve (Foldr v1 v2 f i xs) = Expr $ Foldr (case assignedExprWithDefault v1 ve of {Expr (Var v') -> v'; _ -> error "impossible"}) (case assignedExprWithDefault v2 ve of {Expr (Var v') -> v'; _ -> error "impossible"}) (view $ subst' ve f) (view $ subst' ve i) (view $ subst' ve xs)
subst' ve (Foldl v1 v2 f i xs) = Expr $ Foldl (case assignedExprWithDefault v1 ve of {Expr (Var v') -> v'; _ -> error "impossible"}) (case assignedExprWithDefault v2 ve of {Expr (Var v') -> v'; _ -> error "impossible"}) (view $ subst' ve f) (view $ subst' ve i) (view $ subst' ve xs)
subst' ve (Either vl vr l r x) = Expr $ Either
  (case assignedExprWithDefault vl ve of { Expr (Var v) -> v; _ -> error "impossible"})
  (case assignedExprWithDefault vr ve of { Expr (Var v) -> v; _ -> error "impossible"})
  (view $ subst' ve l)
  (view $ subst' ve r)
  (view $ subst' ve x)
subst' ve (Forall v x) = Expr $ Forall (case assignedExprWithDefault v ve of {Expr (Var v') -> v'; _ -> error "impossible"}) (view $ subst' ve x)
subst' ve (Exists v x) = Expr $ Exists (case assignedExprWithDefault v ve of {Expr (Var v') -> v'; _ -> error "impossible"}) (view $ subst' ve x)


-- | Evaluate the provided value expression.
-- Either the Right Constant Value is returned or a (Left) error message.
eval :: Expr v -> Either String v
eval = evalView . view

evalView :: ExprView v -> Either String v
evalView (reduce -> Const v) = Right v
evalView _ = Left "Value Expression is not a constant value"

reduce :: ExprView v -> ExprView v
reduce (Var v) = Var v
reduce (Const v) = Const v
reduce (Ite (reduce -> Const b) (reduce -> e1) (reduce -> e2)) = if b then e1 else e2
reduce (Ite (reduce -> c) (reduce -> e1) (reduce -> e2)) = Ite c e1 e2
reduce (Sum t (mapFreeMonoidX reduce -> es)) | allFreeMonoidX isConst es = withExprConstraints t $ Const $ FMX.fold $ mapFreeMonoidX constant es
reduce (Sum t (mapFreeMonoidX reduce -> es)) = Sum t es
reduce (Product t (mapFreeMonoidX reduce -> es)) | allFreeMonoidX isConst es = withExprConstraints t $ Const $ FMX.fold $ mapFreeMonoidX constant es
reduce (Product t (mapFreeMonoidX reduce -> es)) = Product t es
reduce (Modulo (reduce -> e1) (reduce -> e2@(Const 0))) = Modulo e1 e2 -- leave divisions by zero as expressions
reduce (Modulo (reduce -> (Const x)) (reduce -> (Const y))) = Const $ x `mod` y
reduce (Modulo (reduce -> e1) (reduce -> e2)) = Modulo e1 e2
reduce (Divide (reduce -> e1) (reduce -> e2@(Const 0))) = Divide e1 e2 -- leave divisions by zero as expressions
reduce (Divide (reduce -> (Const x)) (reduce -> (Const y))) = Const $ x `divInteger` y
reduce (Divide (reduce -> e1) (reduce -> e2)) = Divide e1 e2
reduce (DivideFloat (reduce -> e1) (reduce -> e2@(Const 0))) = DivideFloat e1 e2 -- leave divisions by zero as expressions
reduce (DivideFloat (reduce -> (Const x)) (reduce -> (Const y))) = Const $ x / y
reduce (DivideFloat (reduce -> e1) (reduce -> e2)) = DivideFloat e1 e2
reduce (Length _ (reduce -> Const xs)) = Const $ fromIntegral $ length xs
reduce (Length t (reduce -> e)) = Length t e
reduce (Equal _ (reduce -> Const e1) (reduce -> Const e2)) = Const (e1 == e2)
reduce (Equal t (reduce -> e1) (reduce -> e2)) = Equal t e1 e2
reduce (Gez (reduce -> (Const x))) = Const $ x >= 0
reduce (Gez (reduce -> e)) = Gez e
reduce (Not (reduce -> (Const b))) = Const $ not b
reduce (Not (reduce -> e)) = Not e
reduce (And (Set.map reduce -> es))
  | all isConst es = Const $ and (Set.map constant es)
  | xs <- Set.filter isConst es
  , ys <- Set.filter (not . isConst) es
  = if and (Set.map constant xs) then And ys else Const False
reduce (Zip a b (reduce -> x) (reduce -> y))
  | Const xs <- x
  , Const ys <- y
  = withExprConstraints a $ withExprConstraints b $ Const $ zip xs ys
  | otherwise = Zip a b x y
reduce (Concat (reduce -> es))
  | Const as <- es = Const $ concat as
reduce (Concat (reduce -> e)) = Concat e
reduce (Cons (reduce -> x) (reduce -> xs))
  | Const a <- x
  , Const as <- xs = Const $ a : as
  | otherwise = Cons x xs
reduce (Append (reduce -> xs) (reduce -> ys))
  | Const as <- xs
  , Const bs <- ys = Const $ as ++ bs
  | otherwise = Append xs ys
reduce (LElem t (reduce -> x) (reduce -> xs))
  | Const a <- x
  , Const as <- xs = Const $ a `elem` as
  | otherwise = LElem t x xs
reduce (Take (reduce -> i) (reduce -> xs))
  | Const j <- i
  , Const as <- xs = Const $ take (fromInteger j) as
  | otherwise = Take i xs
reduce (Drop (reduce -> i) (reduce -> xs))
  | Const j <- i
  , Const as <- xs = Const $ drop (fromInteger j) as
  | otherwise = Drop i xs
reduce (First tp (reduce -> x))
  | Const (y,_) <- x = case typeOf' x of
      TupleType t _ -> withExprConstraints t $ Const y
  | otherwise = First tp x
reduce (Second tp (reduce -> x))
  | Const (_,y) <- x = case typeOf' x of
      TupleType _ t -> withExprConstraints t $ Const y
  | otherwise = Second tp x
reduce (Pair (reduce -> x) (reduce -> y))
  | Const a <- x
  , Const b <- y = Const (a,b)
  | otherwise = Pair x y
reduce (Head (reduce -> xs))
  | Const (y:_) <- xs = Const y
  | Const [] <- xs = error "Head of empty list"
  | otherwise = Head xs
reduce (Tail (reduce -> xs))
  | Const (_:y) <- xs = Const y
  | Const [] <- xs = error "Tail of empty list"
  | otherwise = Tail xs
reduce (ELeft (reduce -> x))
  | Const y <- x = Const (Left y)
  | otherwise = ELeft x
reduce (ERight (reduce -> x))
  | Const y <- x = Const (Right y)
  | otherwise = ERight x
reduce (Map v (reduce -> f') (reduce -> xs))
  | Const ys <- xs =
    let f y = reduce $ view $ subst' (VarModel $ DMap.singleton v $ Expr $ Const y) f'
        zs = map f ys
    in case traverse (\case
                        Const a -> Just a
                        _ -> Nothing) zs of
      Just as -> Const as
      Nothing -> Map v f' xs
  | otherwise = Map v f' xs
reduce (Filter v (reduce -> f') (reduce -> xs))
  | Const ys <- xs =
    let f y = (y,) $ reduce $ view $ subst' (VarModel $ DMap.singleton v $ Expr $ Const y) f'
        zs = map f ys
    in case traverse (\case -- innermost Maybe is whether the filter accepts the element, outermost Maybe is whether the reduction succeeds
                        (y, Const True) -> Just (Just y)
                        (_, Const False) -> Just Nothing
                        _ -> Nothing) zs of
      Just as -> Const $ catMaybes as
      Nothing -> Filter v f' xs
  | otherwise = Filter v f' xs
reduce (Foldr v1 v2 (reduce -> f') (reduce -> i') (reduce -> xs))
  | Const ys <- xs
  , Const i <- i' =
    let f a b = reduce $ view $ subst' (VarModel $ DMap.insert v2 (Expr b) $ DMap.singleton v1 $ Expr $ Const a) f'
    in foldr f (Const i) ys
  | otherwise = Foldr v1 v2 f' i' xs
reduce (Foldl v1 v2 (reduce -> f') (reduce -> i') (reduce -> xs))
  | Const ys <- xs
  , Const i <- i' =
    let f b a = reduce $ view $ subst' (VarModel $ DMap.insert v1 (Expr b) $ DMap.singleton v2 $ Expr $ Const a) f'
    in foldl f (Const i) ys
  | otherwise = Foldl v1 v2 f' i' xs
reduce (Either vl vr (reduce -> l) (reduce -> r) (reduce -> x))
  | Const (Left x') <- x =
    reduce $ view $ subst' (VarModel $ DMap.singleton vl $ Expr $ Const x') l
  | Const (Right x') <- x =
    reduce $ view $ subst' (VarModel $ DMap.singleton vr $ Expr $ Const x') r
  | otherwise = Either vl vr l r x
reduce (Forall v (reduce -> x))
  | Const b <- x = Const b
  | otherwise = Forall v x
reduce (Exists v (reduce -> x))
  | Const b <- x = Const b
  | otherwise = Exists v x

mapExpressionVars :: (forall a. Variable a -> Variable a) -> Expr t -> Expr t
mapExpressionVars f = Expr . mapExpressionVars' f . view

mapExpressionVars' :: (forall a. Variable a -> Variable a) -> ExprView t -> ExprView t
mapExpressionVars' _ e@(Const _) = e
mapExpressionVars' f (Var v) = Var $ f v -- this line is effectively the purpose of this function
mapExpressionVars' f (Ite cond vexp1 vexp2)  = Ite (mapExpressionVars' f cond) (mapExpressionVars' f vexp1) (mapExpressionVars' f vexp2)
mapExpressionVars' f (Divide t n)            = Divide (mapExpressionVars' f t) (mapExpressionVars' f n)
mapExpressionVars' f (Modulo t n)            = Modulo (mapExpressionVars' f t) (mapExpressionVars' f n)
mapExpressionVars' f (DivideFloat t n)       = DivideFloat (mapExpressionVars' f t) (mapExpressionVars' f n)
mapExpressionVars' f (Sum t s)               = Sum t (FMX.mapTerms (SumTerm . mapExpressionVars' f . summand) s)
mapExpressionVars' f (Product t p)           = Product t (FMX.mapTerms (ProductTerm . mapExpressionVars' f . factor) p)
mapExpressionVars' f (Length t vexp)         = Length t (mapExpressionVars' f vexp)
mapExpressionVars' f (Gez v)                 = Gez (mapExpressionVars' f v)
mapExpressionVars' f (And vexps)             = And (Set.map (mapExpressionVars' f) vexps)
mapExpressionVars' f (Not vexp)              = Not (mapExpressionVars' f vexp)
mapExpressionVars' f (Equal t x y)           = Equal t (mapExpressionVars' f x) (mapExpressionVars' f y)
mapExpressionVars' f (LElem t x y)           = LElem t (mapExpressionVars' f x) (mapExpressionVars' f y)
mapExpressionVars' f (Concat x)              = Concat (mapExpressionVars' f x)
mapExpressionVars' f (Cons x xs)             = Cons (mapExpressionVars' f x) (mapExpressionVars' f xs)
mapExpressionVars' f (Append x xs)           = Append (mapExpressionVars' f x) (mapExpressionVars' f xs)
mapExpressionVars' f (Take x xs)             = Take (mapExpressionVars' f x) (mapExpressionVars' f xs)
mapExpressionVars' f (Drop x xs)             = Drop (mapExpressionVars' f x) (mapExpressionVars' f xs)
mapExpressionVars' f (First t x)             = First t (mapExpressionVars' f x)
mapExpressionVars' f (Second t x)            = Second t (mapExpressionVars' f x)
mapExpressionVars' f (Pair x xs)             = Pair (mapExpressionVars' f x) (mapExpressionVars' f xs)
mapExpressionVars' f (Head v)                = Head (mapExpressionVars' f v)
mapExpressionVars' f (Tail v)                = Tail (mapExpressionVars' f v)
mapExpressionVars' f (ELeft v)               = ELeft (mapExpressionVars' f v)
mapExpressionVars' f (ERight v)              = ERight (mapExpressionVars' f v)
mapExpressionVars' f (Zip a b x y)           = Zip a b (mapExpressionVars' f x) (mapExpressionVars' f y)
mapExpressionVars' f (Map v x xs)            = Map (f v) (mapExpressionVars' f x) (mapExpressionVars' f xs)
mapExpressionVars' f (Filter v x xs)         = Filter (f v) (mapExpressionVars' f x) (mapExpressionVars' f xs)
mapExpressionVars' f (Foldr v1 v2 g i xs)    = Foldr (f v1) (f v2) (mapExpressionVars' f g) (mapExpressionVars' f i) (mapExpressionVars' f xs)
mapExpressionVars' f (Foldl v1 v2 g i xs)    = Foldl (f v1) (f v2) (mapExpressionVars' f g) (mapExpressionVars' f i) (mapExpressionVars' f xs)
mapExpressionVars' f (Either v1 v2 l r x)    = Either (f v1) (f v2) (mapExpressionVars' f l) (mapExpressionVars' f r) (mapExpressionVars' f x)
mapExpressionVars' f (Forall v x)            = Forall (f v) (mapExpressionVars' f x)
mapExpressionVars' f (Exists v x)            = Exists (f v) (mapExpressionVars' f x)