Playing around with Racket still in the few hours I have during the weeks. Thinking functionally has been a good exercise, but I'm still working through the question of when it's appropriate to use set! to permute state. Euler problem 4, which asks for the largest palindromic number made from the product of two three digit numbers, really posed the problem.

I was inspired a bit by O'Connell's implementations in Python, which included several different avenues for making the results more efficient.

Walking through some solutions, then, we turn first to the preliminaries:

(define (string-reverse s)
  (list->string (reverse (string->list s))))

(define (palin? s)
  (cond ([string? s] (equal? s (string-reverse s)))
        ([number? s] (let ((mxs (number->string s)))
                       (palin? mxs)))
        (else (error "I don't know how to handle anything but strings and numbers."))))

This is the basic checker for a palindromic number. There are probably faster ways to manipulate integral values for this, but I didn't pursue that in my efforts to make things more efficient.

So let's approach using the naïve method:

(define (euler4-1 low up)
  (apply max 
         (filter palin?
                 (for*/list ([i (in-range low up)]
                             [j (in-range low up)])
                   (* i j)))))

> (time (euler4-1 100 1000))
cpu time: 476 real time: 479 gc time: 96

This implementation does twice as much work as it needs to since we repeat factors in the i and j loops. We can trim it down very easily by using [j (in-range i up)] instead. This produces, not unexpectedly, somewhat better results.

> (time (euler4-2 100 1000))
cpu time: 248 real time: 248 gc time: 48 

Next, as O'Connell notes, we have to realize that this is a monotonically increasing function: we can therefore count down rather than counting up and break out of the loop when we find an i,j pair that's both palindromic and smaller than the current maximum.

This notion of "current maximum," though, implies some state. In functional languages right Racket, state is kind of a dirty thing and purists eschew it. (To be fair, though, even a for*/list is kind of a dirty thing: we should be recursing instead of iterating, right? I guess under the hood we are...)

Even so, a functional approach using named lets seems dreadfully awkward. Instead, storing the max value in a variable makes the most sense to me:

(define (euler4-3 lb ub)
  ;; This is a non-idiomatic way to do this, but ...
  (let ((mx 0))
    (for*/list ([i (in-range ub lb -1)]
                [j (in-range ub i -1)]
                #:when (and (< mx (* i j)) (palin? (* i j))))
      (set! mx (* i j)))
    mx))

> (time (euler4-3 100 1000))
cpu time: 32 real time: 32 gc time: 0

The maximum value is locally scoped and a simple type, so there shouldn't be any concern that permuting it will somehow leak out elsewhere. Moreover it seems more straightforward to read this code than trying to create nested lets with two loops. I'm also a fan of the #:when guard here that prevents execution unless the conditions are met (i.e., the loop body executes only when the maximum value is less than i * j and i * j is a palindrome).