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

On Sat, Jan 5, 2013 at 7:31 PM, Neil Toronto <neil.toronto at gmail.com> wrote:
> 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.

Well, you might consider porting his code to Typed Racket.  I hear it
was designed for that. ;)

> 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...

Is the use of index types a fundamental refactoring, or something that
could be added to Hari's code?

I ask because having 3+ different functional random-access data
structures seems like a loss for Racket code interoperability over
all.

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

Certainly the data structure has fast functional update, I'm not
certain about the code in `tr-pfds`.  The data structure is described
here: http://en.wikipedia.org/wiki/VList; see in particular the paper
by Bagwell cited in the references.  It might also be worth looking at
the Hash-array Mapped Trie, currently used in Scala and Clojure, and
the RRB-tree, described here:
http://infoscience.epfl.ch/record/169879/files/RMTrees.pdf .

Sam

> 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.
>
>