[racket] Randomized bisimulation tests and Metropolis-Hastings random walk

From: Sam Tobin-Hochstadt (samth at ccs.neu.edu)
Date: Fri Jan 4 16:54:39 EST 2013

Have you tried testing your implementation against either David Van
Horn's implementation (not in TR) [1], or Hari's implementation (in
TR) [2]? Or against VLists (also in Hari's PFDs package)?

[1] https://github.com/dvanhorn/ralist
[2] https://github.com/takikawa/tr-pfds/tree/master/data/ralist

On Fri, Jan 4, 2013 at 4:45 PM, Neil Toronto <neil.toronto at gmail.com> wrote:
>
> I'm working on a Typed Racket implementation of Chris Okasaki's purely
> functional random-access lists, which are O(1) for `cons', `first' and
> `rest', and basically O(log(n)) for random access. I wanted solid randomized
> tests, and I figured the best way would be bisimulation: do exactly the
> same, random thing to a (Listof Integer) and an (RAList Integer), then
> ensure the lists are the same. Iterate N times, each time using the altered
> lists for the next bisimulation step.

Posted on the users mailing list.