[racket] idiomatic and fast

From: Deren Dohoda (deren.dohoda at gmail.com)
Date: Sat Apr 28 17:06:58 EDT 2012

I don't know if I could ever be a resource on "most idiomatic",
especially since I basically never use any of the for/et ceteras but
this feels reminiscent of "The Little Schemer" to me (except for the
internal define instead of letrec):

(define (make-triangles to-n)
  (define (next-triangle last-sum current-number)
    (if (> current-number to-n)
        empty
        (let ((new-sum (+ last-sum current-number)))
          (cons new-sum (next-triangle new-sum (add1 current-number))))))
  (next-triangle 0 1))

If for some reason I was worried about all the leftover conses---I try
not to worry about these things unless I have to---I could make it
totally tail-recursive at the cost of doing one big reverse at the
end:
(define (make-triangles-2 to-n)
  (define (next-triangle last-sum current-number results-so-far)
    (if (> current-number to-n)
        (reverse results-so-far)
        (let ((new-sum (+ last-sum current-number)))
          (next-triangle new-sum
                         (add1 current-number)
                         (cons new-sum results-so-far)))))
  (next-triangle 0 1 empty))
********
> (define-syntax-rule (my-time expression)
  (begin
    (collect-garbage)(collect-garbage)(collect-garbage)
    (time expression)))
> (let ((n 50000))
    (collect-garbage)(collect-garbage)(collect-garbage)
    (let ((one (my-time (make-triangles n)))
          (two (my-time (make-triangles-2 n)))
          (three (my-time (for/list ([i (in-range 2 (+ n 2))])
(for/sum ([j (in-range i)]) j)))))
      (and (equal? one two) (equal? two three))))
cpu time: 47 real time: 47 gc time: 0
cpu time: 15 real time: 16 gc time: 0
cpu time: 12984 real time: 14375 gc time: 140
#t

Deren

On Sat, Apr 28, 2012 at 3:54 PM, Joe Gilray <jgilray at gmail.com> wrote:
> Hi,
>
> I'm trying to come up with the most idiomatic way to generate triangle
> numbers that is also fast:
>
> (for/list ([i (in-range 2 22)]) (for/sum ([j (in-range i)]) j))
>
> works but is slow because it regenerates the sums each time
>
> (define s 0) (for/list ([i (in-range 1 21)]) (set! s (+ s i)) s)
>
> is fast, but ugly.
>
> How do I keep the sum in an idiomatic fashion?
>
> Thanks,
> -Joe
>
> ____________________
>  Racket Users list:
>  http://lists.racket-lang.org/users
>


Posted on the users mailing list.