Quantcast

Quickcheck: pushing element onto stack increases stack size

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Quickcheck: pushing element onto stack increases stack size

Patrick Browne
Hi,
I am trying to use Quickcheck to check that pushing an element increases the size of a stack.
Something like:
prop_size2 x s = (size (Push x s)) > (size s)

Is this possible? Below is my effort using an empty stack.
Thanks in advance,
Pat


module Stack (empty, push, pop, top, isEmpty) where
import Test.QuickCheck

data Stack a = Empty | Push a (Stack a) deriving  Show

empty :: Stack a
empty = Empty

push :: a -> Stack a -> Stack a
push x ss = Push x ss
 
pop :: Stack a -> Stack a
pop Empty = error "pop emptyStack"
pop (Push x ss) = ss
 
top :: Stack a -> a
top Empty = error "top emptyStack"
top (Push x ss) = x

isEmpty :: Stack a -> Bool
isEmpty Empty = True
isEmpty (Push x ss) = False


size :: (Stack a) -> Int
size Empty = 0 
size (Push x ss) = succ (size ss) 


prop_size x  = (size (Push x Empty)) > (size Empty)

This email originated from DIT. If you received this email in error, please delete it from your system. Please note that if you are not the named addressee, disclosing, copying, distributing or taking any action based on the contents of this email or attachments is prohibited. www.dit.ie

Is ó ITBÁC a tháinig an ríomhphost seo. Má fuair tú an ríomhphost seo trí earráid, scrios de do chóras é le do thoil. Tabhair ar aird, mura tú an seolaí ainmnithe, go bhfuil dianchosc ar aon nochtadh, aon chóipeáil, aon dáileadh nó ar aon ghníomh a dhéanfar bunaithe ar an ábhar atá sa ríomhphost nó sna hiatáin seo. www.dit.ie

Tá ITBÁC ag aistriú go Gráinseach Ghormáin – DIT is on the move to Grangegorman


_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Quickcheck: pushing element onto stack increases stack size

David McBride
First you need a way to generate an arbitrary stack.  Here's a simple
method that just gives you a 50% chance at each level of generating an
extra layer.

instance Arbitrary a => Arbitrary (Stack a) where
  arbitrary = oneof [return Empty, Push <$> arbitrary <*> arbitrary ]

prop_size_succeeds x s = size (Push x s) > size s
prop_size_fails x s = size s > size Empty

>quickCheck prop_size_fails
*** Failed! Falsifiable (after 6 tests):
()
Empty


On Thu, May 11, 2017 at 3:38 PM, PATRICK BROWNE <[hidden email]> wrote:

> Hi,
> I am trying to use Quickcheck to check that pushing an element increases the
> size of a stack.
> Something like:
> prop_size2 x s = (size (Push x s)) > (size s)
>
> Is this possible? Below is my effort using an empty stack.
> Thanks in advance,
> Pat
>
>
> module Stack (empty, push, pop, top, isEmpty) where
> import Test.QuickCheck
>
> data Stack a = Empty | Push a (Stack a) deriving  Show
>
> empty :: Stack a
> empty = Empty
>
> push :: a -> Stack a -> Stack a
> push x ss = Push x ss
>
> pop :: Stack a -> Stack a
> pop Empty = error "pop emptyStack"
> pop (Push x ss) = ss
>
> top :: Stack a -> a
> top Empty = error "top emptyStack"
> top (Push x ss) = x
>
> isEmpty :: Stack a -> Bool
> isEmpty Empty = True
> isEmpty (Push x ss) = False
>
>
> size :: (Stack a) -> Int
> size Empty = 0
> size (Push x ss) = succ (size ss)
>
>
> prop_size x  = (size (Push x Empty)) > (size Empty)
>
> This email originated from DIT. If you received this email in error, please
> delete it from your system. Please note that if you are not the named
> addressee, disclosing, copying, distributing or taking any action based on
> the contents of this email or attachments is prohibited. www.dit.ie
>
> Is ó ITBÁC a tháinig an ríomhphost seo. Má fuair tú an ríomhphost seo trí
> earráid, scrios de do chóras é le do thoil. Tabhair ar aird, mura tú an
> seolaí ainmnithe, go bhfuil dianchosc ar aon nochtadh, aon chóipeáil, aon
> dáileadh nó ar aon ghníomh a dhéanfar bunaithe ar an ábhar atá sa ríomhphost
> nó sna hiatáin seo. www.dit.ie
>
> Tá ITBÁC ag aistriú go Gráinseach Ghormáin – DIT is on the move to
> Grangegorman
>
>
> _______________________________________________
> Beginners mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Quickcheck: pushing element onto stack increases stack size

