Scheme/Lisp嵌套循環和遞歸

Question

我試圖解決一個問題，要求我使用嵌套循環或嵌套遞歸的Scheme。

例如我有兩個名單，我必須檢查他們的笛卡爾產品的條件。

解決這些類型問題的最佳方法是什麼？任何關於如何簡化這些類型的函數的指針？

---

我會詳細說明一下，因爲我的意圖可能不夠清楚。

有規律的遞歸函數可能是這樣的：

(define (factorial n) 
    (factorial-impl n 1)) 

(define (factorial-impl n t) 
    (if (eq? n 0) 
     t 
     (factorial-impl (- n 1) (* t n)))) 

試圖寫一個類似的功能，但與嵌套遞歸引入了複雜的的代碼一個新的水平，我想知道是什麼的基本模式是這些類型的功能，因爲它可以變得非常難看，速度非常快。

作爲一個具體的例子，我正在尋找最簡單的方式來訪問兩個列表的笛卡爾積中的所有項目。

Answer 1

在Scheme中， 「map」函數通常用於計算基於另一個列表的一個列表。

事實上，在方案中，地圖需要一個「正論證」功能和「n」名單，並調用 功能爲每個列表中的每個對應的元素：

> (map * '(3 4 5) '(1 2 3)) 
(3 8 15) 

但一個很自然的除這將是一個「笛卡爾映射」函數，它將用你從每個列表中選取一個元素的所有不同方式調用你的「n-argument」函數。我花了一段時間才能弄清楚到底如何做到這一點，但在這裏你去：

; curry takes: 
; * a p-argument function AND 
; * n actual arguments, 
; and returns a function requiring only (p-n) arguments 
; where the first "n" arguments are already bound. A simple 
; example 
; (define add1 (curry + 1)) 
; (add1 3) 
; => 4 
; Many other languages implicitly "curry" whenever you call 
; a function with not enough arguments. 
(define curry 
    (lambda (f . c) (lambda x (apply f (append c x))))) 

; take a list of tuples and an element, return another list 
; with that element stitched on to each of the tuples: 
; e.g. 
; > (stitch '(1 2 3) 4) 
; ((4 . 1) (4 . 2) (4 . 3)) 
(define stitch 
    (lambda (tuples element) 
     (map (curry cons element) tuples))) 

; Flatten takes a list of lists and produces a single list 
; e.g. 
; > (flatten '((1 2) (3 4))) 
; (1 2 3 4) 
(define flatten 
    (curry apply append)) 

; cartesian takes two lists and returns their cartesian product 
; e.g. 
; > (cartesian '(1 2 3) '(4 5)) 
; ((1 . 4) (1 . 5) (2 . 4) (2 . 5) (3 . 4) (3 . 5)) 
(define cartesian 
    (lambda (l1 l2) 
     (flatten (map (curry stitch l2) l1)))) 

; cartesian-lists takes a list of lists 
; and returns a single list containing the cartesian product of all of the lists. 
; We start with a list containing a single 'nil', so that we create a 
; "list of lists" rather than a list of "tuples". 

; The other interesting function we use here is "fold-right" (sometimes called 
; "foldr" or "reduce" in other implementations). It can be used 
; to collapse a list from right to left using some binary operation and an 
; initial value. 
; e.g. 
; (fold-right cons '() '(1 2 3)) 
; is equivalent to 
; ((cons 1 (cons 2 (cons 3 '()))) 
; In our case, we have a list of lists, and our binary operation is to get the 
; "cartesian product" between each list. 
(define cartesian-lists 
    (lambda (lists) 
     (fold-right cartesian '(()) lists))) 

; cartesian-map takes a n-argument function and n lists 
; and returns a single list containing the result of calling that 
; n-argument function for each combination of elements in the list: 
; > (cartesian-map list '(a b) '(c d e) '(f g)) 
; ((a c f) (a c g) (a d f) (a d g) (a e f) (a e g) (b c f) 
; (b c g) (b d f) (b d g) (b e f) (b e g)) 
(define cartesian-map 
    (lambda (f . lists) 
     (map (curry apply f) (cartesian-lists lists)))) 

沒有所有的評論和一些更緊湊的功能定義語法有：

(define (curry f . c) (lambda x (apply f (append c x)))) 
(define (stitch tuples element) 
     (map (curry cons element) tuples)) 
(define flatten (curry apply append)) 
(define (cartesian l1 l2) 
     (flatten (map (curry stitch l2) l1))) 
(define cartesian-lists (curry fold-right cartesian '(())))) 
(define (cartesian-map f . lists) 
     (map (curry apply f) (cartesian-lists lists))) 

我以爲以上是合理的「優雅」 ......直到有人向我展示了相當的哈斯克爾定義：

cartes f (a:b:[]) = [ f x y | x <- a , y <- b ] 
cartes f (a:b:bs) = cartes f ([ f x y | x <- a , y <- b ]:bs) 

2線！

我不是那麼有信心在我的執行效率 - 尤其是「扁平化」的步驟是快寫，但最終可能會調用「追加」 一個非常大的數量的列表，這可能會或可能不會很在一些Scheme實現上效率很高。

爲了達到最終的實用性/實用性，您需要一個可以採用「懶惰評估」列表/流/迭代器而不是完全指定列表的版本....如果您喜歡，可以使用「笛卡爾地圖流」功能然後返回結果的「流」......但這取決於上下文（我正在考慮在SICP中引入的「流」概念）......並且由於它的延遲評估而免費來自Haskell版本。一般來說，在Scheme中，如果你想在某個時間點「循環」循環，你也可以使用延續（例如拋出一個異常，但在控制流程的Scheme中被接受）。

我很開心寫這個！

Answer 2

我不知道我看到了什麼問題。 我相信在函數式編程中你必須理解的主要事情是：通過編寫幾個更簡單的函數來構建複雜的函數。

例如，在這種情況下：

;compute the list of the (x,y) for y in l 
(define (pairs x l) 
    (define (aux accu x l) 
    (if (null? l) 
     accu 
     (let ((y (car l)) 
       (tail (cdr l))) 
      (aux (cons (cons x y) accu) x tail)))) 
    (aux '() x l)) 

(define (cartesian-product l m) 
    (define (aux accu l) 
    (if (null? l) 
     accu 
     (let ((x (car l)) 
       (tail (cdr l))) 
      (aux (append (pairs x m) accu) tail)))) 
    (aux '() l))  

您識別不同的步驟：獲得笛卡爾積，如果「循環」在第一列表中，你將不得不能計算第二個列表中的(x,y)的列表，y。

Answer 3

這裏有一些很好的答案了，但對於簡單的嵌套函數（如您的尾遞歸階乘），我更喜歡一個名爲令：

(define factorial 
    (lambda (n) 
    (let factorial-impl ([n n] [t 1]) 
     (if (eq? n 0) 
     t 
     (factorial-impl (- n 1) (* t n))))))