[Agda] how to use monoid solver and how to derive a concept
monoid if assume we do not know monoid
Mandy Martino
tesleft at hotmail.com
Tue Dec 15 12:14:57 CET 2015
Hi Sergei ,
i find this method from book polynomials completion book, mention fst and snd for And and Or
then edit code of all combinations of tree with fst and snd, then it can generate all valid relations
for transitive axiomeval (Mode (Mode (Meaf 1.0) And (Meaf 2.0)) Or (Mode (Meaf 2.0) And (Meaf 3.0))) > eval (Mode (Meaf 1.0) And (Meaf 3.0))
then i guess the criteria for valid axiom may be eval x > eval y
i believe the book so i guess this will work well, if this is wrong, please verify it.
now, you know that how i can try all combinations of equivalence relations by replacing transitive with new relation.
:l trees.hslet allparams = replicateM 3 [1.0, 2.0]let alltrees = [getAllTrees c | x <- allparams, c <- [x]]eval(alltrees!!1!!1) == eval(alltrees!!1!!1)let alltrees1 = forM_ [0..(sizeoflist alltrees)] $ \i -> forM_ [0..(sizeoflist (alltrees!!i))] $ \j -> [(alltrees!!i!!j, eval(alltrees!!i!!j)== eval(alltrees!!i!!j))]--let bb = filter (\n -> if n != () then snd n == True) alltrees1
allexprs :: [ Mree Double ]let allexprs = concat alltrees -- a list of all the Mrees in alterslet alltrees2 = [ ((x,y), eval x > eval y) | x <- allexprs, y <- allexprs]let bb = [ (x,y) | ((x,y), True) <- alltrees2 ]
eval (Mode (Mode (Meaf 1.0) And (Meaf 2.0)) Or (Mode (Meaf 2.0) And (Meaf 3.0))) > eval (Mode (Meaf 1.0) And (Meaf 3.0))
trees.hs
import Data.Listimport Control.Monadimport Math.Combinatimport System.IO
data Operation = And | Or | MA | MB | Impl deriving Show
data Mree x = Meaf x | Mode (Mree x) Operation (Mree x) deriving Show
splits :: [a] -> [([a], [a])]splits xs = zip (inits xs) (tails xs)
getAllTrees :: [a] -> [Mree a]getAllTrees [] = []getAllTrees [x] = return $ Meaf xgetAllTrees xs = do (left, right) <- splits xs guard $ not (null left) && not (null right) leftT <- getAllTrees left rightT <- getAllTrees right op <- [And, Or] return $ Mode leftT op rightT
eval :: Mree Double -> Doubleeval (Meaf x) = xeval (Mode l And r) = eval leval (Mode l Or r) = eval r
peval :: Mree Double -> Stringpeval (Meaf x) = show x :: Stringpeval (Mode l And r) = "(" ++ peval l ++ "^" ++ peval r ++ ")"peval (Mode l Or r) = "(" ++ peval l ++ "V" ++ peval r ++ ")"
sizeoflist :: [a] -> Intsizeoflist = length
eeval1 :: Mree Float -> Floateeval1 (Meaf x) = xeeval1 (Mode l And r) = eeval1 l * eeval1 reeval1 (Mode l Or r) = eeval1 l + eeval1 reeval1 (Mode l MA r) = eeval1 l + eeval1 reeval1 (Mode l MB r) = eeval1 l + eeval1 r
eeval2 :: Mree Float -> Floateeval2 (Meaf x) = xeeval2 (Mode l And r) = eeval2 l * eeval2 reeval2 (Mode l Or r) = eeval2 l + eeval2 reeval2 (Mode l MA r) = eeval2 l + eeval2 reeval2 (Mode l MB r) = eeval2 l * eeval2 r
eeval3 :: Mree Float -> Floateeval3 (Meaf x) = xeeval3 (Mode l And r) = eeval3 l * eeval3 reeval3 (Mode l Or r) = eeval3 l + eeval3 reeval3 (Mode l MA r) = eeval3 l * eeval3 reeval3 (Mode l MB r) = eeval3 l + eeval3 r
eeval4 :: Mree Float -> Floateeval4 (Meaf x) = xeeval4 (Mode l And r) = eeval4 l * eeval4 reeval4 (Mode l Or r) = eeval4 l + eeval4 reeval4 (Mode l MA r) = eeval4 l * eeval4 reeval4 (Mode l MB r) = eeval4 l * eeval4 r
mulVV :: Num a => [a] -> [a] -> amulVV u v = sum $ zipWith (*) u v
mulMV :: Num a => [[a]] -> [a] -> [a]mulMV m v = map (mulVV v) m
mulMM :: Num a => [[a]] -> [[a]] -> [[a]]mulMM m n = transpose $ map (mulMV m) $ transpose $ n
msize :: [[Float]] -> Intmsize = length
mapMatrix :: (Float -> Float) -> [[Float]] -> [[Float]]mapMatrix f = map (map f)
coords :: [[Float]] -> [[(Int, Int)]]coords = zipWith (map . (,)) [0..] . map (zipWith const [0..])
delmatrix :: Int -> Int -> [[Float]] -> [[Float]]delmatrix i j = dellist i . map (dellist j) where dellist i xs = take i xs ++ drop (i + 1) xs
determinant :: [[Float]] -> Floatdeterminant m | msize m == 1 = head (head m) | otherwise = sum $ zipWith addition [0..] m where addition i (x:_) = x * cofactor i 0 m
cofactor :: Int -> Int -> [[Float]] -> Floatcofactor i j m = ((-1.0) ** fromIntegral (i + j)) * determinant (delmatrix i j m)
cofactorM :: [[Float]] -> [[Float]]cofactorM m = map (map (\(i,j) -> cofactor j i m)) $ coords m
inversem :: [[Float]] -> [[Float]]inversem m = mapMatrix (* recip det) $ cofactorM m where det = determinant m
Regards,
Martin
> Subject: Re: [Agda] how to use monoid solver and how to derive a concept monoid if assume we do not know monoid
> From: mechvel at botik.ru
> To: tesleft at hotmail.com
> CC: agda at lists.chalmers.se
> Date: Tue, 15 Dec 2015 00:29:32 +0400
>
> On Mon, 2015-12-14 at 19:21 +0800, Mandy Martino wrote:
>
> > Hi ,
> > i find many places define identity, symmetric and transitive, how
> > to use monoid solve and which can it solve?
> >
> >
> > i would like to define a new set of equivalence relations, is
> > there a light weight version of monoid?
>
> See in Wikipedia what is a monoid.
> Monoid in Standard library is adequate, it cannot be any more
> "light weight".
>
> Monid has the axioms of
> (1) associativity for _∙_, (2) identity (ε).
>
>
> > how to use monoid solve and which can it solve?
>
> Earlier I tried SemiringSolver for Nat.
> And I guess that MonoidSolver uses a similar principle of reduction to
> a normal form
> (let people correct me, if I mistake).
>
> For monoid:
> having expressions e1 and e2,
> a proof for the equality
> e1 ≈ e2 (E)
>
> can be searched by applying the `solve' function.
> `solve' brings e1 and e2 to their certain normal forms e1' and e2'.
> This is done by moving parentheses (by using the associativity law),
> and canceling ε by using the identity law.
> Then, if e1' and e2' coincide
> (are equal by Equivalence.refl contained in the setoid),
> then the result of `solve' is a proof for (E).
> Otherwise, some other proof may exist or not.
>
> In various instances of Monoid there may exist many equations or
> statements which can be proved but are not proved by MonoidSolver.
>
> Example of a proof:
> I expect that `solve' will bring e1 = (x ∙ (e ∙ x)) ∙ (y ∙ e)
> and e2 = (e ∙ (x ∙ x)) ∙ y
>
> by using the laws of associativity and identity to the same expression
>
> x ∙ (x ∙ y).
> And this proves the equality
>
> (x ∙ (e ∙ x)) ∙ (y ∙ e) ≈ (e ∙ (x ∙ x)) ∙ y
>
> for any Monoid.
>
> I do not know how precisely MonoidSolver is used.
> But I have an example of using SemiringSolver, and I expect that
> MonoidSolver has a similar usage.
>
> For Nat (n : Nat) :
>
> open import Data.Nat.Properties using (module SemiringSolver)
>
> open SemiringSolver using (solve; _:=_; con; _:+_; _:*_)
>
> e : suc (suc (n + n)) ≡ 2 * suc n
> e = solve 1 (\n → con 1 :+ (con 1 :+ (n :+ n)) :=
> (con 2) :* (con 1 :+ n)
> )
> PE.refl n
>
> I guess that `solve' does the following. It has
>
> e1 = 1 + (1 + (n + n))
> e2 = (1 + (1 + 0)) * (1 + n),
>
> and it brings both terms to this normal form:
> 1 + (1 + (n + n)).
>
> It is done only by using the axioms of an arbitrary (commutative) ring.
>
> I have arranged this by looking into the source of Standard library,
> where it uses SemiringSolver, I just mimic the usage.
>
> I guess that under this `solve',
> `con' is a tag for a constant, `:' is a tag for an operator,
> all other items (in this case it is `n') are variables in a term.
>
> I expect that MonoidSolver has a similar usage.
>
>
> > assume we do not know monoid, how to build a concept such as
> > monoid based on custom equivalence relations?
>
> I do not know what is a custom equivalence relation.
> So I cannot tell.
>
> Regards,
>
> ------
> Sergei
>
>
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.chalmers.se/pipermail/agda/attachments/20151215/03a93ce3/attachment-0001.html
More information about the Agda
mailing list