For Loop Construction Turned Functional

Question

I am currently learning Racket and want to do the following simple task: Construct a list which contains all tuples (i,j) : Int * Int with 0 <= i < N and 0 <= j < M.

In, let's say Python, I would immediately know how to approach this, by using for loops:

# Not using any modules on purpose here
a = []
for i in range(5):
    for j in range(6):
        a.append((i,j))     

But I have trouble doing this in Racket. By now I have found a solution which replicates the for-loop approach by using a recursively defined function which for a : A and f : Int -> A -> A satisfies the equations

for 0 a f = a
for n a f = for (n-1) ( (f n) a ) f  

which results in a chain of applications: for n a f = ( (f 0) o ... o (f n) )(a). (By f o g I mean composition of f and g). So first f n is applied to a, then f (n - 1) to the result of that, etc.

Given I basically want to do something like (f 0 0) o (f 0 1) o ... o (f N M) (a) this can be split up as:

 ((f 0 0) ... (f 0 M)) o ... o ((f N 0) ... (f N M)) (a)
= (λz. for M z (f 0)) o ... o (λz. for M z (f N)) (a)
= (λy. for N y (λi z. for M z (f i))) (a)

Which then translates to the following Racket code:

(define (for n x f) 
    (if (<= 0 n) 
        (for (- n 1) (f n x) f) 
        x))
        
(define a '())
(define (append i j x) (cons (cons i j) x))

((λ(x) 
    (for 5 x (λ(i x) 
       (for 6 x (λ(j x) 
              (append i j x)))))) a)

The answer produces the desired result and is at least nice regarding that it is obvious how to extend this construction with any number of additional loops.

But I am still wondering whether there isn't a neater functional way to do this.

I'm happy with any answer that does or does not use functions which might already be present in some library and which I have simply missed so far.

Answer 1

You are probably looking for for*/list:

(for*/list ([i (range 5)]
            [j (range 6)])
  (list i j))

See also Racket guide for Iterations and Comprehensions.

Answer 2

The for*/$@! forms are compact, but Scheme ("Programming languages should be designed not by piling feature on top of feature...") is still there:

(define (range-pairs m n)  ;; Nat Nat -> (Listof (Cons Nat Nat))
  ;; produce (range m) ? (range n)
  (do ([i (sub1 m) (sub1 i)]
       [a '() (do ([j (sub1 n) (sub1 j)]
                   [a a (cons (cons i j) a)])
                ((negative? j) a))])
    ((negative? i) a)))

Answer 3

One perhaps-nice way of thinking about this is to realise that this is a counting problem but the base for each digit can vary. So in the case you give this is counting in base (N M): the low-order digit is base N and the high-order digit is base M.

So, the first thing is to write a function which will increment numbers like this, with the obvious representation of a number being a list of digits. Here's one approach to that:

(define (increment-digits digits bases overflow)
  ;; Increment a number represented as a list of digits, where each digit is
  ;; in the corresponsing base.  On overflow return overflow.
  (let ripple ([ds digits]
               [bs bases]
               [rs '()]
               [carry? #t])
    (if (null? ds)
        ;; End of the digits
        (if carry?
            overflow
            (reverse rs))
        (match-let ([(cons d mds) ds]
                    [(cons b mbs) bs])
         (define nd (+ d (if carry? 1 0)))
         (if (= nd b)
             (ripple mds mbs (cons 0 rs) #t)
             (ripple mds mbs (cons nd rs) #f))))))

So now:

> (increment-digits (increment-digits '(0 0) '(2 2) #f) '(2 2) #f)
'(0 1)

Now, we can use this function to construct a stream of all the numbers in one of these per-digit bases:

(define (digit-stream bases)
  (let increment ([digits (make-list (length bases) 0)])
    (if digits
        (stream-cons digits
                     (increment (increment-digits digits bases #f)))
        empty-stream)))

Note that such a stream is completely lazy since stream-cons is lazy: it's not computed until you need it. So, for instance, you can happily say:

(digit-stream '(1000000 1000000 1000000 1000000))

which is a stream with 10^24 elements. And things like

(stream-ref (digit-stream '(1000000 1000000 1000000 1000000)) 1000000)

will work fine (it is (0 1 0 0) of course).

So now it merely remains to turn such a stream into a list:

> (stream->list (digit-stream '(2 5)))
'((0 0) (1 0) (0 1) (1 1) (0 2) (1 2) (0 3) (1 3) (0 4) (1 4))

Answer 4

Martin's answer is spot on.

Here are a few alternatives.

The first one is the most direct translation of the original Python:

(append*
  (for/list ([i 5])
    (for/list ([j 6])
       (list i j))))

The (for/list clauses expression) collects the values produced by expression in a list. The clauses are used to generate values that can be used in the expression.

The clause [i 5] is short for [i (in-range 5)] and will bind i to the values 0, 1, 2, 3, 4, 5 in order.

Thus

(for/list ([i 5])
   i)

will produce the list (0 1 2 3 4).

And similarly

(for/list ([i 5])
  (for/list ([j 6])
     (list i j)))

will produce the list (((0 0) (0 1) (0 2) ... (0 5)) ((1 0) ...)). Since you don't want a list of lists, but a single list, using append* will give you a single list instead.

Since nested lists are so common, one can use the for* variant instead:

(for*/list ([i 5] [j 6])
   (list i j)))

This will run through the the clauses in a nested fashion.

For comparison, try:

(for/list ([i 5] [j 6])
   (list i j)))

which will run through the clauses in parallel.

The result of the last example is ((0 0) (1 1) (2 2) (3 3) (4 4)). Note that the looping stops when the first clauses runs out of values.

Answer 5

For another pure-Scheme solution, you can use nested applications of (map) to accomplish the same thing.

(map (lambda (i)
       (map 
        (lambda (j)
          (list i j)) 
        (range 0 6 1))) 
     (range 0 5 1))

For strictness' sake, I have also implemented a somewhat overly elaborate (range) function to support this.

(define (range start end step)
  "Generates a list of integers from 'start' to 'end', stepping by 'step' values."
  (cond 
   ((= 0 step)
    '())
   ((or
     (and (< step 0)
          (< end start))
     (< start end))
    (cons start (range (+ start step) end step)))
   (else '())))

The output of this in #lang racket is:

'(((0 0) (0 1) (0 2) (0 3) (0 4) (0 5))
  ((1 0) (1 1) (1 2) (1 3) (1 4) (1 5))
  ((2 0) (2 1) (2 2) (2 3) (2 4) (2 5))
  ((3 0) (3 1) (3 2) (3 3) (3 4) (3 5))
  ((4 0) (4 1) (4 2) (4 3) (4 4) (4 5)))