Patrick Browne
David,
Thanks for the help.
Much appreciated,
Pat

On 11 May 2017 at 21:00, David McBride <[hidden email]> wrote:
First you need a way to generate an arbitrary stack.  Here's a simple
method that just gives you a 50% chance at each level of generating an
extra layer.

instance Arbitrary a => Arbitrary (Stack a) where
  arbitrary = oneof [return Empty, Push <$> arbitrary <*> arbitrary ]

prop_size_succeeds x s = size (Push x s) > size s
prop_size_fails x s = size s > size Empty

>quickCheck prop_size_fails
*** Failed! Falsifiable (after 6 tests):
()
Empty


On Thu, May 11, 2017 at 3:38 PM, PATRICK BROWNE <[hidden email]> wrote:
> Hi,
> I am trying to use Quickcheck to check that pushing an element increases the
> size of a stack.
> Something like:
> prop_size2 x s = (size (Push x s)) > (size s)
>
> Is this possible? Below is my effort using an empty stack.
> Thanks in advance,
> Pat
>
>
> module Stack (empty, push, pop, top, isEmpty) where
> import Test.QuickCheck
>
> data Stack a = Empty | Push a (Stack a) deriving  Show
>
> empty :: Stack a
> empty = Empty
>
> push :: a -> Stack a -> Stack a
> push x ss = Push x ss
>
> pop :: Stack a -> Stack a
> pop Empty = error "pop emptyStack"
> pop (Push x ss) = ss
>
> top :: Stack a -> a
> top Empty = error "top emptyStack"
> top (Push x ss) = x
>
> isEmpty :: Stack a -> Bool
> isEmpty Empty = True
> isEmpty (Push x ss) = False
>
>
> size :: (Stack a) -> Int
> size Empty = 0
> size (Push x ss) = succ (size ss)
>
>
> prop_size x  = (size (Push x Empty)) > (size Empty)
>
> This email originated from DIT. If you received this email in error, please
> delete it from your system. Please note that if you are not the named
> addressee, disclosing, copying, distributing or taking any action based on
> the contents of this email or attachments is prohibited. www.dit.ie
>
> Is ó ITBÁC a tháinig an ríomhphost seo. Má fuair tú an ríomhphost seo trí
> earráid, scrios de do chóras é le do thoil. Tabhair ar aird, mura tú an
> seolaí ainmnithe, go bhfuil dianchosc ar aon nochtadh, aon chóipeáil, aon
> dáileadh nó ar aon ghníomh a dhéanfar bunaithe ar an ábhar atá sa ríomhphost
> nó sna hiatáin seo. www.dit.ie
>
> Tá ITBÁC ag aistriú go Gráinseach Ghormáin – DIT is on the move to
> Grangegorman
>
>
> _______________________________________________
> Beginners mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>


This email originated from DIT. If you received this email in error, please delete it from your system. Please note that if you are not the named addressee, disclosing, copying, distributing or taking any action based on the contents of this email or attachments is prohibited. www.dit.ie

Is ó ITBÁC a tháinig an ríomhphost seo. Má fuair tú an ríomhphost seo trí earráid, scrios de do chóras é le do thoil. Tabhair ar aird, mura tú an seolaí ainmnithe, go bhfuil dianchosc ar aon nochtadh, aon chóipeáil, aon dáileadh nó ar aon ghníomh a dhéanfar bunaithe ar an ábhar atá sa ríomhphost nó sna hiatáin seo. www.dit.ie

Tá ITBÁC ag aistriú go Gráinseach Ghormáin – DIT is on the move to Grangegorman


_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Loading...