I'm working on Euler 9 right now, which is a search for the one Pythagorean triple that sums to 1000. This was a very natural segue into looking at Racket's support for generators—we want to generate triplets rather than iterate over the possible values in some naïve fashion.

This problem drove me up against one of the interesting features of scoping that Racket makes you think about that other languages might not. This is an organic thought process, so the post meanders a little bit—as do most of them, I guess—but I think it's all fairly relevant.

It's been awhile since I've done anything to generate triples, but apparently an algorithm was known to the Babylonians (never put anything past those Chaldeans). The basic idea is that we take two numbers U and V such that U and V are relatively prime and generate the triple from the formulas U² + V², U² - V², and 2UV.

It's relatively straightforward to build a generator on top of streams in Racket (n.b., you need to (require racket/generator) to make this code work):

; first we create the streams
(define add2 (lambda (n) (+ 2 n)))
(define evens (stream-cons 2 (stream-map add2 evens)))
(define odds (stream-cons 1 (stream-map add2 odds)))

; then the generators
(define gevens (generator () (for ([e evens]) (yield e))))
(define godds (generator () (for ([o odds]) (yield o))))

(Admittedly perhaps this is a bit of overkill, but part of the exercise is learning language features.)

Then we can generate values in evens and odds easily enough by running the respective generator:

> (gevens)
2
> (gevens)
4

What becomes difficult in this case is how we put this together to generate the triples. An initial stab looked like this:

(define ptriples
  (generator ()
    (let ([u (godds)]
          [v (gevens)])
      (yield (list (+ (* u u) (* v v)) (- (* u u) (* v v)) (* 2 u v))))))

Aside from the rather serious logic bug that we cannot generate triples in order this way (we iterate the evens and odds together, but we don't want to do this—instead we want to iterate until we find a GCD for the two numbers), there is a closure here. The let binds u and v to permanent values: we don't reevaluate the generator at each call for the triples.

This is where I'd normally rely on some kind of set! or other state-permuting functionality of the software...but that seems like a no-no in the world of Racket. What to do?

Scheme offers a dynamically-scoped option called fluid-let, but this isn't available in Racket. Parameterization is an option, but it seems awfully clunky at first blush, especially since its benefits are unlikely to be useful in a project like this one.

As I work through the solution, I'll spend more time on this; I suspect in the end it'll be a moot point, but it's not a bad example—if a toy one—of how scoping rules affect functional programming.