{-# language MultiParamTypeClasses #-}
{-# language FlexibleContexts      #-}
{-# language UndecidableInstances  #-}
{-# language FlexibleInstances #-}

module Satchmo.Polynomial 

( Poly (Poly), NumPoly, polynomial, constant, fromCoefficients
, isNull, null, constantTerm, coefficients
, equals, ge, gt
, add, times, subtract, compose, apply, derive
)

where

import Prelude hiding (subtract,null)
import Data.Map ( Map )
import qualified Data.Map as M
import Control.Applicative ((<$>))
import Control.Monad (foldM)

import Satchmo.MonadSAT (MonadSAT)
import Satchmo.Boolean (Boolean,monadic)
import qualified Satchmo.Boolean as B
import Satchmo.Code

import qualified Satchmo.BinaryTwosComplement.Op.Fixed as F
--import qualified Satchmo.Binary.Op.Fixed as F

import Control.Monad ( forM )

-- | polynomial in one variable,
-- coefficients starting from degree zero
data Poly a = Poly [a] deriving ( Poly a -> Poly a -> Bool
(Poly a -> Poly a -> Bool)
-> (Poly a -> Poly a -> Bool) -> Eq (Poly a)
forall a. Eq a => Poly a -> Poly a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: forall a. Eq a => Poly a -> Poly a -> Bool
== :: Poly a -> Poly a -> Bool
$c/= :: forall a. Eq a => Poly a -> Poly a -> Bool
/= :: Poly a -> Poly a -> Bool
Eq, Eq (Poly a)
Eq (Poly a) =>
(Poly a -> Poly a -> Ordering)
-> (Poly a -> Poly a -> Bool)
-> (Poly a -> Poly a -> Bool)
-> (Poly a -> Poly a -> Bool)
-> (Poly a -> Poly a -> Bool)
-> (Poly a -> Poly a -> Poly a)
-> (Poly a -> Poly a -> Poly a)
-> Ord (Poly a)
Poly a -> Poly a -> Bool
Poly a -> Poly a -> Ordering
Poly a -> Poly a -> Poly a
forall a.
Eq a =>
(a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
forall a. Ord a => Eq (Poly a)
forall a. Ord a => Poly a -> Poly a -> Bool
forall a. Ord a => Poly a -> Poly a -> Ordering
forall a. Ord a => Poly a -> Poly a -> Poly a
$ccompare :: forall a. Ord a => Poly a -> Poly a -> Ordering
compare :: Poly a -> Poly a -> Ordering
$c< :: forall a. Ord a => Poly a -> Poly a -> Bool
< :: Poly a -> Poly a -> Bool
$c<= :: forall a. Ord a => Poly a -> Poly a -> Bool
<= :: Poly a -> Poly a -> Bool
$c> :: forall a. Ord a => Poly a -> Poly a -> Bool
> :: Poly a -> Poly a -> Bool
$c>= :: forall a. Ord a => Poly a -> Poly a -> Bool
>= :: Poly a -> Poly a -> Bool
$cmax :: forall a. Ord a => Poly a -> Poly a -> Poly a
max :: Poly a -> Poly a -> Poly a
$cmin :: forall a. Ord a => Poly a -> Poly a -> Poly a
min :: Poly a -> Poly a -> Poly a
Ord, Int -> Poly a -> ShowS
[Poly a] -> ShowS
Poly a -> String
(Int -> Poly a -> ShowS)
-> (Poly a -> String) -> ([Poly a] -> ShowS) -> Show (Poly a)
forall a. Show a => Int -> Poly a -> ShowS
forall a. Show a => [Poly a] -> ShowS
forall a. Show a => Poly a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: forall a. Show a => Int -> Poly a -> ShowS
showsPrec :: Int -> Poly a -> ShowS
$cshow :: forall a. Show a => Poly a -> String
show :: Poly a -> String
$cshowList :: forall a. Show a => [Poly a] -> ShowS
showList :: [Poly a] -> ShowS
Show )

type NumPoly = Poly F.Number

instance Decode m a Integer => Decode m (Poly a) (Poly Integer) where
    decode :: Poly a -> m (Poly Integer)
decode (Poly [a]
xs) = do
      [Integer]
decodedXs <- [a] -> (a -> m Integer) -> m [Integer]
forall (t :: * -> *) (m :: * -> *) a b.
(Traversable t, Monad m) =>
t a -> (a -> m b) -> m (t b)
forM [a]
xs a -> m Integer
forall (m :: * -> *) c a. Decode m c a => c -> m a
decode 
      Poly Integer -> m (Poly Integer)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (Poly Integer -> m (Poly Integer))
-> Poly Integer -> m (Poly Integer)
forall a b. (a -> b) -> a -> b
$ [Integer] -> Poly Integer
forall a. [a] -> Poly a
Poly [Integer]
decodedXs

fromCoefficients :: MonadSAT m => Int -- ^ Bits
                 -> [Integer]         -- ^ Coefficients
                 -> m NumPoly
fromCoefficients :: forall (m :: * -> *). MonadSAT m => Int -> [Integer] -> m NumPoly
fromCoefficients Int
width [Integer]
coefficients = 
    [Number] -> NumPoly
forall a. [a] -> Poly a
Poly ([Number] -> NumPoly) -> m [Number] -> m NumPoly
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> ([Integer] -> (Integer -> m Number) -> m [Number]
forall (t :: * -> *) (m :: * -> *) a b.
(Traversable t, Monad m) =>
t a -> (a -> m b) -> m (t b)
forM [Integer]
coefficients ((Integer -> m Number) -> m [Number])
-> (Integer -> m Number) -> m [Number]
forall a b. (a -> b) -> a -> b
$ Int -> Integer -> m Number
forall (m :: * -> *). MonadSAT m => Int -> Integer -> m Number
F.constantWidth Int
width)

polynomial :: MonadSAT m => Int -- ^ Bits
           -> Int -- ^ Degree
           -> m NumPoly
polynomial :: forall (m :: * -> *). MonadSAT m => Int -> Int -> m NumPoly
polynomial Int
bits Int
deg = 
    [Number] -> NumPoly
forall a. [a] -> Poly a
Poly ([Number] -> NumPoly) -> m [Number] -> m NumPoly
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> ([Int] -> (Int -> m Number) -> m [Number]
forall (t :: * -> *) (m :: * -> *) a b.
(Traversable t, Monad m) =>
t a -> (a -> m b) -> m (t b)
forM [ Int
0 .. Int
deg ] ((Int -> m Number) -> m [Number])
-> (Int -> m Number) -> m [Number]
forall a b. (a -> b) -> a -> b
$ \ Int
i -> Int -> m Number
forall (m :: * -> *). MonadSAT m => Int -> m Number
F.number Int
bits)

constant :: MonadSAT m
         => Integer
         -> m NumPoly
constant :: forall (m :: * -> *). MonadSAT m => Integer -> m NumPoly
constant Integer
0 = NumPoly -> m NumPoly
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (NumPoly -> m NumPoly) -> NumPoly -> m NumPoly
forall a b. (a -> b) -> a -> b
$ [Number] -> NumPoly
forall a. [a] -> Poly a
Poly []
constant Integer
const = do
    Number
c <- Integer -> m Number
forall (m :: * -> *). MonadSAT m => Integer -> m Number
F.constant Integer
const
    NumPoly -> m NumPoly
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (NumPoly -> m NumPoly) -> NumPoly -> m NumPoly
forall a b. (a -> b) -> a -> b
$ [Number] -> NumPoly
forall a. [a] -> Poly a
Poly [Number
c]

-- | this is sort of wrong:
-- null polynomial should have degree -infty
-- but this function will return -1
degree :: Poly a -> Int
degree :: forall a. Poly a -> Int
degree ( Poly [a]
xs ) = Int -> Int
forall a. Enum a => a -> a
pred (Int -> Int) -> Int -> Int
forall a b. (a -> b) -> a -> b
$ [a] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
xs

isNull :: Poly a -> Bool
isNull :: forall a. Poly a -> Bool
isNull (Poly []) = Bool
True
isNull Poly a
_         = Bool
False

null :: Poly a
null :: forall a. Poly a
null = [a] -> Poly a
forall a. [a] -> Poly a
Poly []

constantTerm :: Poly a -> a
constantTerm :: forall a. Poly a -> a
constantTerm (Poly (a
c:[a]
_)) = a
c

coefficients :: Poly a -> [a]
coefficients :: forall a. Poly a -> [a]
coefficients (Poly [a]
cs) = [a]
cs

fill :: MonadSAT m => NumPoly -> NumPoly -> m ([F.Number],[F.Number])
fill :: forall (m :: * -> *).
MonadSAT m =>
NumPoly -> NumPoly -> m ([Number], [Number])
fill (Poly [Number]
p1) (Poly [Number]
p2) = do
  Number
zero <- Integer -> m Number
forall (m :: * -> *). MonadSAT m => Integer -> m Number
F.constant Integer
0
  let maxL :: Int
maxL = Int -> Int -> Int
forall a. Ord a => a -> a -> a
max ([Number] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [Number]
p1) ([Number] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [Number]
p2)
      fill' :: [Number] -> [Number]
fill' [Number]
xs = Int -> [Number] -> [Number]
forall a. Int -> [a] -> [a]
take Int
maxL ([Number] -> [Number]) -> [Number] -> [Number]
forall a b. (a -> b) -> a -> b
$ [Number]
xs [Number] -> [Number] -> [Number]
forall a. [a] -> [a] -> [a]
++ Number -> [Number]
forall a. a -> [a]
repeat Number
zero
  ([Number], [Number]) -> m ([Number], [Number])
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return ([Number] -> [Number]
fill' [Number]
p1, [Number] -> [Number]
fill' [Number]
p2)

reverseBoth :: ([a],[b]) -> ([a], [b])
reverseBoth :: forall a b. ([a], [b]) -> ([a], [b])
reverseBoth ([a]
p1, [b]
p2) = ([a] -> [a]
forall a. [a] -> [a]
reverse [a]
p1, [b] -> [b]
forall a. [a] -> [a]
reverse [b]
p2)

binaryOp :: ([a] -> b) -> ([a] -> [a] -> b) -> [a] -> [a] -> b
binaryOp :: forall a b. ([a] -> b) -> ([a] -> [a] -> b) -> [a] -> [a] -> b
binaryOp [a] -> b
unary [a] -> [a] -> b
binary [a]
p1 [a]
p2 =
    case ([a]
p1,[a]
p2) of
      ([],[a]
ys) -> [a] -> b
unary [a]
ys
      ([a]
xs,[]) -> [a] -> b
unary [a]
xs
      ([a]
xs,[a]
ys) -> [a] -> [a] -> b
binary [a]
xs [a]
ys

equals,  ge,  gt  :: MonadSAT m => NumPoly -> NumPoly -> m Boolean
equals', ge', gt' :: MonadSAT m => [F.Number] -> [F.Number] -> m Boolean

equals :: forall (m :: * -> *). MonadSAT m => NumPoly -> NumPoly -> m Boolean
equals NumPoly
p1 NumPoly
p2 = NumPoly -> NumPoly -> m ([Number], [Number])
forall (m :: * -> *).
MonadSAT m =>
NumPoly -> NumPoly -> m ([Number], [Number])
fill NumPoly
p1 NumPoly
p2 m ([Number], [Number])
-> (([Number], [Number]) -> m Boolean) -> m Boolean
forall a b. m a -> (a -> m b) -> m b
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= ([Number] -> [Number] -> m Boolean)
-> ([Number], [Number]) -> m Boolean
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry [Number] -> [Number] -> m Boolean
forall (m :: * -> *).
MonadSAT m =>
[Number] -> [Number] -> m Boolean
equals'

equals' :: forall (m :: * -> *).
MonadSAT m =>
[Number] -> [Number] -> m Boolean
equals' = ([Number] -> m Boolean)
-> ([Number] -> [Number] -> m Boolean)
-> [Number]
-> [Number]
-> m Boolean
forall a b. ([a] -> b) -> ([a] -> [a] -> b) -> [a] -> [a] -> b
binaryOp (\[Number]
_ -> Bool -> m Boolean
forall (m :: * -> *). MonadSAT m => Bool -> m Boolean
B.constant Bool
True)
          (\(Number
x:[Number]
xs) (Number
y:[Number]
ys) -> do Boolean
e <- Number -> Number -> m Boolean
forall (m :: * -> *). MonadSAT m => Number -> Number -> m Boolean
F.equals Number
x Number
y
                                Boolean
rest <- [Number] -> [Number] -> m Boolean
forall (m :: * -> *).
MonadSAT m =>
[Number] -> [Number] -> m Boolean
equals' [Number]
xs [Number]
ys
                                [Boolean] -> m Boolean
forall (m :: * -> *). MonadSAT m => [Boolean] -> m Boolean
B.and [Boolean
e,Boolean
rest]
          )

ge :: forall (m :: * -> *). MonadSAT m => NumPoly -> NumPoly -> m Boolean
ge NumPoly
p1 NumPoly
p2 = NumPoly -> NumPoly -> m ([Number], [Number])
forall (m :: * -> *).
MonadSAT m =>
NumPoly -> NumPoly -> m ([Number], [Number])
fill NumPoly
p1 NumPoly
p2 m ([Number], [Number])
-> (([Number], [Number]) -> m Boolean) -> m Boolean
forall a b. m a -> (a -> m b) -> m b
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= ([Number] -> [Number] -> m Boolean)
-> ([Number], [Number]) -> m Boolean
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry [Number] -> [Number] -> m Boolean
forall (m :: * -> *).
MonadSAT m =>
[Number] -> [Number] -> m Boolean
ge' (([Number], [Number]) -> m Boolean)
-> (([Number], [Number]) -> ([Number], [Number]))
-> ([Number], [Number])
-> m Boolean
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ([Number], [Number]) -> ([Number], [Number])
forall a b. ([a], [b]) -> ([a], [b])
reverseBoth

ge' :: forall (m :: * -> *).
MonadSAT m =>
[Number] -> [Number] -> m Boolean
ge' = ([Number] -> m Boolean)
-> ([Number] -> [Number] -> m Boolean)
-> [Number]
-> [Number]
-> m Boolean
forall a b. ([a] -> b) -> ([a] -> [a] -> b) -> [a] -> [a] -> b
binaryOp (\[Number]
_ -> Bool -> m Boolean
forall (m :: * -> *). MonadSAT m => Bool -> m Boolean
B.constant Bool
True)
      (\(Number
x:[Number]
xs) (Number
y:[Number]
ys) -> do Boolean
gt <- Number -> Number -> m Boolean
forall (m :: * -> *). MonadSAT m => Number -> Number -> m Boolean
F.gt Number
x Number
y
                            Boolean
eq <- Number -> Number -> m Boolean
forall (m :: * -> *). MonadSAT m => Number -> Number -> m Boolean
F.equals Number
x Number
y
                            Boolean
rest <- [Number] -> [Number] -> m Boolean
forall (m :: * -> *).
MonadSAT m =>
[Number] -> [Number] -> m Boolean
ge' [Number]
xs [Number]
ys
                            ([Boolean] -> m Boolean) -> [m Boolean] -> m Boolean
forall (m :: * -> *) a b. Monad m => ([a] -> m b) -> [m a] -> m b
monadic [Boolean] -> m Boolean
forall (m :: * -> *). MonadSAT m => [Boolean] -> m Boolean
B.or [ Boolean -> m Boolean
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return Boolean
gt
                                         , [Boolean] -> m Boolean
forall (m :: * -> *). MonadSAT m => [Boolean] -> m Boolean
B.and [ Boolean
eq, Boolean
rest ]]
      )

gt :: forall (m :: * -> *). MonadSAT m => NumPoly -> NumPoly -> m Boolean
gt NumPoly
p1 NumPoly
p2 = NumPoly -> NumPoly -> m ([Number], [Number])
forall (m :: * -> *).
MonadSAT m =>
NumPoly -> NumPoly -> m ([Number], [Number])
fill NumPoly
p1 NumPoly
p2 m ([Number], [Number])
-> (([Number], [Number]) -> m Boolean) -> m Boolean
forall a b. m a -> (a -> m b) -> m b
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= ([Number] -> [Number] -> m Boolean)
-> ([Number], [Number]) -> m Boolean
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry [Number] -> [Number] -> m Boolean
forall (m :: * -> *).
MonadSAT m =>
[Number] -> [Number] -> m Boolean
gt' (([Number], [Number]) -> m Boolean)
-> (([Number], [Number]) -> ([Number], [Number]))
-> ([Number], [Number])
-> m Boolean
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ([Number], [Number]) -> ([Number], [Number])
forall a b. ([a], [b]) -> ([a], [b])
reverseBoth

gt' :: forall (m :: * -> *).
MonadSAT m =>
[Number] -> [Number] -> m Boolean
gt' = ([Number] -> m Boolean)
-> ([Number] -> [Number] -> m Boolean)
-> [Number]
-> [Number]
-> m Boolean
forall a b. ([a] -> b) -> ([a] -> [a] -> b) -> [a] -> [a] -> b
binaryOp (\[Number]
_ -> Bool -> m Boolean
forall (m :: * -> *). MonadSAT m => Bool -> m Boolean
B.constant Bool
False)
      (\(Number
x:[Number]
xs) (Number
y:[Number]
ys) -> do Boolean
gt <- Number -> Number -> m Boolean
forall (m :: * -> *). MonadSAT m => Number -> Number -> m Boolean
F.gt Number
x Number
y
                            Boolean
eq <- Number -> Number -> m Boolean
forall (m :: * -> *). MonadSAT m => Number -> Number -> m Boolean
F.equals Number
x Number
y
                            Boolean
rest <- [Number] -> [Number] -> m Boolean
forall (m :: * -> *).
MonadSAT m =>
[Number] -> [Number] -> m Boolean
gt' [Number]
xs [Number]
ys
                            ([Boolean] -> m Boolean) -> [m Boolean] -> m Boolean
forall (m :: * -> *) a b. Monad m => ([a] -> m b) -> [m a] -> m b
monadic [Boolean] -> m Boolean
forall (m :: * -> *). MonadSAT m => [Boolean] -> m Boolean
B.or [ Boolean -> m Boolean
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return Boolean
gt
                                         , [Boolean] -> m Boolean
forall (m :: * -> *). MonadSAT m => [Boolean] -> m Boolean
B.and [ Boolean
eq, Boolean
rest ]]
      )

add,  times, subtract, compose :: MonadSAT m => NumPoly -> NumPoly -> m NumPoly
add', times' :: MonadSAT m => [F.Number] -> [F.Number] -> m [F.Number]

add :: forall (m :: * -> *). MonadSAT m => NumPoly -> NumPoly -> m NumPoly
add (Poly [Number]
p1) (Poly [Number]
p2) = [Number] -> NumPoly
forall a. [a] -> Poly a
Poly ([Number] -> NumPoly) -> m [Number] -> m NumPoly
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> [Number] -> [Number] -> m [Number]
forall (m :: * -> *).
MonadSAT m =>
[Number] -> [Number] -> m [Number]
add' [Number]
p1 [Number]
p2
add' :: forall (m :: * -> *).
MonadSAT m =>
[Number] -> [Number] -> m [Number]
add' = ([Number] -> m [Number])
-> ([Number] -> [Number] -> m [Number])
-> [Number]
-> [Number]
-> m [Number]
forall a b. ([a] -> b) -> ([a] -> [a] -> b) -> [a] -> [a] -> b
binaryOp [Number] -> m [Number]
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return 
       (\(Number
x:[Number]
xs) (Number
y:[Number]
ys) -> do Number
z  <- Number -> Number -> m Number
forall (m :: * -> *). MonadSAT m => Number -> Number -> m Number
F.add Number
x Number
y
                             [Number]
zs <- [Number] -> [Number] -> m [Number]
forall (m :: * -> *).
MonadSAT m =>
[Number] -> [Number] -> m [Number]
add' [Number]
xs [Number]
ys
                             [Number] -> m [Number]
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return ([Number] -> m [Number]) -> [Number] -> m [Number]
forall a b. (a -> b) -> a -> b
$ Number
z Number -> [Number] -> [Number]
forall a. a -> [a] -> [a]
: [Number]
zs
       )

times :: forall (m :: * -> *). MonadSAT m => NumPoly -> NumPoly -> m NumPoly
times (Poly [Number]
p1) (Poly [Number]
p2) = [Number] -> NumPoly
forall a. [a] -> Poly a
Poly ([Number] -> NumPoly) -> m [Number] -> m NumPoly
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> [Number] -> [Number] -> m [Number]
forall (m :: * -> *).
MonadSAT m =>
[Number] -> [Number] -> m [Number]
times' [Number]
p1 [Number]
p2
times' :: forall (m :: * -> *).
MonadSAT m =>
[Number] -> [Number] -> m [Number]
times' = ([Number] -> m [Number])
-> ([Number] -> [Number] -> m [Number])
-> [Number]
-> [Number]
-> m [Number]
forall a b. ([a] -> b) -> ([a] -> [a] -> b) -> [a] -> [a] -> b
binaryOp (\[Number]
_ -> [Number] -> m [Number]
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return [])
         (\(Number
x:[Number]
xs) [Number]
ys -> do [Number]
zs   <- [Number] -> [Number] -> m [Number]
forall (m :: * -> *).
MonadSAT m =>
[Number] -> [Number] -> m [Number]
times' [Number]
xs [Number]
ys
                           ~(Number
f:[Number]
fs) <- [Number] -> (Number -> m Number) -> m [Number]
forall (t :: * -> *) (m :: * -> *) a b.
(Traversable t, Monad m) =>
t a -> (a -> m b) -> m (t b)
forM [Number]
ys ((Number -> m Number) -> m [Number])
-> (Number -> m Number) -> m [Number]
forall a b. (a -> b) -> a -> b
$ Number -> Number -> m Number
forall (m :: * -> *). MonadSAT m => Number -> Number -> m Number
F.times Number
x
                           [Number]
rest <- [Number] -> [Number] -> m [Number]
forall (m :: * -> *).
MonadSAT m =>
[Number] -> [Number] -> m [Number]
add' [Number]
zs [Number]
fs
                           [Number] -> m [Number]
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return ([Number] -> m [Number]) -> [Number] -> m [Number]
forall a b. (a -> b) -> a -> b
$ Number
f Number -> [Number] -> [Number]
forall a. a -> [a] -> [a]
: [Number]
rest
         )

subtract :: forall (m :: * -> *). MonadSAT m => NumPoly -> NumPoly -> m NumPoly
subtract (Poly [Number]
p1) (Poly [Number]
p2) = do
  [Number]
p2' <- [Number] -> (Number -> m Number) -> m [Number]
forall (t :: * -> *) (m :: * -> *) a b.
(Traversable t, Monad m) =>
t a -> (a -> m b) -> m (t b)
forM [Number]
p2 Number -> m Number
forall (m :: * -> *). MonadSAT m => Number -> m Number
F.negate
  [Number] -> NumPoly
forall a. [a] -> Poly a
Poly ([Number] -> NumPoly) -> m [Number] -> m NumPoly
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> [Number] -> [Number] -> m [Number]
forall (m :: * -> *).
MonadSAT m =>
[Number] -> [Number] -> m [Number]
add' [Number]
p1 [Number]
p2'

-- | @compose p(x) q(x) = p(q(x))@
compose :: forall (m :: * -> *). MonadSAT m => NumPoly -> NumPoly -> m NumPoly
compose (Poly [Number]
p1) (Poly [Number]
p2) = 
    let Number
p:[Number]
ps = [Number] -> [Number]
forall a. [a] -> [a]
reverse [Number]
p1
    in do
      [Number] -> NumPoly
forall a. [a] -> Poly a
Poly ([Number] -> NumPoly) -> m [Number] -> m NumPoly
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> [Number] -> [Number] -> [Number] -> m [Number]
forall {m :: * -> *}.
MonadSAT m =>
[Number] -> [Number] -> [Number] -> m [Number]
compose' [Number
p] [Number]
ps [Number]
p2

compose' :: [Number] -> [Number] -> [Number] -> m [Number]
compose' [Number]
zs = ([Number] -> m [Number])
-> ([Number] -> [Number] -> m [Number])
-> [Number]
-> [Number]
-> m [Number]
forall a b. ([a] -> b) -> ([a] -> [a] -> b) -> [a] -> [a] -> b
binaryOp (\[Number]
_  -> [Number] -> m [Number]
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return [Number]
zs)
              (\(Number
x:[Number]
xs) [Number]
ys -> do [Number]
zs' <- [Number]
zs [Number] -> [Number] -> m [Number]
forall (m :: * -> *).
MonadSAT m =>
[Number] -> [Number] -> m [Number]
`times'` [Number]
ys m [Number] -> ([Number] -> m [Number]) -> m [Number]
forall a b. m a -> (a -> m b) -> m b
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= [Number] -> [Number] -> m [Number]
forall (m :: * -> *).
MonadSAT m =>
[Number] -> [Number] -> m [Number]
add' [Number
x] 
                                [Number] -> [Number] -> [Number] -> m [Number]
compose' [Number]
zs' [Number]
xs [Number]
ys
              )

-- | @apply p x@ applies number @x@ to polynomial @p@
apply :: MonadSAT m => NumPoly -> F.Number -> m F.Number
apply :: forall (m :: * -> *). MonadSAT m => NumPoly -> Number -> m Number
apply (Poly [Number]
poly) Number
x = 
    let Number
p:[Number]
ps = [Number] -> [Number]
forall a. [a] -> [a]
reverse [Number]
poly
    in 
      (Number -> Number -> m Number) -> Number -> [Number] -> m Number
forall (t :: * -> *) (m :: * -> *) b a.
(Foldable t, Monad m) =>
(b -> a -> m b) -> b -> t a -> m b
foldM (\Number
sum -> Number -> Number -> Number -> m Number
forall (m :: * -> *).
MonadSAT m =>
Number -> Number -> Number -> m Number
F.linear Number
sum Number
x) Number
p [Number]
ps

-- | @derive p@ computes the derivation of @p@
derive :: MonadSAT m => NumPoly -> m NumPoly
derive :: forall (m :: * -> *). MonadSAT m => NumPoly -> m NumPoly
derive (Poly [Number]
p) = 
    let p' :: [(Number, Integer)]
p' = [Number] -> [Integer] -> [(Number, Integer)]
forall a b. [a] -> [b] -> [(a, b)]
zip [Number]
p [Integer
0..]
        dx :: (Number, Integer) -> m Number
dx (Number
x,Integer
e) = Integer -> m Number
forall (m :: * -> *). MonadSAT m => Integer -> m Number
F.constant Integer
e m Number -> (Number -> m Number) -> m Number
forall a b. m a -> (a -> m b) -> m b
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= Number -> Number -> m Number
forall (m :: * -> *). MonadSAT m => Number -> Number -> m Number
F.times Number
x
    in
      ([Number] -> NumPoly
forall a. [a] -> Poly a
Poly ([Number] -> NumPoly)
-> ([Number] -> [Number]) -> [Number] -> NumPoly
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> [Number] -> [Number]
forall a. Int -> [a] -> [a]
drop Int
1) ([Number] -> NumPoly) -> m [Number] -> m NumPoly
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> [(Number, Integer)]
-> ((Number, Integer) -> m Number) -> m [Number]
forall (t :: * -> *) (m :: * -> *) a b.
(Traversable t, Monad m) =>
t a -> (a -> m b) -> m (t b)
forM [(Number, Integer)]
p' (Number, Integer) -> m Number
forall {m :: * -> *}. MonadSAT m => (Number, Integer) -> m Number
dx