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
