On Sat, Jan 5, 2013 at 7:31 PM, Neil Toronto <neil.toro...@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.toro...@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. > > ____________________ Racket Users list: http://lists.racket-lang.org/users
