Scheme中的變量函數（使用嵌套映射）

Question

我必須在Scheme中定義一個採用以下形式的可變參數函數：(define (n-loop procedure [a list of pairs (x,y)])其中對的列表可以是任意長度。

每一對指定一個較低（包含）和一個上限（排除）。也就是說，下面的函數調用：(n-loop (lambda (x y) (inspect (list x y))) (0 2) (0 3))生產：

(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) 

現在，我已經就這個話題發表一個以前的時間，就被奇妙地幫助。但是，我已經有了新的指導方針來遵守。解決方案只能使用嵌套地圖找到。

我一直在探討的方法如下：找到第一組邊界所指定的所有值（在本例中爲(0 1 2)）。這可以通過稱爲​​的函數完成。然後，我需要把這些數字中的每一個，並在下一組邊界(0 1 2 3)中使用每個數字，從而產生((0 0) (0 1) (0 2) (0 3) (1 0)...)。

我已經寫了這點如下：

(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)) 
) 

但對於給定的數字，當我需要((0 0) (0 1) (0 2) (0 3) (1 0)...)這個輸出(0 1 0 1 2 0 1 2 0 1 2)。這是一個討厭的問題。有沒有人有任何見解？

Answer 1

這個問題比你看起來更復雜。特別是，生成任意範圍列表的笛卡爾積需要更多的工作 - 您是否嘗試過兩個以上的範圍？這引起了我的興趣，這時候我給我一槍一個完整的解決方案，使用了列表（cons，car，cdr，append），lambda，apply和map只爲解決方案定義的過程，簡單的操作。

首先，輔助程序從最簡單到最難。我們需要一種方法來生成一系列數字。如果可能，使用build-list或for-list，但如果你需要從頭開始實現它：

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

現在我們需要在列表摺疊（減少，累計）的值的機制。如果可以使用foldr，否則實現這樣的：

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

爲了避免在列表中不必要的嵌套，使用flatmap - 這兩個地圖和變平值的列表中的程序：

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

這是解決方案的核心 - 生成任意長度的值列表的笛卡爾積的過程：

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

最後，問題中的過程。它使用上面定義的輔助程序，注意到的是，op接收可以具有參數（取決於特定範圍的數）的任意數，因此我們需要的值的每個所生成的元組使用apply：

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

像這樣測試：

(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))