# [Haskell-cafe] what is the fastest way to extract variables from a proposition?

Cetin Sert cetin.sert at gmail.com
Wed Feb 20 23:54:01 EST 2008

```sert at elite:~/workspace/Haskell-1/bin\$ time ./theResult sert
1000001

real    0m1.384s
user    0m1.148s
sys     0m0.112s

sert at elite:~/workspace/Haskell-1/bin\$ time ./theResult bromage
1000001

real    0m2.240s
user    0m1.972s
sys     0m0.176s

sert at elite:~/workspace/Haskell-1/bin\$ time ./theResult bromage
10000001

real    0m59.875s
user    0m58.080s
sys     0m1.656s

sert at elite:~/workspace/Haskell-1/bin\$ time ./theResult sert
10000001

real    0m32.043s
user    0m30.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 <derek.a.elkins at gmail.com> 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 10000000))
> > real    0m3.290s
> > user    0m3.152s
> > sys     0m0.020s
> >
> > main = do print ((length ∘ vars_) (plong 10000000))
> > real    0m3.732s
> > user    0m3.680s
> > sys     0m0.024s
> >
> > --                         vrsn=varsBromage
> > main = do print ((length ∘ vrsn) (plong 10000000))
> > real    0m4.164s
> > user    0m4.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, ajb at spamcop.net <ajb at spamcop.net> wrote:
> >         G'day all.
> >
> >
> >         Quoting Cetin Sert <cetin.sert at gmail.com>:
> >
> >         > -- 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
> >
> >         _______________________________________________
> >
> > _______________________________________________