[racket] idiomatic and fast
From: Chris Stephenson (cs at csl.tc)
Date: Sat Apr 28 17:29:38 EDT 2012 

On 28/04/12 22:54, Joe Gilray wrote:
>
> (for/list ([i (inrange 2 22)]) (for/sum ([j (inrange i)]) j))
>
> works but is slow because it regenerates the sums each time
>
> (define s 0) (for/list ([i (inrange 1 21)]) (set! s (+ s i)) s)
>
> is fast, but ugly.
>
> How do I keep the sum in an idiomatic fashion?
>
Joe
Here are some solutions that I would consider more idiomatic. And fast
enough.
Your first (Slow) solution is asymptotically slower than the (fast and
ugly) solution . The time taken by slow is O(n^2). None of these
solutions have this problem.
Solution 1:
Let foldl keep the total for you
(define (firstntrianglenumbers n)
(rest (reverse (foldl (lambda (l r) (cons (+ l (first r)) r)) (list 0)
(rest (buildlist (add1 n) (lambda (x) x)))))))
This is blisteringly fast  it generates 20000 triangle numbers as fast
as your "ugly" code.
Solution 2:
Use the formula discovered by the schoolboy Gauss:
(define (firstntrianglenumbersformula n)
(map (lambda (n) (/ (* n (add1 n)) 2)) (rest (buildlist n
(lambda(x) x)))))
I was surprised to find that this seems to be twice as slow as solution
1. Not really a significant difference, though, and easier to understand
than 1.
Solution 3:
Make an infinite list of triangle numbers in lazy racket. Not very fast,
but very idiomatic, and it does make a list of *all* the triangle numbers.
About 20 times as slow as solution 1, but still O(n)
#lang lazy
(define integers (cons 1 (map add1 integers)))
(define trianglenumbers (cons 1 (map + (rest integers) trianglenumbers)))
You need to evaluate the line below to actually see the list
(time (!!list(take 20000 trianglenumbers)))
Try it a second time and get a (pleasant) surprise.
; it goes a bit (I mean a lot) faster the second time
(time (!!list(take 20000 trianglenumbers)))
Chris

Chris Stephenson
cs at csl.tc