let it leave me like a long breath

i’m writing some haskell & i’ve put together maybe the first complicated, math-based type i’ve ever written?

it’s for enumerable combinatorics equations and the deal is you got

total :: Enumerable a -> Integer
pick :: Monoid a => Enumerable a -> Integer -> Either EnumerableError a

where you can say ‘give me anything in [0..total x)’ and you’ll get out that specific permutation of values. so it lets you exhaustively enumerate certain random generators, basically. and also transform the random generation into just "pick a random number in the range and then just calculate that value", since it's possible to generate any given value without looking at its neighbors.

(the monoid constraint is just b/c otherwise it would have to return [a] which is kind of annoying since that’s basically never what you’d actually want)

i was testing this with quickcheck (also my first time using quickcheck) to make sure it actually did what i thought it did, and for a while i had a quickcheck Arbitrary instance that just did not terminate, since these are nested data structures that can store an arbitrarily complex expression. even after limiting it a bunch i still can get it to churn out nice compact expressions that have a total count of, for example, 458575485777749657103020327287430331293288631270492527580669116448151889324257271211264327503524251371913200211982149838423029009393779536545995926888936184639883868071199119583128675780396729867476981269731795729169851133510432815404825306221507642742572989858640526486864585952735243739518209812574667794254182198110257592401920000000000000000000000000000000000000000000000000000000000000000000000000000000000

so it has kind of been illuminating about the nature of combinatorial explosions.

i’m working on adding weights and constraints and some other stuff but that’s somewhat difficult, since some constraints are basically super easy to codify and others are known NP-complete.

i spent a lot of time thinking about how it would or would not be an applicative functor, and then it turns out the actual Applicative instance is like ~250 characters

anyway code follows ( Read more... )