Re: [racket-dev] Something wrong with check-within
submitted as bug report On Nov 11, 2010, at 7:54 PM, David Van Horn wrote: > On 11/11/10 7:34 PM, Nadeem Abdul Hamid wrote: >> The check-within in the follow program (in BSL/ISL) seems to hang. > > I see DrRacket (5.0.1, 5.0.99) loop on this: > _ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/dev
Re: [racket-dev] Something wrong with check-within
On 11/11/10 7:34 PM, Nadeem Abdul Hamid wrote: The check-within in the follow program (in BSL/ISL) seems to hang. I see DrRacket (5.0.1, 5.0.99) loop on this: (check-within (make-posn (list 0) (list 0)) (make-posn (list 0) (list 0)) 0.001) David _ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/dev
[racket-dev] Something wrong with check-within
The check-within in the follow program (in BSL/ISL) seems to hang. This is sort of the simplest example I can reproduce, but my students have been running into this with some more complicated test cases. I thought it might have to do with the inexact numbers, but even if you change the #i0.501 to 0.501, it still hangs. I'm seeing this problem in version 5.0.2, but I believe my students are running 5.0.1... (define-struct anim (ctrl-pts curve-pts t running?)) (define SAMPLE-WORLD-NEXT (make-anim (list (make-posn 20 190) (make-posn 10 10) (make-posn 100 10) (make-posn 125 190) (make-posn 150 30)) (list (make-posn 20 190)) 0.501 true)) (check-within SAMPLE-WORLD-NEXT (make-anim (list (make-posn 20 190) (make-posn 10 10) (make-posn 100 10) (make-posn 125 190) (make-posn 150 30)) (list (make-posn 20 190)) #i0.501 true) 0.001) _ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/dev
Re: [racket-dev] set operations
I've written a version of `set-choose', and also `set-first' and `set-rest' (with the obvious meanings) a few times. They can be useful. (I always waffled about whether to use just `set-choose', or `set-first' along with `set-rest'. Mathematically, `set-first' and `set-rest' don't make sense, but they're easier to code with.) Neil T Ryan Culpepper wrote: I think a function named set-choose should return just the chosen element. I would call the function below set-split, maybe. Also, beware that for/first returns #f if the sequence is empty. Ryan On 11/11/2010 01:38 PM, Jay McCarthy wrote: I think it is a good idea. Any objectors? Jay On Wed, Nov 10, 2010 at 12:40 PM, David Van Horn wrote: The set library is missing a convenient way of selecting an element from a set, making it hard to write recursive functions matching the inductive structure of a set. Could you add this function, or something like it? (define (set-choose s) (let ((x (for/first ([x (in-set s)]) x))) (values x (set-remove s x David _ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/dev _ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/dev _ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/dev
Re: [racket-dev] set operations
I think a function named set-choose should return just the chosen element. I would call the function below set-split, maybe. Also, beware that for/first returns #f if the sequence is empty. Ryan On 11/11/2010 01:38 PM, Jay McCarthy wrote: I think it is a good idea. Any objectors? Jay On Wed, Nov 10, 2010 at 12:40 PM, David Van Horn wrote: The set library is missing a convenient way of selecting an element from a set, making it hard to write recursive functions matching the inductive structure of a set. Could you add this function, or something like it? (define (set-choose s) (let ((x (for/first ([x (in-set s)]) x))) (values x (set-remove s x David _ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/dev _ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/dev
Re: [racket-dev] set operations
I think it is a good idea. Any objectors? Jay On Wed, Nov 10, 2010 at 12:40 PM, David Van Horn wrote: > The set library is missing a convenient way of selecting an element from a > set, making it hard to write recursive functions matching the inductive > structure of a set. > > Could you add this function, or something like it? > > (define (set-choose s) > (let ((x (for/first ([x (in-set s)]) > x))) > (values x (set-remove s x > > David > _ > For list-related administrative tasks: > http://lists.racket-lang.org/listinfo/dev > -- Jay McCarthy Assistant Professor / Brigham Young University http://faculty.cs.byu.edu/~jay "The glory of God is Intelligence" - D&C 93 _ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/dev
Re: [racket-dev] How about adding this simple list-shuffling procedure to racket?
When truly picking uniformally shuffled lists from a given list, see: http://telefonica.net/web2/koot/natural-to-permutation.scm and try (require srfi/27) ; for random-integer (require "natural-to-permutation.scm") (let* ((lst (build-list 1000 (lambda (k) (round (quotient k 10) (shuffler (make-K->P lst eq?)) (K (random-integer (nPs lst eq? (time (shuffler K))) Where random-integer is assumed to produce a uniform distribution. Jos _ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/dev
Re: [racket-dev] How about adding this simple list-shuffling procedure to racket?
5 minutes ago, Neil Toronto wrote: > Carl Eastlund wrote: > > It's "pick a random, uniform ordering, and then sort based on it". > > The random keys are chosen per element and cached (hence > > #:cache-keys? #t), not per comparison. > > Spanking good point, my good man. I think you're right. It's a very common method, and the classic example of the decorate-map-strip method that has some perl-guy's name slapped on it now. The wikipedia page on FY is pretty decent -- and one concern that I've encountered in the past is that it's sensitive to what that page calls "modulo bias". The decorated version is more robust, especially with (random) that works at the highest `random' granularity. (BTW, to compare them you should use some (random 1000) thing to avoid the fp cost.) -- ((lambda (x) (x x)) (lambda (x) (x x))) Eli Barzilay: http://barzilay.org/ Maze is Life! _ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/dev
Re: [racket-dev] How about adding this simple list-shuffling procedure to racket?
Carl Eastlund wrote: On Thu, Nov 11, 2010 at 12:40 PM, Neil Toronto wrote: I don't know. I know that the "run through the list and swap with another random element" algorithms are usually non-uniform, and so are a lot of other things that seem like they'd work. I wouldn't use something that wasn't proven to shuffle uniformly, at least for any serious statistics work. But this is not "run through the list and swap with another random element". It's "pick a random, uniform ordering, and then sort based on it". The random keys are chosen per element and cached (hence #:cache-keys? #t), not per comparison. Spanking good point, my good man. I think you're right. Just for the heck of it, I implemented the array-building version of Fisher-Yates and gave it a functional interface: (define (shuffle lst) (cond [(empty? lst) empty] [else (let* ([n (length lst)] [vec (make-vector n (first lst))]) (for ([e (in-list (rest lst))] [i (in-range 1 n)]) (define j (random (add1 i))) (vector-set! vec i (vector-ref vec j)) (vector-set! vec j e)) (vector->list vec))])) On my computer, it beats the sort-based shuffle on every list size I tried it on: 1, 5, 10, 100, and 1000. (Notably, not by much on length-10 lists.) It has better asymptotic complexity, so that should hold as the list size increases. Interestingly enough, it looks like O(n log n) is as good as purely functional code can get. The sorting version is downright elegant. (Well, it's not *purely* functional. But the Haskell people have to zip the list with random numbers in the Random monad, or some other such nonsense.) Neil T _ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/dev
Re: [racket-dev] How about adding this simple list-shuffling procedure to racket?
On Thu, Nov 11, 2010 at 11:40 AM, Carl Eastlund wrote: > On Thu, Nov 11, 2010 at 12:40 PM, Neil Toronto wrote: >> >> I don't know. I know that the "run through the list and swap with another >> random element" algorithms are usually non-uniform, and so are a lot of >> other things that seem like they'd work. I wouldn't use something that >> wasn't proven to shuffle uniformly, at least for any serious statistics >> work. > > But this is not "run through the list and swap with another random > element". It's "pick a random, uniform ordering, and then sort based > on it". The random keys are chosen per element and cached (hence > #:cache-keys? #t), not per comparison. Note that this is not the algorithm at the other end of the link that Neil T. sent; but one could probably make one like it in a simple manner using this idea. Robby _ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/dev
Re: [racket-dev] How about adding this simple list-shuffling procedure to racket?
On Thu, Nov 11, 2010 at 12:40 PM, Neil Toronto wrote: > > I don't know. I know that the "run through the list and swap with another > random element" algorithms are usually non-uniform, and so are a lot of > other things that seem like they'd work. I wouldn't use something that > wasn't proven to shuffle uniformly, at least for any serious statistics > work. But this is not "run through the list and swap with another random element". It's "pick a random, uniform ordering, and then sort based on it". The random keys are chosen per element and cached (hence #:cache-keys? #t), not per comparison. --Carl _ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/dev
Re: [racket-dev] How about adding this simple list-shuffling procedure to racket?
Carl Eastlund wrote: On Thu, Nov 11, 2010 at 12:18 PM, Neil Toronto wrote: Eric Hanchrow wrote: I find myself using this all the time; it seems it'd be handy to have built in. (define (shuffled list) (sort list < #:key (lambda (_) (random)) #:cache-keys? #t)) Is the distribution of shuffled lists uniform? That'd be hard to analyze, since it would depend on the sorting algorithm. I would guess it's not. (Don't worry if you didn't catch this yourself. It's not exactly straightforward.) It should be uniform regardless of algorithm, since #:cache-keys? is #t. Shouldn't it? I don't know. I know that the "run through the list and swap with another random element" algorithms are usually non-uniform, and so are a lot of other things that seem like they'd work. I wouldn't use something that wasn't proven to shuffle uniformly, at least for any serious statistics work. (I mean "proven," too. Distributions are very hard to establish using test cases.) Besides that, modern implementations of the Fisher-Yates shuffle are O(n), and this is O(n log n). Not a huge deal, but Fisher-Yates is simple enough that it's worth the cost to implement it once. Neil T _ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/dev
Re: [racket-dev] How about adding this simple list-shuffling procedure to racket?
I think that if random doesn't pick the same number twice you're guaranteed to be independent of the sorting algorithm, at least. Robby On Thu, Nov 11, 2010 at 11:18 AM, Neil Toronto wrote: > Eric Hanchrow wrote: >> >> I find myself using this all the time; it seems it'd be handy to have >> built in. >> >> (define (shuffled list) >> (sort list < #:key (lambda (_) (random)) #:cache-keys? #t)) > > Is the distribution of shuffled lists uniform? That'd be hard to analyze, > since it would depend on the sorting algorithm. I would guess it's not. > > (Don't worry if you didn't catch this yourself. It's not exactly > straightforward.) > > If you want an "unbiased" shuffle, see > > http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle > > Neil T > _ > For list-related administrative tasks: > http://lists.racket-lang.org/listinfo/dev > _ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/dev
Re: [racket-dev] How about adding this simple list-shuffling procedure to racket?
On Thu, Nov 11, 2010 at 12:18 PM, Neil Toronto wrote: > Eric Hanchrow wrote: >> >> I find myself using this all the time; it seems it'd be handy to have >> built in. >> >> (define (shuffled list) >> (sort list < #:key (lambda (_) (random)) #:cache-keys? #t)) > > Is the distribution of shuffled lists uniform? That'd be hard to analyze, > since it would depend on the sorting algorithm. I would guess it's not. > > (Don't worry if you didn't catch this yourself. It's not exactly > straightforward.) It should be uniform regardless of algorithm, since #:cache-keys? is #t. Shouldn't it? --Carl _ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/dev
Re: [racket-dev] How about adding this simple list-shuffling procedure to racket?
Eric Hanchrow wrote: I find myself using this all the time; it seems it'd be handy to have built in. (define (shuffled list) (sort list < #:key (lambda (_) (random)) #:cache-keys? #t)) Is the distribution of shuffled lists uniform? That'd be hard to analyze, since it would depend on the sorting algorithm. I would guess it's not. (Don't worry if you didn't catch this yourself. It's not exactly straightforward.) If you want an "unbiased" shuffle, see http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle Neil T _ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/dev
[racket-dev] How about adding this simple list-shuffling procedure to racket?
I find myself using this all the time; it seems it'd be handy to have built in. (define (shuffled list) (sort list < #:key (lambda (_) (random)) #:cache-keys? #t)) Thanks. _ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/dev
[racket-dev] start up error
This start up error shows up much more frequently for me with gr2 (1/2) than it used to (1/10). > $ drracket > [1] 35606 > [:~/0Unison/Amr] matthias% link: reference (phase 0) to a variable in module > "/Users/matthias/plt/collects/string-constants/string-constant.rkt" that is > uninitialized (phase level 0); reference appears in module: > "/Users/matthias/plt/collects/lazy/info.rkt" in: language > > === context === > /Users/matthias/plt/collects/lazy/info.rkt: [running body] > /Users/matthias/plt/collects/setup/getinfo.rkt:28:0: get-info/full > /Users/matthias/plt/collects/drracket/private/language-configuration.rkt:1210:4: > add-info-specified-language > /Users/matthias/plt/collects/racket/private/map.rkt:45:11: for-each > /Users/matthias/plt/collects/drracket/private/tools.rkt:453:0: run-phases > /Users/matthias/plt/collects/drracket/drracket.rkt: [running body] _ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/dev
