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

[Cetin Sert]

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 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
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20080221/bc99625a/attachment.htm