[Haskell-cafe] what is the fastest way to extract variables from a proposition?
-- proposition data Prp a = Var a | Not (Prp a) | Or (Prp a) (Prp a) | And (Prp a) (Prp a) | Imp (Prp a) (Prp a) | Xor (Prp a) (Prp a) | Eqv (Prp a) (Prp a) | Cns Bool deriving (Show, Eq) -- Here are to variable extraction methods -- variable extraction reference imp. -- Graham Hutton: Programming in Haskell, 107 vars_ :: Prp a → [a] vars_ (Cns _) = [] vars_ (Var x) = [x] vars_ (Not p) = vars_ p vars_ (Or p q) = vars_ p ++ vars_ q vars_ (And p q) = vars_ p ++ vars_ q vars_ (Imp p q) = vars_ p ++ vars_ q vars_ (Xor p q) = vars_ p ++ vars_ q vars_ (Eqv p q) = vars_ p ++ vars_ q -- variable extraction new * this is faster vars :: Prp a → [a] vars p = evs [p] where evs [] = [] evs (Cns _ :ps) = [] evs (Var x :ps) = x:evs ps evs (Not p :ps) = evs (p:ps) evs (Or p q:ps) = evs (p:q:ps) evs (And p q:ps) = evs (p:q:ps) evs (Imp p q:ps) = evs (p:q:ps) evs (Xor p q:ps) = evs (p:q:ps) evs (Eqv p q:ps) = evs (p:q:ps) -- for : Not (Imp (Or (Var 'p') (Var 'q')) (Var p)) -- vars_: ['p','q','p'] -- vars : ['p','q','p'] -- order and the fact that 'p' appears twice being irrelevant: -- is there an even faster way to do this? -- -- Cetin Sert -- www.corsis.de ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] what is the fastest way to extract variables from a proposition?
It depends what you mean by faster; more efficient (runtime) or less typing (programmer time!) For the former, you have basically the best implementation there is; you are basically encoding the continuation of (++) into the accumulating list of arguments to evs. You might want to consider difference lists to simplify the definition, however; the performance should be comparable: newtype DList a = DL ([a] - [a]) dlToList :: DList a - [a] dlToList (DL l) = l [] dlSingleton :: a - DList a dlSingleton = DL . (:) dlConcat :: DList a - DList a - DList a dlConcat (DL l1) (DL l2) = DL (l1 . l2) varsDL :: Prp a - DList a varsDL (Var a) = dlSingleton a varsDL (Not a) = varsDL a varsDL (Or a b) = varsDL a `dlConcat` varsDL b -- etc. If you want less typing, consider some form of generics programming such as using Scrap your Boilerplate; see http://www.cs.vu.nl/boilerplate/ data Prp a = ... deriving (Eq, Show, Data, Typeable) -- note that this gives the wrong result for Prp Bool because of Cns. -- this is fixable, see http://www.cs.vu.nl/boilerplate/testsuite/foldTree.hs varsGeneric :: forall a. Typeable a = Prp a - [a] varsGeneric = listify (\x - case (x :: a) of _ - True) -- ryan On 2/20/08, Cetin Sert [EMAIL PROTECTED] wrote: -- proposition data Prp a = Var a | Not (Prp a) | Or (Prp a) (Prp a) | And (Prp a) (Prp a) | Imp (Prp a) (Prp a) | Xor (Prp a) (Prp a) | Eqv (Prp a) (Prp a) | Cns Bool deriving (Show, Eq) -- Here are to variable extraction methods -- variable extraction reference imp. -- Graham Hutton: Programming in Haskell, 107 vars_ :: Prp a → [a] vars_ (Cns _) = [] vars_ (Var x) = [x] vars_ (Not p) = vars_ p vars_ (Or p q) = vars_ p ++ vars_ q vars_ (And p q) = vars_ p ++ vars_ q vars_ (Imp p q) = vars_ p ++ vars_ q vars_ (Xor p q) = vars_ p ++ vars_ q vars_ (Eqv p q) = vars_ p ++ vars_ q -- variable extraction new * this is faster vars :: Prp a → [a] vars p = evs [p] where evs [] = [] evs (Cns _ :ps) = [] evs (Var x :ps) = x:evs ps evs (Not p :ps) = evs (p:ps) evs (Or p q:ps) = evs (p:q:ps) evs (And p q:ps) = evs (p:q:ps) evs (Imp p q:ps) = evs (p:q:ps) evs (Xor p q:ps) = evs (p:q:ps) evs (Eqv p q:ps) = evs (p:q:ps) -- for : Not (Imp (Or (Var 'p') (Var 'q')) (Var p)) -- vars_: ['p','q','p'] -- vars : ['p','q','p'] -- order and the fact that 'p' appears twice being irrelevant: -- is there an even faster way to do this? -- -- Cetin Sert -- www.corsis.de ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] what is the fastest way to extract variables from a proposition?
G'day all.
Quoting Cetin Sert [EMAIL PROTECTED]:
-- proposition
data Prp a = Var a
| Not (Prp a)
| Or (Prp a) (Prp a)
| And (Prp a) (Prp a)
| Imp (Prp a) (Prp a)
| Xor (Prp a) (Prp a)
| Eqv (Prp a) (Prp a)
| Cns Bool
deriving (Show, Eq)
This is probably the fastest:
vars :: Prp a - [a]
vars p = vars' p []
where
vars' (Var a) = (a:)
vars' (Not p) = vars' p
vars' (Or l r) = vars' l . vars' r
{- etc -}
vars' (Cns _) = id
Cheers,
Andrew Bromage
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] what is the fastest way to extract variables from a proposition?
plong 0 = Var 0
plong n | even n= Or (Var n) (plong (n-1))
| otherwise = And (Var n) (plong (n-1))
main = do print ((length ∘ vars) (plong 1000))
real0m3.290s
user0m3.152s
sys 0m0.020s
main = do print ((length ∘ vars_) (plong 1000))
real0m3.732s
user0m3.680s
sys 0m0.024s
-- vrsn=varsBromage
main = do print ((length ∘ vrsn) (plong 1000))
real0m4.164s
user0m4.128s
sys 0m0.008s
ghc -fglasgow-exts -O2
ghc 6.8.2
@Andrew:
It is astonishing to see that your version actually performs the worst (at
least on my machine). By looking at your code I had also thought that yours
would be the fastest in terms of runtime performance, it was also exactly
what I tried but failed to get to here on my own. Maybe future ghc versions
will change this in favour of your version.
I would like to have someone test it on another machine though:
fetch: svn co https://okitsune.svn.sourceforge.net/svnroot/okitsune .
build: ghc -fglasgow-exts -O2 Common.hs Propositions.hs Test.hs
testS: time ./a.out sert
testH: time ./a.out hutton
testB: time ./a.out bromage
Best regards,
Cetin Sert.
On 21/02/2008, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote:
G'day all.
Quoting Cetin Sert [EMAIL PROTECTED]:
-- proposition
data Prp a = Var a
| Not (Prp a)
| Or (Prp a) (Prp a)
| And (Prp a) (Prp a)
| Imp (Prp a) (Prp a)
| Xor (Prp a) (Prp a)
| Eqv (Prp a) (Prp a)
| Cns Bool
deriving (Show, Eq)
This is probably the fastest:
vars :: Prp a - [a]
vars p = vars' p []
where
vars' (Var a) = (a:)
vars' (Not p) = vars' p
vars' (Or l r) = vars' l . vars' r
{- etc -}
vars' (Cns _) = id
Cheers,
Andrew Bromage
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] what is the fastest way to extract variables from a proposition?
On Thu, 2008-02-21 at 05:10 +0100, Cetin Sert wrote:
plong 0 = Var 0
plong n | even n= Or (Var n) (plong (n-1))
| otherwise = And (Var n) (plong (n-1))
compare the times again but with plong as follows:
plong 0 = Var 0
plong n | even n = Or (plong (n-1)) (Var n)
| otherwise = And (plong (n-1)) (Var n)
main = do print ((length ∘ vars) (plong 1000))
real0m3.290s
user0m3.152s
sys 0m0.020s
main = do print ((length ∘ vars_) (plong 1000))
real0m3.732s
user0m3.680s
sys 0m0.024s
-- vrsn=varsBromage
main = do print ((length ∘ vrsn) (plong 1000))
real0m4.164s
user0m4.128s
sys 0m0.008s
ghc -fglasgow-exts -O2
ghc 6.8.2
@Andrew:
It is astonishing to see that your version actually performs the worst
(at least on my machine). By looking at your code I had also thought
that yours would be the fastest in terms of runtime performance, it
was also exactly what I tried but failed to get to here on my own.
Maybe future ghc versions will change this in favour of your version.
I would like to have someone test it on another machine though:
fetch: svn co https://okitsune.svn.sourceforge.net/svnroot/okitsune .
build: ghc -fglasgow-exts -O2 Common.hs Propositions.hs Test.hs
testS: time ./a.out sert
testH: time ./a.out hutton
testB: time ./a.out bromage
Best regards,
Cetin Sert.
On 21/02/2008, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote:
G'day all.
Quoting Cetin Sert [EMAIL PROTECTED]:
-- proposition
data Prp a = Var a
| Not (Prp a)
| Or (Prp a) (Prp a)
| And (Prp a) (Prp a)
| Imp (Prp a) (Prp a)
| Xor (Prp a) (Prp a)
| Eqv (Prp a) (Prp a)
| Cns Bool
deriving (Show, Eq)
This is probably the fastest:
vars :: Prp a - [a]
vars p = vars' p []
where
vars' (Var a) = (a:)
vars' (Not p) = vars' p
vars' (Or l r) = vars' l . vars' r
{- etc -}
vars' (Cns _) = id
Cheers,
Andrew Bromage
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] what is the fastest way to extract variables from a proposition?
G'day all. Quoting Cetin Sert [EMAIL PROTECTED]: It is astonishing to see that your version actually performs the worst (at least on my machine). On your example, I'm not surprised: plong 0 = Var 0 plong n | even n= Or (Var n) (plong (n-1)) | otherwise = And (Var n) (plong (n-1)) This is effectively a singly linked list. I would expect my (well, I didn't invent it) to work better on something that didn't have this unique structure, such as: test 0 = Var 0 test n | even n= Or (Var n) (test (n-1)) | otherwise = And (test (n-1)) (Var n) Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] what is the fastest way to extract variables from a proposition?
[EMAIL PROTECTED]:~/workspace/Haskell-1/bin$ time ./theResult sert
101
real0m1.384s
user0m1.148s
sys 0m0.112s
[EMAIL PROTECTED]:~/workspace/Haskell-1/bin$ time ./theResult bromage
101
real0m2.240s
user0m1.972s
sys 0m0.176s
[EMAIL PROTECTED]:~/workspace/Haskell-1/bin$ time ./theResult bromage
1001
real0m59.875s
user0m58.080s
sys 0m1.656s
[EMAIL PROTECTED]:~/workspace/Haskell-1/bin$ time ./theResult sert
1001
real0m32.043s
user0m30.930s
sys 0m0.992s
Hutton seems to fail miserably in both lengths here o_O
I was not aware of the effect of structures on performance.
Thanks for reminding me!
Best Regards,
Cetin Sert
On 21/02/2008, Derek Elkins [EMAIL PROTECTED] wrote:
On Thu, 2008-02-21 at 05:10 +0100, Cetin Sert wrote:
plong 0 = Var 0
plong n | even n= Or (Var n) (plong (n-1))
| otherwise = And (Var n) (plong (n-1))
compare the times again but with plong as follows:
plong 0 = Var 0
plong n | even n = Or (plong (n-1)) (Var n)
| otherwise = And (plong (n-1)) (Var n)
main = do print ((length ∘ vars) (plong 1000))
real0m3.290s
user0m3.152s
sys 0m0.020s
main = do print ((length ∘ vars_) (plong 1000))
real0m3.732s
user0m3.680s
sys 0m0.024s
-- vrsn=varsBromage
main = do print ((length ∘ vrsn) (plong 1000))
real0m4.164s
user0m4.128s
sys 0m0.008s
ghc -fglasgow-exts -O2
ghc 6.8.2
@Andrew:
It is astonishing to see that your version actually performs the worst
(at least on my machine). By looking at your code I had also thought
that yours would be the fastest in terms of runtime performance, it
was also exactly what I tried but failed to get to here on my own.
Maybe future ghc versions will change this in favour of your version.
I would like to have someone test it on another machine though:
fetch: svn co https://okitsune.svn.sourceforge.net/svnroot/okitsune .
build: ghc -fglasgow-exts -O2 Common.hs Propositions.hs Test.hs
testS: time ./a.out sert
testH: time ./a.out hutton
testB: time ./a.out bromage
Best regards,
Cetin Sert.
On 21/02/2008, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote:
G'day all.
Quoting Cetin Sert [EMAIL PROTECTED]:
-- proposition
data Prp a = Var a
| Not (Prp a)
| Or (Prp a) (Prp a)
| And (Prp a) (Prp a)
| Imp (Prp a) (Prp a)
| Xor (Prp a) (Prp a)
| Eqv (Prp a) (Prp a)
| Cns Bool
deriving (Show, Eq)
This is probably the fastest:
vars :: Prp a - [a]
vars p = vars' p []
where
vars' (Var a) = (a:)
vars' (Not p) = vars' p
vars' (Or l r) = vars' l . vars' r
{- etc -}
vars' (Cns _) = id
Cheers,
Andrew Bromage
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] what is the fastest way to extract variables from a proposition?
I would expect my (well, I didn't invent it) to work better on something that didn't have this unique structure, such as: test 0 = Var 0 test n | even n= Or (Var n) (test (n-1)) | otherwise = And (test (n-1)) (Var n) for some reason this still does not perform as well as it should o__O I think function composition might somehow be the bottleneck behind this. --with plong 0 = Var 0 plong n | even n= Or (Var n) (plong (n-1)) | otherwise = And (plong (n-1)) (Var n) --and n = 100 [EMAIL PROTECTED]:~/workspace/Haskell-1/bin$ time ./theResult sert 101 real0m0.692s user0m0.624s sys 0m0.040s [EMAIL PROTECTED]:~/workspace/Haskell-1/bin$ time ./theResult sert 101 real0m0.696s user0m0.644s sys 0m0.036s [EMAIL PROTECTED]:~/workspace/Haskell-1/bin$ time ./theResult sert 101 real0m0.840s user0m0.744s sys 0m0.052s [EMAIL PROTECTED]:~/workspace/Haskell-1/bin$ time ./theResult bromage 101 real0m1.561s user0m1.360s sys 0m0.100s [EMAIL PROTECTED]:~/workspace/Haskell-1/bin$ time ./theResult bromage 101 real0m1.692s user0m1.392s sys 0m0.136s [EMAIL PROTECTED]:~/workspace/Haskell-1/bin$ time ./theResult bromage 101 real0m1.959s user0m1.580s sys 0m0.116s Best Regards, Cetin Sert On 21/02/2008, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote: G'day all. Quoting Cetin Sert [EMAIL PROTECTED]: It is astonishing to see that your version actually performs the worst (at least on my machine). On your example, I'm not surprised: plong 0 = Var 0 plong n | even n= Or (Var n) (plong (n-1)) | otherwise = And (Var n) (plong (n-1)) This is effectively a singly linked list. I would expect my (well, I didn't invent it) to work better on something that didn't have this unique structure, such as: test 0 = Var 0 test n | even n= Or (Var n) (test (n-1)) | otherwise = And (test (n-1)) (Var n) Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
