Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Add partition generation #428

Open
treeowl opened this issue Jul 27, 2021 · 2 comments
Open

Add partition generation #428

treeowl opened this issue Jul 27, 2021 · 2 comments

Comments

@treeowl
Copy link
Contributor

treeowl commented Jul 27, 2021

When producing certain sorts of recursive structures, it would be very useful to have functions like

genPartition :: (MonadGen m, Integral n) => n -> m [n]
breakInN :: (MonadGen m, Integral n) => Int -> n -> m [n]

Each would take a non-negative integer and produce a list of strictly positive integers that sum to that integer. genPartition would generate partitions of all sizes; breakInN would take an argument indicating the desired length of the result list, and would fail if asked to produce an empty list or one that's too long.

Why for? Suppose you want to generate something like Data.Tree.Tree. The currently-available tools make it very hard to both

  1. Avoid producing a bunch of trivial trees.
  2. Avoid ever producing an utterly enormous tree.

With genPartition, you can produce a partition of the desired size, which determines the number of trees in the subforest and how large each of them should be.

Digging around online, I found this algorithm, but unfortunately I don't know enough to fully understand it, let alone implement it for Hedgehog.

@jacobstanley
Copy link
Member

This would be pretty awesome, I've thought a lot about trying to generate random programs and I can see this being related to the issues you see there.

@treeowl
Copy link
Contributor Author

treeowl commented Jan 27, 2022

I guess we'd also want versions that could also produce zeros. I have not thought about the how since submitting this issue.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants