Variadic Functions in Scheme (using nested maps)

Question

I have to define a variadic function in Scheme that takes the following form: (define (n-loop procedure [a list of pairs (x,y)]) where the list of pairs can be any length.

Each pair specifies a lower (inclusive) and upper bound (exclusive). That is, the following function call: (n-loop (lambda (x y) (inspect (list x y))) (0 2) (0 3)) produces:

(list x y) is (0 0)
(list x y) is (0 1)
(list x y) is (0 2)
(list x y) is (1 0)
(list x y) is (1 1)
(list x y) is (1 2)

Now, I had posted on this topic one previous time and was helped wonderfully. However, I have been given new guidelines to adhere to. The solution is to be found using nested maps only.

The way I've been going about this is as follows: find all of the values specified by the first set of bounds (in the example, (0 1 2)). This can be done by a function called (enumerate lowBound highBound). Then, I need to take each of those numbers, and cons each number in the next set of bounds (0 1 2 3), resulting in ((0 0) (0 1) (0 2) (0 3) (1 0)...).

What I've written to this point is the following:

(define (n-loop op . pairs)
     (apply op (generate pairs))
)

(define (generate pairs)
    (map (lambda (x) (cons x (generate (cdr pairs)))) 
         (map (lambda (x) (enumerate (car x) (cadr x))) pairs))
)

But for the given numbers, this outputs (0 1 0 1 2 0 1 2 0 1 2) when I need ((0 0) (0 1) (0 2) (0 3) (1 0)...). This is a nasty problem. Does anyone have any insight?

Óscar López · Accepted Answer · 2012-10-22 20:02:43Z

1

This problem is more complex than you seem to realize. In particular, generating the cartesian product of an arbitrary list of ranges needs far more work - have you tried your procedure with more than two ranges? It piqued my interest, this time I'll give my shot to a complete solution, using only procedures defined for the solution, simple operations over lists (cons, car, cdr, append), lambda, apply and map.

First, the helper procedures from simplest to hardest. We need a way to generate a range of numbers. If available, use build-list or for-list, but if you need to implement it from scratch:

(define (enumerate low high)
  (if (>= low high)
      '()
      (cons low
            (enumerate (add1 low) high))))

Now we need a mechanism for folding (reducing, accumulating) the values in a list. If available use foldr, otherwise implement it like this:

(define (reduce proc lst init)
  (if (null? lst)
      init
      (proc (car lst)
            (reduce proc (cdr lst) init))))

To avoid unnecessary nesting in lists, use a flatmap - a procedure that both maps and flattens a list of values:

(define (flatmap proc lst)
  (reduce (lambda (e acc)
            (append (proc e) acc))
          lst '()))

This is the core of the solution - a procedure that generates the cartesian product of an arbitrarily long list of lists of values denoting ranges:

(define (product . args)
  (reduce (lambda (pool result)
            (flatmap (lambda (x)
                       (map (lambda (y)
                              (cons x y))
                            result))
                     pool))
          args
          '(())))

Finally, the procedure in the question. It uses the helper procedures defined above, noticing that the op received can have an arbitrary number of parameters (depending on the number of ranges specified), so we need to use apply on each generated tuple of values:

(define (n-loop op . pairs)
  (map (lambda (tuple) (apply op tuple))
       (apply product
              (map (lambda (pair)
                     (enumerate (car pair) (cadr pair)))
                   pairs))))

Test it like this:

(n-loop (lambda (x y z) (list x y z))
        '(0 2) '(0 3) '(4 6))

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

edited Oct 22, 2012 at 20:02

answered Oct 22, 2012 at 16:07

Óscar López

237k38 gold badges321 silver badges391 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

aquemini Over a year ago

Right. I already had enumerate, accumulate, and flatmap defined. Just couldn't figure out how to combine them together. I'll test this out, thanks.

Óscar López Over a year ago

If it works for you, please don't forget to accept this answer by clicking on the check mark to its left.

aquemini Over a year ago

It hasn't worked yet, or I would have. Might just be a transcription error on my part, but it keeps returning the list null. Did you test it out?

Óscar López Over a year ago

Of course! The last lines in my answer were generated by the program. Please copy-paste the whole thing in a separate window and try again, maybe there's something different with respect to your code.

Óscar López Over a year ago

I tested the code in Racket - although I'm not using non-standard procedures and it should work on any Scheme interpreter.

Collectives™ on Stack Overflow

Variadic Functions in Scheme (using nested maps)

1 Answer 1

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related