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

Thanks for the pointers!

I can't use David Van Horn's because it's untyped, and I need to use 
this in Typed Racket. (No polymorphic, opaque types, and if I use the 
`struct' form in `require/typed', I'd get the performance problems I 
just wrote about on the dev list.)

Last time I checked Hari's RAList implementation, it was broken, so I 
started my own from scratch (which is what I worked from just now). He's 
fixed it, though. I could run some benchmarks, but I'm sure mine's a 
little faster. (I use index types for static guarantees and to get TR to 
optimize fixnum ops.) His has more functions, though...

Would a VList have fast functional update? I don't see a `list-set' 
exported, and I'm not familiar with the data structure.

Neil ⊥

On 01/04/2013 02:54 PM, Sam Tobin-Hochstadt wrote:
> 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.