Clojurians Log v2

I have a function that takes as input a large set of uniformly distributed random numbers and a directed, acyclic graph. It returns a random topological ordering of the graph. I’d like to hook this into test.check such that if I run test.check/quick-check twice with the same seed parameter then the same topological orderings will be generated.

As I understand it, test.check’s generators and combinators are designed to keep me from having to see the underlying RNG

and that’s worked really well until now, when I need a lot of uniformly distributed random numbers

Is the test.check.generators/->Generator function considered part of the public API?

@nwjsmith so if you had a generator for uniformly distributed random numbers, would that solve it?

@gfredericks yes, that would work beautifully

Then I could do a (gen/vector (gen/rand-int max) num-elements) and fmap my random-topological-ordering over it

(def gen-rand-double
  (gen/no-shrink
   (gen/->Generator
    (fn [rnd _size]
      (rose/pure (random/rand-double rnd))))))

Ah, there’s random/rand-long.

(def gen-rand-long
  (gen/no-shrink
   (gen/->Generator
    (fn [rnd _size]
      (rose/pure (random/rand-long rnd))))))

(gen/generate (gen/vector gen-rand-long) 10 100) ;; => [6200754525179398429 -3542882520031353397]
(gen/generate (gen/vector gen-rand-long) 10 100) ;; => [6200754525179398429 -3542882520031353397]

That seems to do the trick

I’m not really sure what the effects of no-shrink are here, or what rose/pure is doing. I’ll have to watch you’re old talk again to brush up on the internals.

Your talk from this week was fantastic by the way, really good guide to building custom generators.

(also, why do they have to be uniformly distributed?)

http://alexander-karzanov.net/Publications/91_LEO11_N.pdf

the algorithm is on page 2. I’ve got to generate a large number of random swaps of a topological ordering.

(the bottom of page 2)

At first I tried gen/choose, but I ended up with really bad distributions on the generator.

Choose is uniform, unlike most other builtin generators

Hrm. Maybe I just thought I’d end up with really bad distributions

I’ll try choose again.

no-shrink is a noop in your code I believe

You need uniform ints or doubles?

ints

What range?

between 0 and 2n-1, where n is the number of nodes in the graph.

Oooh, yeah, choose is bad for large n

Foolproof is (gen/vector (gen/choose 0 1) n), then fmap the bits to a bigint

But even if the algorithm demands uniform, I'm curious if testing with a nonuniform generator would actually be bad

But either way, there's no builtin bigint generator yet, which makes it harder for you :(

Putting it together with the approach you suggested should work though. I’m going to experiment a bit with all of the approaches above. Will report back.

BTW do you have a strategy for testing generators? Specifically how they shrink, their distribution, performance etc.

Experimenting at the REPL has been working for me, but now I have all of these useful graph-related generators and I’m hoping to open source them. Might have to come up with my own strategy.

No, that's an interesting idea. You can see examples in the tests of testing distribution & shrinking a bit, but it's all ad-hoc

Shrinking is particularly weird to test

Maybe...