Questions Asked

Q: On the quickcheck verification are we suppose to use the smooth_perms function given and compare the result with our defined function that uses the tree, or is it suppose to just use our implementation and verify that all elements generated are a possible permutation of the list and there are no more smooth permutations?! Also is it suppose to fuse those three functions into one and test that one or testing a pipeline such as toList $ (prune n) $ fromList is fine? My concern is because quickcheck is taking a long time to check when i compare my function with the given because it's generating lists with more than 6 or 7 elements. Since smooth_perms is using filter when there are no smooth permutations the result is [], and when we give [] as an argument (with some number) to smooth_perms it produces [[]], are we suppose to mimic this result as well? I'm asking because with my current Tree data (newtype Tree a = Branch [(a,Tree a)], I would have to distinguish Branch [] when I receive [] as arg. to produce [[]] and Branch [] after "pronning" to produce []. I manage to solve this, but the solution is not as elegant. This is detail that could make my property to fail, since [] /= [[]].

A: First question: I have given an specification, by giving an inefficient implementation. You may use this as the one to test against. It ouwl dbe nice to test the fused version, but of course you may also test the "composed" version. The trick of the exercise is to make both the equality a bit faster and to make sure that you are indeed generating lists which have smooth permutations. Random lists are not likely to be very smooth. There is indeed a difference between a Branch [] which indicates that things have been pruned away and a Leaf constructor which indicates that you have reached the end of the list.

(you might say: inefficient

-- DoaitseSwierstra - 24 Nov 2010