referring to the Serial instances in http://hackage.haskell.org/package/smallcheck : the idea is that series d gives all objects of depth <= d. depth of a term from an algebraic data type is the standard "depth" concept for trees (maximum nesting of constructors = longest path from root to node) 1. why are the tuple constructors treated differently? I'd expect depth (x,y) = succ $ max (depth x) (depth y) but the succ is missing. 2. why depth and not size (= total number of constructors)? it seems that the number of objects (trees) of given depth rises much more drastically than number of trees of given size. just wondering - J.W.
Hi, I'm cc'ing the people behind smallcheck, who can give definitive answers.
1. why are the tuple constructors treated differently? I'd expect depth (x,y) = succ $ max (depth x) (depth y) but the succ is missing.
I think this was a design choice. Some people would consider: data Foo = Foo a b and data Foo = Foo (a,b) to be roughly the same - in some way the tuple is just to group things up, but it never is any structure by itself, since any structure it has is limited by the type system. But it could have been defined the other way.
2. why depth and not size (= total number of constructors)? it seems that the number of objects (trees) of given depth rises much more drastically than number of trees of given size.
That seems harder to generate terms compositionally. To create all terms of depth n+1 you just glue together all terms of depth n, but to create terms of size n+1 you need to glue 1 with n, 2 with n-1 etc. Thanks, Neil
2. why depth and not size (= total number of constructors)?
That seems harder to generate terms compositionally. To create all terms of depth n+1 you just glue together all terms of depth n, but to create terms of size n+1 you need to glue 1 with n, 2 with n-1 etc.
So? One would fear that this is inefficient because then these series (of smaller sizes) would have to be generated several times. But no, instead of class Serial a where series :: Int -> [a] one could "cache" these into series' :: [[a]] such that series k == series' !! k actually, series k == [ 0 .. k ] >>= ( series' !! ) because I'd want series' do be disjoint (each object has only one size). That should be doable by a simple rewrite of (some parts) of the library. I'm going to find a clever student to whom I could assign this ... Are there any standard test cases (i.e., they work nicely with the original Smallcheck and must continue to work with any modified version)? Best - Johannes.
participants (2)
-
Johannes Waldmann -
Neil Mitchell